Rodinia: A Benchmark Suite for Heterogeneous Computing

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.8883

This paper presents and characterizes Rodinia, a benchmark suite for heterogeneous computing. To help architects study emerging platforms such as GPUs (Graphics Processing Units), Rodinia includes applications and kernels which target multi-core CPU and GPU platforms. The choice of applications is inspired by Berkeley’s dwarf taxonomy. Our characterization shows that the Rodinia benchmarks cover a wide range of parallel communication patterns, synchronization techniques and power consumption, and has led to some important architectural insight, such as the growing importance of memory-bandwidth limitations and the consequent importance of data layout. I.

[StreamGraph] 小規模行列に対する SVD の応用例

国際会議 IISWC のストーリー立てに関する続き。一つの concern は、ワークロードとしての汎用性が重要となるが、ストリームアプリケーションのワークロードに共通な行列計算として 小規模な行列に対する SVD 計算が様々な応用に使えるという主張をする。SST はもちろんだが、その他にも例が必要。画像特徴抽出などは典型的であるが、いくつかの論文を参照する必要がある。少し調べてみよう。

A fast SVD based video watermarking algorithm compatible with MPEG2 Standard
http://www.columbia.edu/itc/applied/e3101/SVD_applications.pdf

続きは後ほど

[StreamGPU] IISWC 2011

IISWC 2011 のストーリー立て。Workload Characterization に関する学会なので以下のようなストーリー構成にする。
(1) リアルタイムの異常検知・変化点検知は、データストリーム処理では非常に重要なアプリケーション(=Workload)の一つである
- 様々な異常検知・変化点検知機構が提案されているが、SST はノンパラメトリックな手法として強力な手法である
- 但し、計算量は O(n^3) であり、リアルタイム性を実現するのは困難である。
- 本論文では GPU による高速化に関する知見を示す。特に既存の CULA ライブラリを示したときの性能特性と、提案する GPU タスク並列による最適化を施した際の性能特性を示す
(2) CULA ライブラリによるナイーブな高速化→スケールしない＋小さい行列サイズで性能が出ない、という結果を示す
(3) GPU タスク並列手法による性能最適化＋評価結果

学会の性質上、より汎用性が重要。ある特定のアルゴリズムに関するワークロードに関する性能特性を測っただけでは難しい。書き方によるが、強調するのは上記の SST, SVD のアルゴリズムは１インスタンスの一つであり、他のストリーム＋GPUにも（ある程度）一般的に言える知見をこの論文によって提供できると主張することが重要。

DEBS に出した論文をベースに、上記の構成に変える作業を行う。既に、実験結果など（データ転送の内訳以外）はほぼ揃っているので、構成の改変と論文の完成度を上げるのみ。

TODO
- 小規模な行列サイズに対する SVD (Single Value Decomposition) ベースのアルゴリズムを調査する (できるだけ早く)

[StreamGPU] 論文の方向性

上野君と議論し、今後2本の論文を出すことにする。

- GPUタスク並列の論文ーSVD と IKA-SST によって評価。IKA-SSTに関しては、カーネル実行とデータ転送のオーバーラップ、複数カーネル実行、データ差分転送による最適化は無しで純粋にタスク並列で勝負

- もう一本は、「異常検知アルゴリズム IKA-SST のGPUによる最適化」これはタスク並列＋カーネル実行とデータ転送のオーバーラップ、複数カーネル実行、データ差分転送による最適化あり

近況

マルチGPU・マルチノード上の高速 MapReduce 処理系, そしてインクリメンタルグラフ処理の研究が本格的に始まり、非常に楽しみです。また、何度も書いてますが、大規模分散ファイルシステムとの統合、そして耐故障性も重要な研究要素なので、研究が一段落した人には是非取り組んで欲しいと思います。

石井君には, Yahoo S4 vs System S/SPADEの定性的（できれば定量的にも）比較を行う解説記事を書いてもらうことになりました。また、動的に変化するネットワークグラフを視覚化するアプリケーションも作ってもらうことになりました。研究のインパクトを視覚的に伝えるのも非常に重要なので、期待してます。

また、DEBSの学会の締切りに関しては、高データレートアプリケーションへのGPUタスク並列化の論文を、上野君が鋭意執筆してくれてます。

皆さん、それぞれこの調子で頑張ってください。

GIM-V on GPUs に関連する論文

まずは以下の論文を読みましょう。

1. Pegasus (GIM-Vの理解と Hadoop コード理解）: 過去のブログ参照
2. Mars (MapReduceのGPU実装）http://www.citeulike.org/group/1670/article/4009779
3. PageRank, RWR(http://suzumura-lab.blogspot.com/2010/12/streamgraph-rwr.html), HADIなどのGPU高速化に関する論文

GIM-V のGPU実装

松浦君の修論テーマの方向性が決まりました。
「大規模グラフ分析プログラミングモデル GIM-V の マルチ GPU による実現と高速化」

この研究の肝は以下の2つです。
(1) マルチノードでかつマルチ GPU 環境を十二分に活用した高速化.
(2) GIM-V のモデルを記述した論理実行モデルの提唱と最適化コード生成

　西井君のテーマである Incremental GIM-V （ストリーム計算）のテーマと大きく関係していますが、バッチ計算とストリーム計算を両方享受できるような統一的な実行基盤を作ることも当然視野に入れます。この統一的な実行基盤で欠かせないのはスケジューリング機構ですが、松浦君の「バッチ処理とストリーム処理のスケジューリング機構」と石井君の「ストリーム処理のクラウドへの委譲」に関する研究がその先駆け的な研究という位置づけになります。

あと不足しているのは、特に大規模グラフデータを格納する分散ファイルシステムへのアクセス機構とローカリティを意識したデータスケジューリングです。また、耐故障性も重要です。この点に関しては、新M1の新たな研究となるか、新B4の研究になるかは相談で決めていきましょう。

[StreamGPU] 高データレートストリーム処理へのGPUタスク並列の適用

上野氏: 次の論文（まずは査読つき国内論文）の概要
ターゲット学会：FIT査読付き論文、またはその他


----
タイトル：高データレートストリーム処理へのGPUタスク並列の適用

問題
・小さい計算量のアルゴリズムへの対応
・データレートが高い場合の、IOボトルネック
・計算量の異なるタスクを同時に計算するには？（ウィンドウサイズが異なるなど）

解決策
・問題サイズの大きさによっては、warpごとのタスク並列で計算（○）
・データ転送と計算のオーバーラップ（△）
・計算量の異なるタスクを、複数カーネル同時実行で計算（△）

評価
・IKA-SST

結果
・条件が良ければ、CPU1コアに対して、teslaで60倍、GTX 460で40倍の性能

考察
・CPU計算部分の計算量は、ウィンドウサイズによらず一定なので、ウィンドウサイズを小さくすると、CPUの計算がボトルネックになる

[StreamGraph] RWR の並列化・高速化

　ノード間の関連度を計算する手法　Random Walk With Restarts は　PEGASUS の１アプリケーションとしても実装されており、ソースコードにも入っています。

　また、RWRのGPUによる高速化が以下の論文で発表されています。

「Fast Mining Algorithms of Graph data on GPUs」,KDD LDMTAS2010 (KDD2010のワークショップ）, Xintian Yang (Ohio State University) (PDF)

[StreamGraph] グラフアルゴリズムの GPU 化

Fast Mining Algorithms of Graph data on GPUs, LDMTA 2010

Scaling up the sparse matrix-vector multiplication kernel on modern Graphics Processing Units (GPU) has been at the heart of numerous studies in both academia and industry. In this article we present a novel approach to data representation for computing this kernel, particularly targeting sparse matrices representing power-law graphs. Using real data, we show how our representation scheme, coupled witha novel tiling algorithm, can yield signi ficant bene ts over the current state of the art GPU and CPU e orts on a number of core data mining algorithms such as PageRank, HITS and Random Walk with Restart.

http://arnetminer.org/confs/LDMTA2010/KDD-LDMTA-YangXintian.pdf

Accelerating Large Graph Algorithms on the GPU Using CUDA, 2007

http://www.springerlink.com/content/y4816x2q7475v93n/

Large graphs involving millions of vertices are common in many practical applications and are challenging to process. Practical-time implementations using high-end computers are reported but are accessible only to a few. Graphics Processing Units (GPUs) of today have high computation power and low price. They have a restrictive programming model and are tricky to use. The G80 line of Nvidia GPUs can be treated as a SIMD processor array using the CUDA programming model. We present a few fundamental algorithms – including breadth first search, single source shortest path, and all-pairs shortest path – using CUDA on large graphs. We can compute the single source shortest path on a 10 million vertex graph in 1.5 seconds using the Nvidia 8800GTX GPU costing $600. In some cases optimal sequential algorithm is not the fastest on the GPU architecture. GPUs have great potential as high-performance co-processors.

A Fast GPU Algorithm for Graph Connectivity, IPDPS 2010

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5470817

raphics processing units provide a large computational power at a very low price which position them as an ubiquitous accelerator. General purpose programming on the graphics processing units (GPGPU) is best suited for regular data parallel algorithms. They are not directly amenable for algorithms which have irregular data access patterns such as list ranking, and finding the connected components of a graph, and the like. In this work, we present a GPU-optimized implementation for finding the connected components of a given graph. Our implementation tries to minimize the impact of irregularity, both at the data level and functional level. Our implementation achieves a speed up of 9 to 12 times over the best sequential CPU implementation. For instance, our implementation finds connected components of a graph of 10 million nodes and 60 million edges in about 500 milliseconds on a GPU, given a random edge list. We also draw interesting observations on why PRAM algorithms, such as the Shiloach-Vishkin algorithm may not be a good fit for the GPU and how they should be modified.

VLDB 2010

http://www.vldb2010.org/proceedings/files/a_research.xml

p.472: The Performance of MapReduce: An In-depth Study
Dawei Jiang (National University of Singapore, Republic of Singapore), Beng Chin Ooi (National University of Singapore, Republic of Singapore), Lei Shi (National University of Singapore, Republic of Singapore), Sai Wu (National University of Singapore, Republic of Singapore)

p.129: Energy Management for MapReduce Clusters
Willis Lang (University of Wisconsin-Madison, United States of America), Jignesh Patel (University of Wisconsin-Madison, United States of America)

p.81: MapMerge: Correlating Independent Schema Mappings
Bogdan Alexe (University of California Santa Cruz, United States of America), Mauricio Hernández (IBM Research, United States of America), Lucian Popa (IBM Almaden Research Center, United States of America), Wang-Chiew Tan (University of California Santa Cruz, United States of Americ

p.449: iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques
Wook-Shin Han (Kyungpook National University, Republic of Korea), Jinsoo Lee (Kyungpook National University, Republic of Korea), Minh-Duc Pham (Kyungpook National University, Republic of Korea), Jeffrey Yu (The Chinese University of Hong Kong, People’s Republic of China)

p.340: On Graph Query Optimization in Large Networks
Peixiang Zhao (University of Illinois at Urbana-Champaign, United States of America), Jiawei Han (University of Illinois at Urbana-Champaign, United States of America)

p.330: Dremel: Interactive Analysis of Web-Scale Datasets
Sergey Melnik (Google, United States of America), Andrey Gubarev (Google, United States of America), Jing Jing Long (Google, United States of America), Geoffrey Romer (Google, United States of America), Shiva Shivakumar (Google, United States of America), Matt Tolton (Google, United States of America), Theo Vassilakis (Google, United States of America)

p.285: HaLoop: Efficient Iterative Data Processing on Large Clusters
Yingyi Bu (University of Washington, United States of America), Bill Howe (University of Washington, United States of America), Magdalena Balazinska (University of Washington, United States of America), Michael Ernst (University of Washington, United States of America)

p.264: Graph Pattern Matching: From Intractable to Polynomial Time
Wenfei Fan (University of Edinburgh, United Kingdom), Jianzhong Li (Harbin Institute of Technology, People’s Republic of China), Shuai Ma (University of Edinburgh, United Kingdom), Nan Tang (University of Edinburgh, United Kingdom), Yinghui Wu (University of Edinburgh, United Kingdom), Yunpeng Wu (National University of Defense Technology, People’s Republic of China)

p.276: GRAIL: Scalable Reachability Index for Large Graphs
Hilmi Yildirim (Rensselaer Polytechnic Institute, United States of America), Vineet Chaoji (Yahoo! Research Labs, United States of America), Mohammed Zaki (Rensselaer Polytechnic Institute, United States of America

p.220: High-Performance Dynamic Pattern Matching over Disordered Streams
Badrish Chandramouli (Microsoft Research, United States of America), Jonathan Goldstein (Microsoft Research, United States of America), David Maier (Portland State University, United States of America)

p.232: SECRET: A Model for Analysis of the Execution Semantics of Stream Processing Systems
Irina Botan (Eidgenössische Technische Hochschule Zürich, Switzerland), Roozbeh Derakhshan (Eidgenössische Technische Hochschule Zürich, Switzerland), Nihal Dindar (Eidgenössische Technische Hochschule Zürich, Switzerland), Laura Haas (IBM Almaden Research Center, United States of America), Renée Miller (University of Toronto, Canada), Nesime Tatbul (Eidgenössische Technische Hochschule Zürich, Switzerland)

p.244: Recognizing Patterns in Streams with Imprecise Timestamps
Haopeng Zhang (University of Massachusetts Amherst, United States of America), Yanlei Diao (University of Massachusetts Amherst, United States of America), Neil Immerman (University of Massachusetts Amherst, United States of America)

有害 Tweet リアルタイム監視

データストリーム処理が応用できる例

http://japan.internet.com/busnews/20100831/5.html

"利用者のツイートが掲載される企業のキャンペーンページなどに無関係な宣伝や公序良俗に反するツイートが投稿された際は、リアルタイムでブロックしたり、メールでアラート"
"オプションで、ハッシュタグや一般キーワードの監視、商品購入を薦めるフレーズなどの自動ピックアップ機能"

[StreamGPU] Singular Value Decomposition for Collaborative Filtering on a GPU

協調フィルタリング用 特異値分解の GPU 用による高速化
----
Singular Value Decomposition for Collaborative Filtering on a GPU, 2010

A collaborative ltering predicts customers' unknown preferences from known preferences. In a computation of the collaborative ltering, a singular value decomposition (SVD) is needed to reduce the size of a large scale matrix so that the burden for the next phase computation will be decreased. In this application, SVD means a roughly approximated factorization of a given matrix into smaller sized matrices. Webb (a.k.a. Simon Funk) showed an e ffective algorithm to compute SVD toward a solution of an open competition called "NetixPrize". The algorithm utilizes an iterative method so that the error of approximation improves in each step of the iteration. We give a GPU version of Webb's algorithm. Our algorithm is implemented in the CUDA and it is shown to be effi cient by an experiment.


http://iopscience.iop.org/1757-899X/10/1/012017/pdf/1757-899X_10_1_012017.pdf

---

Collaborative Filtering 関連の参考論文

A Survey of Collaborative Filtering Techniques, 2009
http://www.hindawi.com/journals/aai/2009/421425.html

Yunhong Zhou, Large-scale Parallel Collaborative Filtering forthe Netflix Prize
http://www.hpl.hp.com/personal/Robert_Schreiber/papers/2008%20AAIM%20Netflix/netflix_aaim08(submitted).pdf

[StreamGPU] 第72回全国大会優秀賞！！

森田君の論文が、第72回全国大会優秀賞・奨励賞選定委員で審議の結果、大会優秀賞 に選ばれました。おめでとうございます！http://www.ipsj.or.jp/01kyotsu/award/taikai_yushu/index.html

なお、表彰式は、次回の第73回全国大会（東京工業大学 大岡山キャンパス、2011.3.2-4）で行う予定だそうです。
http://www.ipsj.or.jp/10jigyo/taikai/73kai/index.html

COMSYS 2010

COMSYS 2010 http://www.ipsj.or.jp/sig/os/index.php?ComSys2010

研究室からは以下の論文を出したいと思います。

- 松浦君＋雁瀬君 --> StreamDS の話

- 上野君 --> StreamGPU の話

7月23日が論文アップロード締め切りです。がんばりましょう。

[StreamGPU] Regular Expression on GPU

正規表現を GPU 上で実行する研究。GPU に関係している人、要チェック。

Regular Expression Matching on Graphics Hardware for Intrusion Detection

http://www.ics.forth.gr/dcs/Activities/papers/gnort-regexp.raid09.pdf

R on GPU

オープンソースの統計言語 Rを GPU を用いて高速化するプロジェクト
http://brainarray.mbni.med.umich.edu/brainarray/rgpgpu/

重回帰分析による 適応的なウィンドウサイズの決定

森田君が計測してくれた以下のデータに対して 統計言語 R を用いた重回帰分析を行ったので報告します。

実行時間 T は、CPU におけるウィンドウサイズ Wcと GPUにおけるウィンドウサイズと Wg の2変数の組み合わせによって、実験的に得られているので、実行時間 Tを Xc, Xg から説明する重回帰式を求めてみましょう。

T= a0 + a1 * Wc + a2 * Wg

以下, R 言語を持ちた分析. 第１フィールドに実行時間、第2フィールドに CPU のウィンドウサイズ、第3フィールドに GPU のウィンドウサイズから構成されるCSV 形式のデータを読み込みます。

> data1<-read.csv("C:/temp/streamgpu1.csv")

Time,CPU,GPU

1.8883369,50,500

2.3832237,50,600

2.7971815,50,700

3.2233268,50,800

3.773477,50,900

4.4216436,50,1000

5.1433544,50,1100

5.8385782,50,1200

6.5608456,50,1300

...

R による重回帰分析の実行と結果の表示

> data1.lm<-lm(Time~CPU+GPU,data=data1)

> summary(data1.lm)

Call:

lm(formula = Time ~ CPU + GPU, data = data1)

Residuals:

Min 1Q Median 3Q Max

-26.076 -4.510 1.308 5.718 30.277

Coefficients:

Estimate Std. Error t value Pr(>|t|)

(Intercept) -2.638e+01 1.488e+00 -17.73 <2e-16>

CPU 4.471e-02 2.677e-03 16.70 <2e-16>

GPU 2.541e-02 6.373e-04 39.87 <2e-16>

---

Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 8.565 on 249 degrees of freedom

Multiple R-squared: 0.8824, Adjusted R-squared: 0.8814

F-statistic: 934 on 2 and 249 DF, p-value: <>

決定係数は 0.8824, 調整済みの決定係数は 0.8814

次に係数の算出。

> round(coefficients(data1.lm),6)

(Intercept) CPU GPU

-26.376838 0.044705 0.025407

これによって、以下の関係式が得られることがわかります。

T (s) =-26.38 + 0.044705 * Wc + 0.025407 * Wg

次に、説明変数 Xg, Xc に相関関係があると思われるので、以下のように相互作用を考慮した回帰係数を求めます。

> data1.lm2<-lm(Time~(CPU+GPU)^2,data=data1)

Call:

lm(formula = Time ~ (CPU + GPU)^2, data = data1)

Residuals:

Min 1Q Median 3Q Max

-25.4525 -4.4603 0.4802 4.4581 31.8098

Coefficients:

Estimate Std. Error t value Pr(>|t|)

(Intercept) -1.258e+01 2.023e+00 -6.217 2.13e-09 ***

CPU 7.909e-03 4.752e-03 1.664 0.0973 .

GPU 1.621e-02 1.175e-03 13.798 <>

CPU:GPU 2.453e-05 2.759e-06 8.891 <>

---

Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 7.473 on 248 degrees of freedom

Multiple R-squared: 0.9108, Adjusted R-squared: 0.9097

F-statistic: 844.2 on 3 and 248 DF, p-value: <>

決定係数は 0.9108, 調整済みの決定係数は 0.9097で、相互作用効果を考慮していない場合の 0.8824, 0.8814 より増加しており、相互作用効果を考慮したモデルの当てはめがよいと言える。

次に係数の決定。

> round(coefficients(data1.lm2),6)

(Intercept) CPU GPU CPU:GPU

-12.578282 0.007909 0.016208 0.000025

Y(g,c) = a0 + a1 * Wc + a2 * Wg + a3 Wc Wg

T (s) = -12.578282 + 0.007909 * Wc + 0.016208 * Wg + 0.000025 * Wc * Wg

前処理の実験データによって上記の回帰式を得ることができたので、応答時間（異常検知までの最大値）の T (秒) がアプリケーションによって与えられ、かつ Wg のウィンドウサイズを 1000 と設定すれば、この式によって、適切な CPU 側でのウィンドウサイズ Wc を以下の式によって求めることができます。

Wc = (T + 12.578282 - 0.016208 * Wg) / (0.007909 + 0.000025 * Wg)

例えば、T=5 と設定したときは、Wc = 41.6385。T=30 と設定したときは Wc = 801 と求められます。

以上です。

評価アプリケーション

M岡研究室の4年生の学生と少しお話したが、評価しているアプリケーションが気になるので以下の論文のアプリケーションを列挙してみる。

様々な機械学習アルゴリズムの MapReduce による実装と高速化

http://www.cs.stanford.edu/people/ang//papers/nips06-mapreducemulticore.pdf

http://www.icsi.berkeley.edu/~arlo/publications/gillick_cs262a_proj.pdf

• Locally Weighted Linear Regression (LWLR)
• Naive Bayes (NB)
• Gaussian Discriminative Analysis (GDA)
• k-means
• Logistic Regression (LR)
• Neural Network (NN)
• Principal Components Analysis (PCA)
• Independent Component Analysis (ICA)
• Expectation Maximization (EM)
• Support Vector Machine (SVM)

この中で、それぞれ GPU による高速化している研究はあるのでそれを使って評価するのが良いだろう。

• k-means の GPU の高速化
  http://www.computer.org/portal/web/csdl/doi/10.1109/CSIE.2009.491

また、ちょっと視点は異なるが、Hadoop が各企業でどのように使われているかをまとめたサイトもある。

http://wiki.apache.org/hadoop/PoweredBy

そのほかに、Apache プロジェクトの中に Mahout という機械学習のアルゴリズムを MapReduce などのフレームワークでスケーラブルにするプロジェクトもあります。

http://lucene.apache.org/mahout/taste.html

StreamGPU: CPU-GPU 協調動作において SLAに基づく適応的なウィンドウサイズ調節機構の提案

　CPU-GPU 協調動作において、お互いの干渉を受けるため、両者のレイテンシを満たす中で最大のウィンドウサイズを決定することが重要である。これを、システマティックに求める方法を考える。

[問題の前提]
SLA (レイテンシ, 結果スコアの精度など)に関してはレイテンシのみを対象

(1) 短いウィンドウサイズの局所的解析：低レイテンシが要求される
- レイテンシの上限が決まっている (例: 10ms)
- CPU で実行
(2) 長いウィンドウサイズの大局的解析：
- レイテンシの上限が決まっている (例: 5秒)
- GPU で実行

[実行環境]
- CPU (2コア) と GPU から構成されるシングルノード。
- GPU, CPU の性能は仮定しない
- 他のジョブは稼動していなく、占有可能

[解く問題]
上記の前提において、(1),(2)で定められたレイテンシを満たす最適なウィンドウサイズ (CPU側、GPU側)を決定する


[解決手法]
CPU 側で守るべきレイテンシを Lc, GPU 側で守るべき レイテンシをLg とし、この両者のレイテンシを満たす最適なウィンドウサイズを CPU, GPU 側で算出する手法を以下に提示する。

0. GPU のウィンドウサイズ Wg を固定する.

CPU, GPU 単体のパフォーマンスを与えられた評価環境においてテストし, 以下のようなデータを算出する。これらのデータから GPU が CPU の性能を上回るウィンドウサイズ Wcpu-gpuを求める。下記の１から６のステップは GPU のウィンドウサイズを固定させるが、このサイズは Wcpu-gpu 以上のサイズから開始する。下記の森田君の実験の場合は 450 が開始点となる。ただし、GPU 側のレイテンシ Lg があらかじめ与えられる。



1. CPU の Conflict が存在しない場合の GPU 単体の実行時間を TG0とする

2. GPU のウィンドウサイズ Wg を固定させて、CPU のウィンドウサイズ Wc を増加させたときの Tg と Tc を測定する。Tg はCPUでの計算やメモリ転送などの干渉を受けて増加する.　

3. 2 のデータを受けて、定義域をサイズ、値域を実行時間とする関数をそれぞれ Fg, Fc とし、その関数を非線形の回帰分析によって算出する。

4. Lg （CPU側で守るべきレイテンシ）を与えたときの最大の Wc (CPUのウィンドウサイズ）をステップ3 によって算出した関数 Fg を用いて, Lg = Fg(x) --> x = Fg-1(Lg) (-1 は逆関数) のように計算し、x を Wc とする。

5. ステップ4を用いて算出したWc と関数 Fc を用いて　(Tc = Fc(Wc)) , Wcにおける実行時間 Tc を算出.

6. ステップ5を用いて算出した Tc が CPU側のレイテンシより下回っているかどうかを検査。
(6-1) 下回っている場合には CPU 側のウィンドウサイズはステップ4 によって得られた Wc とする
(6-2) 上回っている場合には CPU 側のウィンドウサイズWc を Fc-1(Lc) によって求めた値とする
下図においては(6-1) が上図、(6-2) が下図となる