Microsoft PowerPoint - omp-02.ppt
|
|
|
- こうた つまがみ
- 5 years ago
- Views:
Transcription
1 科学技術計算のための マルチコアプログラミング入門第 Ⅱ 部 : オーダリング 2009 年 9 月 14 日 15 日中島研吾
2 /15 2 データ依存性の解決策は? オーダリング (Ordering) について Red-Black,Multicolor(MC) Cuthill-McKee(CM),Reverse-CM(RCM) オーダリングと収束の関係 オーダリングの実装 オーダリング付 ICCG 法の実装
3 /15 3 ICCG 法の並列化 内積 :OK DAXPY:OK 行列ベクトル積 :OK 前処理 : なんとかしなければならない 単純にOpenMPなどの指示行 (directive) を挿入しただけでは 並列化 できない
4 /15 4 データ依存性の解決策 = 色分け, 色づけ (coloring) 依存性を持たない ( 互いに独立な ) 要素を同時に処理するようにすれば良い
5 /15 5 データ依存性の解決策 = 色分け, 色づけ (coloring) 依存性を持たない ( 互いに独立な ) 要素を同時に処理するようにすれば良い
6 /15 6 データ依存性の解決策 = 色分け, 色づけ (coloring) 依存性を持たない要素群 同じ 色 に色づけ (coloring) する 最も単純な色づけ :Red-Black Coloring(2 色 )
7 /15 7 Red-Black(1/3) !$omp parallel do private (ip,i,j,val) do ip= 1, 4 do i= INDEX(ip-1)+1, INDEX(ip) if (COLOR(i).eq.RED) then WVAL= W(i,Z) do j= 1, INL(i) WVAL= WVAL - AL(j,i) * W(IAL(j,i),Z) W(i,Z)= WVAL * W(i,DD)!$omp parallel!$omp parallel do private (ip,i,j,val) do ip= 1, 4 do i= INDEX(ip-1)+1, INDEX(ip) if (COLOR(i).eq.BLACK) then WVAL= W(i,Z) do j= 1, INL(i) WVAL= WVAL - AL(j,i) * W(IAL(j,i),Z) W(i,Z)= WVAL * W(i,DD)!$omp parallel
8 /15 8 Red-Black(2/3) !$omp parallel do private (ip,i,j,val) do ip= 1, 4 do i= INDEX(ip-1)+1, INDEX(ip) if (COLOR(i).eq.RED) then WVAL= W(i,Z) do j= 1, INL(i) WVAL= WVAL - AL(j,i) * W(IAL(j,i),Z) W(i,Z)= WVAL * W(i,DD)!$omp parallel Red 要素を処理する間, 右辺に来るのは必ず Black 要素 RED: 書き出し,BLACK: 読み込み Red 要素の処理をする間, Black 要素の内容が変わることは無い データ依存性が回避される
9 /15 9 Red-Black(3/3) Black 要素を処理する間, 右辺に来るのは必ず Red 要素 RED: 読み込み,BLACK: 書き出し Black 要素の処理をする間, Red 要素の内容が変わることは無い データ依存性が回避される!$omp parallel do private (ip,i,j,val) do ip= 1, 4 do i= INDEX(ip-1)+1, INDEX(ip) if (COLOR(i).eq.BLACK) then WVAL= W(i,Z) do j= 1, INL(i) WVAL= WVAL - AL(j,i) * W(IAL(j,i),Z) W(i,Z)= WVAL * W(i,DD)!$omp parallel
10 /15 10 Red-Black Ordering/Reordering do icol= 1, 2!$omp parallel do private (ip,i,j,val) do ip= 1, 4 do i= INDEX(ip-1,icol)+1, INDEX(ip,icol) WVAL= W(i,Z) do j= 1, INL(i) WVAL= WVAL - AL(j,i) * W(IAL(j,i),Z) W(i,Z)= WVAL * W(i,DD)!$omp parallel INDEX(0,1)= 0 INDEX(1,1)= 2 INDEX(2,1)= 4 INDEX(3,1)= 6 INDEX(4,1)= 8 INDEX(0,2)= 8 INDEX(1,2)=10 INDEX(2,2)=12 INDEX(3,2)=14 INDEX(4,2)=16 要素番号を Red Black の順にふり直す (reordering, ordering) とプログラムが簡単になる ( 計算効率も高い )
11 /15 11 データ依存性の解決策は? オーダリング (Ordering) について Red-Black,Multicolor(MC) Cuthill-McKee(CM),Reverse-CM(RCM) オーダリングと収束の関係 オーダリングの実装 オーダリング付 ICCG 法の実装 マルチコアへの実装 (OpenMP) へ向けて
12 /15 12 オーダリング (ordering) の効用 並列性を得る : 依存性の排除 Fill-inを減らす バンド幅を減らす, プロフィルを減らす ブロック化 もともとは,4 色問題, 一筆書き ( 巡回セールスマン問題 ) 等と関連 数値計算への適用 小国他 行列計算ソフトウェア, 丸善 (1991)
13 /15 13 並列計算のためのオーダリング法 マルチカラーオーダリング 並列性 Red-Black オーダリング (2 色 ) 等 CM 法 (Cuthill-McKee),RCM 法 (Reverse Cuthill- McKee) fill-inを減らす マトリクスのバンド幅を減らす, プロフィルを減らす 並列性
14 /15 14 用語の定義 β i : i 行における非ゼロ成分の列番号の最大値を k とするとき,β i = k i バンド幅 : β i の最大値 プロフィル : β i の和 バンド幅, プロフィル,Fill-inともに少ない方が都合が良い 特にバンド幅, プロフィルは収束に影響
15 /15 15 β i の定義 非ゼロ成分
16 /15 16 マルチカラーオーダリング Multicolor Ordering MC 法 と呼ぶ マルチカラーオーダリングは, 互いに独立で依存性のない要素同士を同じ 色 に分類し, その分類に従って要素や節点の番号を振りなおす手法である Red-Black は 2 色の場合 複雑形状の場合, より多い 色 が必要 同じ 色 に分類された要素に関する計算は並列に実施できる ある要素と, その要素に接続する周囲の要素は違う 色 に属している
17 /15 17 MC 法の基本的なアルゴリズム 1 要素数 色数 を m とする 2 初期要素番号が若い順に互いに独立な要素を m 個選び出して彩色し, 次の色へ進む 3 指定した色数に達して, 全ての要素が彩色されるまで 2を繰り返す 4 色番号の若い順番に要素を再番号づけする ( 各色内では初期要素番号が若い順 )
18 /15 18 MC 法 :4 色
19 /15 19 修正された MC 法 1 次数 最小の要素を 新要素番号 =1, 第 1 色 とし, 色数のカウンタ=1 とする 2 ITEMcou=ICELTOT/NCOLORtotに相当する値を 各色に含まれる要素数 とする 3 ITEMcou 個の独立な要素を初期要素番号が若い順に選び出す 4 ITEMcou 個の要素が選ばれるか, あるいは独立な要素が無くなったら 色数のカウンタ=2 として第 2 色へ進む 5 全ての要素が彩色されるまで3,4を繰り返す 6 最終的な色数カウンタの値をNCOLORtotとし, 色番号の若い順番に要素を再番号づけする ( 各色内では初期要素番号の順番 )
20 /15 20 次数 (degree): 各点に隣接する点の数
21 /15 21 修正された MC 法 1 次数 最小の要素を 新要素番号 =1, 第 1 色 とし, 色数のカウンタ=1 とする 2 ITEMcou=ICELTOT/NCOLORtotに相当する値を 各色に含まれる要素数 とする 3 ITEMcou 個の独立な要素を初期要素番号が若い順に選び出す 4 ITEMcou 個の要素が選ばれるか, あるいは独立な要素が無くなったら 色数のカウンタ=2 として第 2 色へ進む 5 全ての要素が彩色されるまで3,4を繰り返す 6 最終的な色数カウンタの値をNCOLORtotとし, 色番号の若い順番に要素を再番号づけする ( 各色内では初期要素番号の順番 ) 同じ色: 連続した 新 要素番号
22 /15 22 MC 法 :3 色に設定, 実は 5 色
23 /15 23 並列計算のためのオーダリング法 マルチカラーオーダリング 並列性 Red-Black オーダリング (2 色 ) 等 CM 法 (Cuthill-McKee),RCM 法 (Reverse Cuthill- McKee) fill-inを減らす マトリクスのバンド幅を減らす, プロフィルを減らす 並列性
24 /15 24 CM 法の基本的なアルゴリズム 1 各点に隣接する点の数を 次数 (degree), 最小次数の点を レベル =1 の点とする 2 レベル =k-1 に属する点に隣接する点を レベル =k とする 全ての点にレベルづけがされるまで k を1つずつ増やして繰り返す 3 全ての点がレベルづけされたら, レベルの順番に再番号づけする ( 各レベル内では 次数 の番号が少ない順 )
25 /15 25 Cuthill-Mckee Ordering(CM 法 ) の例 Level=1 Level=1 Level= Level=1 Level=2 Level=3 Level=4 レベル順 ( 各レベル内では次数の少ない順 ) に並び替え Level= Level=1 Level=2 Level= Level= Level=1 Level=2 Level= Level=1 Level=2 Level=3
26 /15 26 RCM(Reverse CM) まず CM の手順を実行 次数 (degree) の計算 レベル (k(k 2)) の要素の選択 繰り返し, 再番号付け 再々番号付け CM の番号付けを更に逆順にふり直す Fill-in が CM の場合より少なくなる
27 /15 27 初期状態 バンド幅 4 プロフィル 51 Fill-in 非ゼロ成分, Fill-in
28 /15 28 CM オーダリング バンド幅 4 プロフィル 46 Fill-in 非ゼロ成分, Fill-in
29 /15 29 RCM オーダリング バンド幅 4 プロフィル 46 Fill-in 非ゼロ成分, Fill-in
30 /15 30 修正された CM 法 並列計算向け 1 各要素に隣接する要素数を 次数 とし, 最小次数の要素を レベル =1 の要素とする 2 レベル =k-1 の要素に隣接する要素を レベル =k とする 同じレベルに属する要素はデータ依存性が発生しないように, 隣接している要素同士が同じレベルに入る場合は一方を除外する ( 現状では先に見つかった要素を優先している ) 全ての点要素にレベルづけがされるまで k を1つずつ増やして繰り返す 3 全ての要素がレベルづけされたら, レベルの順番に再番号づけする 同じレベル : 連続した 新 要素番号
31 /15 31 修正された CM 法 同じレベルに属する要素はデータ依存性が発生しない
32 /15 32 修正された CM 法 レベルの少ない順に並び替え
33 /15 33 修正された CM 法 レベルの少ない順に並び替え
34 /15 34 MC 法,CM/RCM 法の違い CM 法では, 同一レベル ( 色 ) における各要素の独立性だけでなく, 計算順序を考慮して, レベル間の依存性を考慮している点
35 /15 35 データ依存性の解決策は? オーダリング (Ordering) について Red-Black,Multicolor(MC) Cuthill-McKee(CM),Reverse-CM(RCM) オーダリングと収束の関係 オーダリングの実装 オーダリング付 ICCG 法の実装 マルチコアへの実装 (OpenMP) へ向けて
36 /15 36 ICCG 法の収束 ( 後述 ) Incompatible Node # ITERATIONS COLOR# COLOR# (20 3 =8,000 要素,EPSICCG=10-8 ) ( :ICCG(L1), :ICCG-MC, :ICCG-CM, :ICCG-RCM)
37 /15 37 収束とオーダリングの関係 ( 後述 ) 要素数 =20 3 Red-Black ~ 4 色 < 初期状態 ~ CM,RCM 初期状態 バンド幅 4 プロフィル 51 Fill-in 54 4 色 バンド幅 10 プロフィル 57 Fill-in 46 Red-Black バンド幅 10 プロフィル 77 Fill-in 44 CM,RCM バンド幅 4 プロフィル 46 Fill-in 44
38 /15 38 反復回数と色数の関係 Incompatible Nodes とは? Doi, S. (NEC) et al 影響の伝わり方 他から影響を受けない点が Incompatible Node 周囲の全ての点よりも番号が若い, ということ少ない方が収束が早い
39 /15 39 CM(Cuthill-McKee) の場合
40 /15 40 Red-Black の場合並列性は高いが incompatible node 多い ILU 系前処理,Gauss-Seidel で反復回数増加
41 / 色の場合並列性は弱まるが incompatible node は減少 ILU 系前処理,Gauss-Seidel で反復回数減少
42 /15 42 収束とオーダリング これ以外にも境界条件の影響などもあり, 一概には言えない たとえば CM と RCM は本問題の場合全く同じになるはずであるが,RCM の方が若干収束が良い
43 /15 43 オーダリングの効果 オーダリングによって, 行列の処理の順番が変わり, 何らかの 改善 が得られる 並列性の付与 : 並列計算, ベクトル計算への適合性 収束が早くなる場合もある 例に示したような単純な形状ですら, オーダリングをしなければ, 並列化, ベクトル化できない 注意点 オーダリングによって答えが変わることもある 対象としている物理, 数学に関する深い知識と洞察を要する
44 /15 44 オーダリング手法の比較 三次元弾性問題 MCは収束遅い, 不安定 ( 特に不均質 ( 悪条件 ) 問題 ) Cyclic-Mulricoloring + RCM(CM-RCM) が有効 ( 後述 ) Washio et al Iterations Homogeneous Iterations Heterogeneous color # 3D Linear-Elastic Problems with 32,768 DOF color # MC CM-RCM No reordering
45 /15 45 データ依存性の解決策は? オーダリング (Ordering) について Red-Black,Multicolor(MC) Cuthill-McKee(CM),Reverse-CM(RCM) オーダリングと収束の関係 オーダリングの実装 オーダリング付 ICCG 法の実装 マルチコアへの実装 (OpenMP) へ向けて
46 /15 46 オーダリング実装 :L2-color 実習 三次元形状 ( ここでは二次元 ) の色づけのプログラム マルチカラーオーダリング,CM 法,RCM 法 (CMRCM についてはあとで ) $ cd <$L2>/color/src $ make $ cd../run $./L2-color You have 16 elements. How many colors do you need? #COLOR must be more than 2 and #COLOR must not be more than 16 CM if #COLOR.eq. 0 RCM if #COLOR.eq.-1 CMRCM if #COLOR.le.-2 => $ ls color.log colo.inp この 2 次元形状を接続関係に基づき色づけする
47 /15 47 実施内容 (2/2) 実習 2 つのファイルが生成される color.log 新旧メッシュ番号の対応表行列関連情報 color.inp メッシュの色分けファイル (MicroAVS 用 ) 入力 : 0 (CM, 7 colors) 入力 : 3 (5 colors) 入力 : 4 (4 colors)
48 /15 48 入力 =0: CM(7 色 ) #new 1 #old 1 color 1 #new 2 #old 2 color 2 #new 3 #old 5 color 2 #new 4 #old 3 color 3 #new 5 #old 6 color 3 #new 6 #old 9 color 3 #new 7 #old 4 color 4 #new 8 #old 7 color 4 #new 9 #old 10 color 4 #new 10 #old 13 color 4 #new 11 #old 8 color 5 #new 12 #old 11 color 5 #new 13 #old 14 color 5 #new 14 #old 12 color 6 #new 15 #old 15 color 6 #new 16 #old 16 color
49 /15 49 入力 =0: CM(7 色 ) #new 1 #old 1 color 1 #new 2 #old 2 color 2 #new 3 #old 5 color 2 #new 4 #old 3 color 3 #new 5 #old 6 color 3 #new 6 #old 9 color 3 #new 7 #old 4 color 4 #new 8 #old 7 color 4 #new 9 #old 10 color 4 #new 10 #old 13 color 4 #new 11 #old 8 color 5 #new 12 #old 11 color 5 #new 13 #old 14 color 5 #new 14 #old 12 color 6 #new 15 #old 15 color 6 #new 16 #old 16 color
50 /15 50 入力 =-1: RCM(7 色 ) #new 1 #old 16 color 1 #new 2 #old 15 color 2 #new 3 #old 12 color 2 #new 4 #old 14 color 3 #new 5 #old 11 color 3 #new 6 #old 8 color 3 #new 7 #old 13 color 4 #new 8 #old 10 color 4 #new 9 #old 7 color 4 #new 10 #old 4 color 4 #new 11 #old 9 color 5 #new 12 #old 6 color 5 #new 13 #old 3 color 5 #new 14 #old 5 color 6 #new 15 #old 2 color 6 #new 16 #old 1 color
51 /15 51 入力 =3: 実際は 5 色 ( マルチカラー ) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color
52 /15 52 入力 =3: 実際は 5 色 ( マルチカラー ) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color /3=5 5 個ずつ独立な要素を元の番号順に選択
53 /15 53 入力 =3: 実際は 5 色 (multicolor) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color /3=5 5 個ずつ独立な要素を元の番号順に選択
54 /15 54 入力 =3: 実際は 5 色 ( マルチカラー ) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color /3= 独立な要素が無くなったら次の色へ
55 /15 55 入力 =3: 実際は 5 色 ( マルチカラー ) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color /3= 独立な要素が無くなったら次の色へ
56 /15 56 入力 =3: 実際は 5 色 ( マルチカラー ) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color /3= 最終的に 5 色必要であった
57 /15 57 入力 =4: 4 色 ( マルチカラー ) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 2 color 2 #new 6 #old 4 color 2 #new 7 #old 5 color 2 #new 8 #old 7 color 2 #new 9 #old 9 color 3 #new 10 #old 11 color 3 #new 11 #old 14 color 3 #new 12 #old 16 color 3 #new 13 #old 10 color 4 #new 14 #old 12 color 4 #new 15 #old 13 color 4 #new 16 #old 15 color
58 /15 入力 =3: 実際は5 色 ( マルチカラー ) 58 color.log: 行列関連情報出力 ### INITIAL connectivity I= 1 INL(i)= 0 INU(i)= 2 IAL: IAU: 2 5 I= 2 INL(i)= 1 INU(i)= 2 IAL: 1 IAU: 3 6 I= 3 INL(i)= 1 INU(i)= 2 IAL: 2 IAU: 4 7 I= 4 INL(i)= 1 INU(i)= 1 IAL: 3 IAU: 8 I= 5 INL(i)= 1 INU(i)= 2 IAL: 1 IAU: 6 9 I= 6 INL(i)= 2 INU(i)= 2 IAL: 2 5 IAU: 7 10 I= 7 INL(i)= 2 INU(i)= 2 IAL: 3 6 IAU: 8 11 I= 8 INL(i)= 2 INU(i)= 1 IAL: 4 7 IAU: 12 I= 9 INL(i)= 1 INU(i)= 2 IAL: 5 IAU: I= 10 INL(i)= 2 INU(i)= 2 IAL: 6 9 IAU: I= 11 INL(i)= 2 INU(i)= 2 IAL: 7 10 IAU: I= 12 INL(i)= 2 INU(i)= 1 IAL: 8 11 IAU: 16 I= 13 INL(i)= 1 INU(i)= 1 IAL: 9 IAU: 14 I= 14 INL(i)= 2 INU(i)= 1 IAL: IAU: 15 I= 15 INL(i)= 2 INU(i)= 1 IAL: IAU: 16 I= 16 INL(i)= 2 INU(i)= 0 IAL: IAU: COLOR number 5 #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color 5
59 /15 入力 =3: 実際は5 色 ( マルチカラー ) 59 color.log: 行列関連情報出力 ### FINAL connectivity I= 1 INL(i)= 0 INU(i)= 2 IAL: IAU: 6 8 I= 2 INL(i)= 0 INU(i)= 3 IAL: IAU: I= 3 INL(i)= 0 INU(i)= 4 IAL: IAU: I= 4 INL(i)= 0 INU(i)= 3 IAL: IAU: I= 5 INL(i)= 0 INU(i)= 3 IAL: IAU: I= 6 INL(i)= 3 INU(i)= 0 IAL: IAU: I= 7 INL(i)= 2 INU(i)= 0 IAL: 2 4 IAU: I= 8 INL(i)= 3 INU(i)= 0 IAL: IAU: I= 9 INL(i)= 3 INU(i)= 1 IAL: IAU: 11 I= 10 INL(i)= 2 INU(i)= 2 IAL: 3 5 IAU: I= 11 INL(i)= 2 INU(i)= 2 IAL: 9 10 IAU: I= 12 INL(i)= 1 INU(i)= 1 IAL: 5 IAU: 15 I= 13 INL(i)= 0 INU(i)= 2 IAL: IAU: I= 14 INL(i)= 3 INU(i)= 0 IAL: IAU: I= 15 INL(i)= 2 INU(i)= 1 IAL: IAU: 16 I= 16 INL(i)= 3 INU(i)= 0 IAL: IAU:
60 /15 60 L2-color のソースファイル $ cd <$L2>/coloring/src $ ls この 2 次元形状を色づけする
61 /15 61 program MAIN use STRUCT use PCG implicit REAL*8 (A-H,O-Z) call POINTER_INIT call POI_GEN call OUTUCD プログラムの構成 open (21, file='color.log', status='unknown') write (21,'(//,a,i8,/)') 'COLOR number', NCOLORtot do ic= 1, NCOLORtot do i= COLORindex(ic-1)+1, COLORindex(ic) write (21,'(3(a,i8))') ' #new', i, ' #old', NEWtoOLD(i), & & ' color', ic close (21) stop end
62 /15 62 プログラムの構成図 MAIN メインルーチン INPUT 制御ファイル読込 INPUT.DAT POINTER_INIT メッシュファイル読込 mesh.dat MC マルチカラーオーダリング BOUNDARY_CELL φ=0 を設定する要素の探索 CELL_METRICS 表面積, 体積等の計算 POI_GEN 行列コネクティビティ生成 CM Cuthill-McKee オーダリング RCM Reverse Cuthill-McKee オーダリング CMRCM Cyclic-Multicoloring + Reverse Cuthill-McKee オーダリング
63 /15 63 program MAIN use STRUCT use PCG implicit REAL*8 (A-H,O-Z) call POINTER_INIT call POI_GEN call OUTUCD プログラムの構成 open (21, file='color.log', status='unknown') write (21,'(//,a,i8,/)') 'COLOR number', NCOLORtot do ic= 1, NCOLORtot do i= COLORindex(ic-1)+1, COLORindex(ic) write (21,'(3(a,i8))') ' #new', i, ' #old', NEWtoOLD(i), & & ' color', ic close (21) stop end
64 /15 64 module STRUCT module STRUCT include 'precision.inc' -- METRICs & FLUX integer (kind=kint) :: ICELTOT, ICELTOTp, N integer (kind=kint) :: NX, NY, NZ, NXP1, NYP1, NZP1, IBNODTOT integer (kind=kint) :: NXc, NYc, NZc real (kind=kreal) :: & DX, DY, DZ, XAREA, YAREA, ZAREA, RDX, RDY, RDZ, & RDX2, RDY2, RDZ2, R2DX, R2DY, R2DZ real (kind=kreal), dimension(:), allocatable :: & VOLCEL, VOLNOD, RVC, RVN integer (kind=kint), dimension(:,:), allocatable :: & XYZ, NEIBcell & & & & ICELTOT: 要素数 N: 節点数 NX,NY,NZ: x,y,z 方向要素数 NXP1,NYP1,NZP1: x,y,z 方向節点数 IBNODTOT: NXP1 NYP1 XYZ(ICELTOT,3): 要素座標 ( 後述 ) NEIBcell(ICELTOT,6): 隣接要素 ( 後述 ) -- BOUNDARYs integer (kind=kint) :: ZmaxCELtot integer (kind=kint), dimension(:), allocatable :: BC_INDEX, BC_NOD integer (kind=kint), dimension(:), allocatable :: ZmaxCEL -- WORK integer (kind=kint), dimension(:,:), allocatable :: IWKX real(kind=kreal), dimension(:,:), allocatable :: FCV end module STRUCT
65 /15 65 module PCG module PCG integer, parameter :: N2= 256 integer :: NUmax, NLmax, NCOLORtot, NCOLORk, NU, NL real(kind=8) :: EPSICCG real(kind=8), dimension(: ), allocatable :: D, PHI, BFORCE real(kind=8), dimension(:,:), allocatable :: AL, AU integer, dimension(:), allocatable :: INL, INU, COLORindex integer, dimension(:), allocatable :: OLDtoNEW, NEWtoOLD integer, dimension(:,:), allocatable :: IAL, IAU end module PCG 扱う行列 : 疎行列 ( 自分の周辺のみと接続 ) 非ゼロ成分のみを記憶する 上下三角成分を別々に記憶 L U
66 /15 66 module PCG module PCG integer, parameter :: N2= 256 integer :: NUmax, NLmax, NCOLORtot, NCOLORk, NU, NL real(kind=8) :: EPSICCG real(kind=8), dimension(: ), allocatable :: D, PHI, BFORCE real(kind=8), dimension(:,:), allocatable :: AL, AU integer, dimension(:), allocatable :: INL, INU, COLORindex integer, dimension(:), allocatable :: OLDtoNEW, NEWtoOLD integer, dimension(:,:), allocatable :: IAL, IAU end module PCG 下三角成分 ( 列番号 ): 非対角成分で自分より要素番号が小さい IAL(icou,i) < i 上三角成分 ( 列番号 ): 非対角成分で自分より要素番号が大きい IAU(icou,i) > i INL(ICELTOT) 下三角成分の数 IAL(NL,ICELTOT) 下三角成分 ( 列番号 ) INU(ICELTOT) 上三角成分の数 IAU(NU,ICELTOT) 上三角成分 ( 列番号 ) NU,NL 上下三角成分の最大数 ( ここでは6) NUmax,NLmax 未使用 U NCOLORtot COLORindex(0:NCOLORtot) OLDtoNEW, NEWtoOLD 色数, レベル数各色 ( レベル ) に含まれる要素数のインデックス (COLORindex(icol)-COLORindex(icol-1)) Coloring 前後の要素番号対照表 L
67 /15 67 module PCG module PCG integer, parameter :: N2= 256 integer :: NUmax, NLmax, NCOLORtot, NCOLORk, NU, NL real(kind=8) :: EPSICCG real(kind=8), dimension(: ), allocatable :: D, PHI, BFORCE real(kind=8), dimension(:,:), allocatable :: AL, AU integer, dimension(:), allocatable :: INL, INU, COLORindex integer, dimension(:), allocatable :: OLDtoNEW, NEWtoOLD integer, dimension(:,:), allocatable :: IAL, IAU 下三角成分 ( 列番号 ): IAL(icou,i) < i その個数が INL(i) 上三角成分 ( 列番号 ): IAU(icou,i) > i その個数が INU(i) end module PCG INL(ICELTOT) 下三角成分の数 IAL(NL,ICELTOT) 下三角成分 ( 列番号 ) INU(ICELTOT) 上三角成分の数 IAU(NU,ICELTOT) 上三角成分 ( 列番号 ) NU,NL 上下三角成分の最大数 ( ここでは6) NUmax,NLmax 未使用 U NCOLORtot COLORindex(0:NCOLORtot) OLDtoNEW, NEWtoOLD 色数, レベル数各色 ( レベル ) に含まれる要素数のインデックス (COLORindex(icol)-COLORindex(icol-1)) Coloring 前後の要素番号対照表 L
68 /15 入力 =3: 実際は5 色 (multicolor) 68 color.logに行列関連情報出力 ### INITIAL connectivity I= 1 INL(i)= 0 INU(i)= 2 IAL: IAU: 2 5 I= 2 INL(i)= 1 INU(i)= 2 IAL: 1 IAU: 3 6 I= 3 INL(i)= 1 INU(i)= 2 IAL: 2 IAU: 4 7 I= 4 INL(i)= 1 INU(i)= 1 IAL: 3 IAU: 8 I= 5 INL(i)= 1 INU(i)= 2 IAL: 1 IAU: 6 9 I= 6 INL(i)= 2 INU(i)= 2 IAL: 2 5 IAU: 7 10 I= 7 INL(i)= 2 INU(i)= 2 IAL: 3 6 IAU: 8 11 I= 8 INL(i)= 2 INU(i)= 1 IAL: 4 7 IAU: 12 I= 9 INL(i)= 1 INU(i)= 2 IAL: 5 IAU: I= 10 INL(i)= 2 INU(i)= 2 IAL: 6 9 IAU: I= 11 INL(i)= 2 INU(i)= 2 IAL: 7 10 IAU: I= 12 INL(i)= 2 INU(i)= 1 IAL: 8 11 IAU: 16 I= 13 INL(i)= 1 INU(i)= 1 IAL: 9 IAU: 14 I= 14 INL(i)= 2 INU(i)= 1 IAL: IAU: 15 I= 15 INL(i)= 2 INU(i)= 1 IAL: IAU: 16 I= 16 INL(i)= 2 INU(i)= 0 IAL: IAU: COLOR number 5 #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color 5
69 /15 入力 =3: 実際は5 色 (multicolor) 69 color.logに行列関連情報出力 ### FINAL connectivity I= 1 INL(i)= 0 INU(i)= 2 IAL: IAU: 6 8 I= 2 INL(i)= 0 INU(i)= 3 IAL: IAU: I= 3 INL(i)= 0 INU(i)= 4 IAL: IAU: I= 4 INL(i)= 0 INU(i)= 3 IAL: IAU: I= 5 INL(i)= 0 INU(i)= 3 IAL: IAU: I= 6 INL(i)= 3 INU(i)= 0 IAL: IAU: I= 7 INL(i)= 2 INU(i)= 0 IAL: 2 4 IAU: I= 8 INL(i)= 3 INU(i)= 0 IAL: IAU: I= 9 INL(i)= 3 INU(i)= 1 IAL: IAU: 11 I= 10 INL(i)= 2 INU(i)= 2 IAL: 3 5 IAU: I= 11 INL(i)= 2 INU(i)= 2 IAL: 9 10 IAU: I= 12 INL(i)= 1 INU(i)= 1 IAL: 5 IAU: 15 I= 13 INL(i)= 0 INU(i)= 2 IAL: IAU: I= 14 INL(i)= 3 INU(i)= 0 IAL: IAU: I= 15 INL(i)= 2 INU(i)= 1 IAL: IAU: 16 I= 16 INL(i)= 3 INU(i)= 0 IAL: IAU:
70 /15 70 program MAIN use STRUCT use PCG implicit REAL*8 (A-H,O-Z) call POINTER_INIT call POI_GEN call OUTUCD プログラムの構成 open (21, file='color.log', status='unknown') write (21,'(//,a,i8,/)') 'COLOR number', NCOLORtot do ic= 1, NCOLORtot do i= COLORindex(ic-1)+1, COLORindex(ic) write (21,'(3(a,i8))') ' #new', i, ' #old', NEWtoOLD(i), & & ' color', ic close (21) stop end
71 /15 71 pointer_init(1/2) *** *** POINTER_INIT *** subroutine POINTER_INIT use STRUCT use PCG implicit REAL*8 (A-H,O-Z) character*9 fname open (21, file= mesh.dat, status='unknown') read (21,'(10i10)') NX, NY, NZ read (21,'(10i10)') ICELTOT mesh.dat を読み込む allocate (NEIBcell(ICELTOT,6), XYZ(ICELTOT,3)) do i= 1, ICELTOT read (21,'(10i10)') ii, (NEIBcell(i,k), k= 1, 6), & & (XYZ (i,j), j= 1, 3) close (21) NXP1= NX + 1 NYP1= NY + 1 NZP1= NZ + 1 IBNODTOT= NXP1 * NYP1 N = NXP1 * NYP1 * NZP1 z y return end x
72 /15 72 pointer_init(2/2) *** *** POINTER_INIT *** subroutine POINTER_INIT use STRUCT use PCG implicit REAL*8 (A-H,O-Z) character*9 fname open (21, file= mesh.dat, status='unknown') read (21,'(10i10)') NX, NY, NZ read (21,'(10i10)') ICELTOT allocate (NEIBcell(ICELTOT,6), XYZ(ICELTOT,3)) do i= 1, ICELTOT read (21,'(10i10)') ii, (NEIBcell(i,k), k= 1, 6), & & (XYZ (i,j), j= 1, 3) close (21) NXP1= NX + 1 NYP1= NY + 1 NZP1= NZ + 1 NXP1,NYP1,NZP1 などは UCD ファイル出力に必要 IBNODTOT= NXP1 * NYP1 N = NXP1 * NYP1 * NZP1 return end
73 /15 73 program MAIN use STRUCT use PCG implicit REAL*8 (A-H,O-Z) call POINTER_INIT call POI_GEN call OUTUCD プログラムの構成 open (21, file='color.log', status='unknown') write (21,'(//,a,i8,/)') 'COLOR number', NCOLORtot do ic= 1, NCOLORtot do i= COLORindex(ic-1)+1, COLORindex(ic) write (21,'(3(a,i8))') ' #new', i, ' #old', NEWtoOLD(i), & & ' color', ic close (21) stop end
74 /15 74 poi_gen(1/4) subroutine POI_GEN use STRUCT use PCG 配列の宣言 implicit REAL*8 (A-H,O-Z) -- INIT. nn = ICELTOT NU= 6 NL= 6 allocate (INL(nn), INU(nn), IAL(NL,nn), IAU(NU,nn)) INL= 0 INU= 0 IAL= 0 IAU= 0
75 / CONNECTIVITY do icel= 1, ICELTOT icn1= NEIBcell(icel,1) icn2= NEIBcell(icel,2) icn3= NEIBcell(icel,3) icn4= NEIBcell(icel,4) icn5= NEIBcell(icel,5) icn6= NEIBcell(icel,6) icoug= 0 if (icn5.ne.0.and.icn5.le.iceltot) then icou= INL(icel) + 1 IAL(icou,icel)= icn5 INL( icel)= icou if (icn3.ne.0.and.icn3.le.iceltot) then icou= INL(icel) + 1 IAL(icou,icel)= icn3 INL( icel)= icou if (icn1.ne.0.and.icn1.le.iceltot) then icou= INL(icel) + 1 IAL(icou,icel)= icn1 INL( icel)= icou NEIBcell(icel,1) poi_gen(2/4) NEIBcell(icel,6) NEIBcell(icel,3) NEIBcell(icel,5) NEIBcell(icel,4) 下三角成分 NEIBcell(icel,5)= icel NX*NY NEIBcell(icel,3)= icel NX NEIBcell(icel,1)= icel 1 NEIBcell(icel,2)
76 / CONNECTIVITY do icel= 1, ICELTOT icn1= NEIBcell(icel,1) icn2= NEIBcell(icel,2) icn3= NEIBcell(icel,3) icn4= NEIBcell(icel,4) icn5= NEIBcell(icel,5) icn6= NEIBcell(icel,6) poi_gen(3/4) NEIBcell(icel,6) NEIBcell(icel,4) if (icn2.ne.0.and.icn2.le.iceltot) then icou= INU(icel) + 1 IAU(icou,icel)= icn2 INU( icel)= icou NEIBcell(icel,1) NEIBcell(icel,3) NEIBcell(icel,2) if (icn4.ne.0.and.icn4.le.iceltot) then icou= INU(icel) + 1 IAU(icou,icel)= icn4 INU( icel)= icou if (icn6.ne.0.and.icn6.le.iceltot) then icou= INU(icel) + 1 IAU(icou,icel)= icn6 INU( icel)= icou NEIBcell(icel,5) 上三角成分 NEIBcell(icel,2)= icel + 1 NEIBcell(icel,4)= icel + NX NEIBcell(icel,6)= icel + NX*NY
77 /15 77 poi_gen(4/4) MULTICOLORING continue write (*,'(//a,i8,a)') 'You have', ICELTOT, ' elements.' write (*,'( a )') 'How many colors do you need?' write (*,'( a )') ' #COLOR must be more than 2 and' write (*,'( a,i8 )') ' #COLOR must not be more than', ICELTOT write (*,'( a )') ' if #COLOR=0 : CM ordering' write (*,'( a )') ' if #COLOR<0 : RCM ordering' write (*,'( a )') '=>' read (*,*) NCOLORtot if (NCOLORtot.eq.1.or.NCOLORtot.gt.ICELTOT) goto 111 allocate (OLDtoNEW(ICELTOT), NEWtoOLD(ICELTOT)) allocate (COLORindex(0:ICELTOT)) 色数を読み込む if (NCOLORtot.gt.0) then call MC (ICELTOT, NL, NU, INL, IAL, INU, IAU, & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) if (NCOLORtot.eq.0) then call CM (ICELTOT, NL, NU, INL, IAL, INU, IAU, & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) if (NCOLORtot.lt.0) then call RCM (ICELTOT, NL, NU, INL, IAL, INU, IAU, & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) & & & write (*,'(/a, i8)') '# TOTAL COLOR number', NCOLORtot
78 /15 78 poi_gen(4/4) MULTICOLORING continue write (*,'(//a,i8,a)') 'You have', ICELTOT, ' elements.' write (*,'( a )') 'How many colors do you need?' write (*,'( a )') ' #COLOR must be more than 2 and' write (*,'( a,i8 )') ' #COLOR must not be more than', ICELTOT write (*,'( a )') ' if #COLOR=0 : CM ordering' write (*,'( a )') ' if #COLOR<0 : RCM ordering' write (*,'( a )') '=>' read (*,*) NCOLORtot if (NCOLORtot.eq.1.or.NCOLORtot.gt.ICELTOT) goto 111 allocate (OLDtoNEW(ICELTOT), NEWtoOLD(ICELTOT)) allocate (COLORindex(0:ICELTOT)) 配列宣言を実施する if (NCOLORtot.gt.0) then call MC (ICELTOT, NL, NU, INL, IAL, INU, IAU, & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) if (NCOLORtot.eq.0) then call CM (ICELTOT, NL, NU, INL, IAL, INU, IAU, & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) if (NCOLORtot.lt.0) then call RCM (ICELTOT, NL, NU, INL, IAL, INU, IAU, & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) & & & write (*,'(/a, i8)') '# TOTAL COLOR number', NCOLORtot
79 /15 79 poi_gen(4/4) MULTICOLORING if (NCOLORtot.gt.0) then call MC (ICELTOT, NL, NU, INL, IAL, INU, IAU, & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) if (NCOLORtot.eq.0) then call CM (ICELTOT, NL, NU, INL, IAL, INU, IAU, & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) if (NCOLORtot.lt.0) then call RCM (ICELTOT, NL, NU, INL, IAL, INU, IAU, & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) & & & write (*,'(/a, i8)') '# TOTAL COLOR number', NCOLORtot INL, INU, IAL, IAU 再番号付け後の情報が入る OLDtoNEW, NEWtoOLD 新旧要素番号対象表 NCOLORtot 色数 ( 入力値と同じかそれより大きくなる ) COLORindex(0:NCOLORtot) COLORindex(ic-1)+1からCOLORindex(ic) までの 要素 ( 再番号付け後 ) が ic 色になる 同じ色の要素は互いに独立 : 並列計算可能
80 /15 80 COLORindex COLORindex(0:NCOLORtot) COLORindex(ic-1)+1 から COLORindex(ic) までの要素 ( 再番号付け後 ) が ic 色になる 同じ色の要素は互いに独立 : 並列計算可能 do ic= 1, NCOLORtot do i= COLORindex(ic-1)+1, COLORindex(ic) write (21,*) i, NEWtoOLD(i), ic COLOR number 5 #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color 5
81 /15 81 *** *** MC *** Multicolor Ordering Method mc(1/8) subroutine MC (N, NL, NU, INL, IAL, INU, IAU, & & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) implicit REAL*8(A-H,O-Z) integer, dimension(n) :: INL, INU, NEWtoOLD, OLDtoNEW integer, dimension(0:n) :: COLORindex integer, dimension(nl,n):: IAL integer, dimension(nu,n):: IAU integer, dimension(:), allocatable :: IW, INLw, INUw integer, dimension(:,:), allocatable :: IALw, IAUw
82 / INIT allocate (IW(N)) IW= 0 NCOLORk = NCOLORtot do i= 1, N NEWtoOLD (i)= i OLDtoNEW (i)= i INmin= N NODmin= 0 do i= 1, N icon= INL(i) + INU(i) if (icon.lt.inmin) then INmin= icon NODmin= i mc(2/8) 作業配列 IW に 0 を入れる IW には各要素の色番号が入る 接続要素数 ( 次数 ) が最小の要素を探索 NODmin OLDtoNEW(NODmin)= 1 NEWtoOLD( 1)= NODmin IW = 0 IW(NODmin)= 1 ITEMcou= N/NCOLORk
83 / INIT allocate (IW(N)) IW= 0 mc(2/8) NCOLORk = NCOLORtot do i= 1, N NEWtoOLD (i)= i OLDtoNEW (i)= i INmin= N NODmin= 0 do i= 1, N icon= INL(i) + INU(i) if (icon.lt.inmin) then INmin= icon NODmin= i OLDtoNEW(NODmin)= 1 NEWtoOLD( 1)= NODmin IW = 0 IW(NODmin)= 1 ITEMcou= N/NCOLORk 接続要素数が最小の要素をオーダリング後の 1 番とする 対照表を更新 作業配列 IW(1) に 1( 色番号 ) を入れる
84 / INIT allocate (IW(N)) IW= 0 mc(2/8) NCOLORk = NCOLORtot do i= 1, N NEWtoOLD (i)= i OLDtoNEW (i)= i INmin= N NODmin= 0 do i= 1, N icon= INL(i) + INU(i) if (icon.lt.inmin) then INmin= icon NODmin= i OLDtoNEW(NODmin)= 1 NEWtoOLD( 1)= NODmin IW = 0 IW(NODmin)= 1 ITEMcou= N/NCOLORk 各色に含まれる要素数の目安
85 /15 85 入力 =3: 実際は 5 色 (multicolor) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color /3=5 = ITEMcou 最終的に 5 色必要であった
86 / MULTIcoloring icou = 1 icouk= 1 do icol= 1, N NCOLORk= icol do i= 1, N if (IW(i).le.0) IW(i)= 0 mc(3/8) カウンタ初期化 icou : 全体のカウンタ icouk : 色内のカウンタ do i= 1, N -- already COLORED if (IW(i).eq.icol) then do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= not COLORED if (IW(i).eq.0) then icou = icou + 1 icouk= icouk + 1 IW(i)= icol do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= -1
87 / MULTIcoloring icou = 1 icouk= 1 do icol= 1, N NCOLORk= icol do i= 1, N if (IW(i).le.0) IW(i)= 0 mc(3/5) 色数に関するループ do i= 1, N -- already COLORED if (IW(i).eq.icol) then do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= not COLORED if (IW(i).eq.0) then icou = icou + 1 icouk= icouk + 1 IW(i)= icol do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= -1
88 / MULTIcoloring icou = 1 icouk= 1 do icol= 1, N NCOLORk= icol do i= 1, N if (IW(i).le.0) IW(i)= 0 do i= 1, N -- already COLORED if (IW(i).eq.icol) then do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= not COLORED if (IW(i).eq.0) then icou = icou + 1 icouk= icouk + 1 IW(i)= icol do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= -1 mc(3/8) 現在の色数を NCOLORk とする 色づけされていない要素の IW の値を 0 とする
89 / MULTIcoloring icou = 1 icouk= 1 do icol= 1, N NCOLORk= icol do i= 1, N if (IW(i).le.0) IW(i)= 0 do i= 1, N -- already COLORED if (IW(i).eq.icol) then do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= not COLORED if (IW(i).eq.0) then icou = icou + 1 icouk= icouk + 1 IW(i)= icol do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= -1 mc(3/8) 全要素に関するループ すでに現在の色に色づけされている場合は, 隣接する要素の IW の値を -1 とする ( 実際にこの部分を通る可能性は最初の一回のみであるが, 念のため ) すでに 現在の色 に色づけされている要素の隣接要素は 現在の色 に入る可能性が無いため除外
90 / MULTIcoloring icou = 1 icouk= 1 mc(3/8) do icol= 1, N NCOLORk= icol do i= 1, N if (IW(i).le.0) IW(i)= 0 do i= 1, N -- already COLORED if (IW(i).eq.icol) then do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= not COLORED if (IW(i).eq.0) then icou = icou + 1 icouk= icouk + 1 IW(i)= icol do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= -1 IW(i)=0 の場合, カウンタを 1 つずつ増やし, 自分の色を icol とする (IW(i)= icol) 隣接する要素の IW の値を -1 とする
91 /15 91 do icol= 1, N NCOLORk= icol do i= 1, N if (IW(i).le.0) IW(i)= 0 do i= 1, N -- already COLORED if (IW(i).eq.icol) then do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= not COLORED if (IW(i).eq.0) then icou = icou + 1 icouk= icouk + 1 IW(i)= icol do k= 1, INL(i) ik= IAL(k,i) if (IW(ik).le.0) IW(ik)= -1 do k= 1, INU(i) ik= IAU(k,i) if (IW(ik).le.0) IW(ik)= -1 if (icou.eq.n) goto 200 if (icouk.eq.itemcou) goto 100 mc(4/8) icou : 全体のカウンタ icouk : 色内のカウンタ 要素数のカウンタ (icou) が N(ICELTOT) を超えたらループを抜ける ( 全要素の色付け完了 ) 色内のカウンタ (icouk) が ITEMcou を超えたら icouk=0 として次の色へ移る icouk < ITEMcou でも i が N に到達したら ( 独立な要素がもうないので ) 次の色へ移る 100 continue icouk= continue
92 /15 92 入力 =3: 実際は 5 色 (multicolor) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color /3=5 5 個ずつ独立な要素を元の番号順に選択
93 /15 93 入力 =3: 実際は 5 色 (multicolor) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color /3=5 5 個ずつ独立な要素を元の番号順に選択
94 /15 94 入力 =3: 実際は 5 色 (multicolor) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color /3= 独立な要素が無くなったら次の色へ
95 /15 95 入力 =3: 実際は 5 色 (multicolor) #new 1 #old 1 color 1 #new 2 #old 3 color 1 #new 3 #old 6 color 1 #new 4 #old 8 color 1 #new 5 #old 9 color 1 #new 6 #old 2 color 2 #new 7 #old 4 color 2 #new 8 #old 5 color 2 #new 9 #old 7 color 2 #new 10 #old 10 color 2 #new 11 #old 11 color 3 #new 12 #old 13 color 3 #new 13 #old 16 color 3 #new 14 #old 12 color 4 #new 15 #old 14 color 4 #new 16 #old 15 color /3= 独立な要素が無くなったら次の色へ
96 / FINAL COLORING NCOLORtot= NCOLORk COLORindex= 0 icoug= 0 do ic= 1, NCOLORtot icou= 0 do i= 1, N if (IW(i).eq.ic) then icou = icou + 1 icoug= icoug + 1 NEWtoOLD(icoug)= i OLDtoNEW(i )= icoug COLORindex(ic)= icou mc(5/8) 色づけを終了した時点での色数 NCOLORk を最終的な色数とする ユーザーが最初に設定した色数と同じかそれより多くなっている do ic= 1, NCOLORtot COLORindex(ic)= COLORindex(ic-1) + COLORindex(ic)
97 / FINAL COLORING NCOLORtot= NCOLORk COLORindex= 0 icoug= 0 do ic= 1, NCOLORtot icou= 0 do i= 1, N if (IW(i).eq.ic) then icou = icou + 1 icoug= icoug + 1 NEWtoOLD(icoug)= i OLDtoNEW(i )= icoug COLORindex(ic)= icou mc(5/8) 各要素の色に従って, 色番号の少ない方から, 要素の再番号付けを行なう OLDtoNEW(old_ID)= new_id NEWtoOLD(new_ID)= old_id この時点では COLORindex には各色の要素数が入っている do ic= 1, NCOLORtot COLORindex(ic)= COLORindex(ic-1) + COLORindex(ic)
98 / FINAL COLORING NCOLORtot= NCOLORk COLORindex= 0 icoug= 0 do ic= 1, NCOLORtot icou= 0 do i= 1, N if (IW(i).eq.ic) then icou = icou + 1 icoug= icoug + 1 NEWtoOLD(icoug)= i OLDtoNEW(i )= icoug COLORindex(ic)= icou do ic= 1, NCOLORtot COLORindex(ic)= COLORindex(ic-1) + COLORindex(ic) mc(6/8) COLORindex を一次元インデックスに置き換える
99 / MATRIX transfer allocate (INLw(N), INUw(N), IALw(NL,N), IAUw(NU,N)) do j= 1, NL do i= 1, N IW(i) = IAL(j,NEWtoOLD(i)) do i= 1, N IAL(j,i) = IW(i) do j= 1, NU do i= 1, N IW(i) = IAU(j,NEWtoOLD(i)) do i= 1, N IAU(j,i) = IW(i) mc(6/8) ワーク配列の定義 INLw(N) INUw(N) IALw(NL,N) IAUw(NU,N) 上下三角成分を, 新しい番号付けに従って入れ替える 上下三角成分そのものの番号はそのまま
100 / do i= 1, N INLw(i) = INL(NEWtoOLD(i)) do i= 1, N INUw(i) = INU(NEWtoOLD(i)) do j= 1, NL do i= 1, N if (IAL(j,i).eq.0) then IALw(j,i) = 0 else IALw(j,i) = OLDtoNEW(IAL(j,i)) do j= 1, NU do i= 1, N if ( IAU(j,i).eq.0) then IAUw(j,i) = 0 else IAUw(j,i) = OLDtoNEW(IAU(j,i)) mc(7/8) 上下三角成分の数を, 新しい番号付けに従って入れ替える INL を並び替えて IW に格納し, 更に INLw に格納する INU を並び替えて IW に格納し, 更に INUw に格納する
101 / do i= 1, N INLw(i) = INL(NEWtoOLD(i)) mc(7/8) do i= 1, N INUw(i) = INU(NEWtoOLD(i)) do j= 1, NL do i= 1, N if (IAL(j,i).eq.0) then IALw(j,i) = 0 else IALw(j,i) = OLDtoNEW(IAL(j,i)) do j= 1, NU do i= 1, N if ( IAU(j,i).eq.0) then IAUw(j,i) = 0 else IAUw(j,i) = OLDtoNEW(IAU(j,i)) 上下三角成分を, 新しい番号付けに従って新しい番号に付け替える IALw,IAUw に格納する
102 / INL= 0 INU= 0 IAL= 0 IAU= 0 do i= 1, N jl= 0 ju= 0 do j= 1, INLw(i) if (IALw(j,i).gt.i) then ju= ju + 1 IAU(jU,i)= IALw(j,i) else jl= jl + 1 IAL(jL,i)= IALw(j,i) do j= 1, INUw(i) if (IAUw(j.i).gt.i) then ju= ju + 1 IAU(jU,i)= IAUw(j,i) else jl= jl + 1 IAL(jL,i)= IAUw(j,i) INL(i)= jl INU(i)= ju deallocate (IW, INLw, INUw, IALw, IAUw) return end mc(8/8) もともとの下三角成分にたいする処理 do i= 1, N jl= 0 ju= 0 do j= 1, INLw(i) if (IALw(j,i).gt.i) then ju= ju + 1 IAU(jU,i)= IALw(j,i) else jl= jl + 1 IAL(jL,i)= IALw(j,i) 新しく番号がついた IALw(j,i) が i より大きいか小さいかによって上三角成分と下三角成分に振り分ける
103 / この操作が必要な理由 Original Color INL( 7)= 2 IAL(1,7)= 3, IAL(2,7)= 6 INU( 7)= 2 IAU(1,7)= 8, IAU(2,7)=11 INL( 9)= 3 IAL(1,9)= 2, IAL(2,9)= 3 IAL(3,9)= 4 INU( 9)= 1 IAU(1,9)=11 再番号付けによって隣接要素との大小関係も変わってしまうため
104 / INL= 0 INU= 0 IAL= 0 IAU= 0 do i= 1, N jl= 0 ju= 0 do j= 1, INLw(i) if (IALw(j,i).gt.i) then ju= ju + 1 IAU(jU,i)= IALw(j,i) else jl= jl + 1 IAL(jL,i)= IALw(j,i) do j= 1, INUw(i) if (IAUw(j.i).gt.i) then ju= ju + 1 IAU(jU,i)= IAUw(j,i) else jl= jl + 1 IAL(jL,i)= IAUw(j,i) mc(8/8) もともとの上三角成分にたいする処理 INL(i)= jl INU(i)= ju deallocate (IW, INLw, INUw, IALw, IAUw) return end
105 / INL= 0 INU= 0 IAL= 0 IAU= 0 mc(8/8) do i= 1, N jl= 0 ju= 0 do j= 1, INLw(i) if (IALw(j,i).gt.i) then ju= ju + 1 IAU(jU,i)= IALw(j,i) else jl= jl + 1 IAL(jL,i)= IALw(j,i) do j= 1, INUw(i) if (IAUw(j.i).gt.i) then ju= ju + 1 IAU(jU,i)= IAUw(j,i) else jl= jl + 1 IAL(jL,i)= IAUw(j,i) 上下三角成分の数 INL(i)= jl INU(i)= ju deallocate (IW, INLw, INUw, IALw, IAUw) return end
106 / CM 法の手順 手順 3: 繰り返し, 再番号付け レベル (k) に属する条件を満たす要素が無くなったら,k=k+1 として, 手順 2 を繰り返し, 全要素の レベル が決定したら終了 レベル の若い順に要素番号をふり直す
107 / RCM(Reverse CM) まず CM の手順を実行 手順 1: 次数 (degree) の計算 手順 2: レベル (k(k 2)) の要素の選択 手順 3: 繰り返し, 再番号付け 手順 4: 再々番号付け CM の番号付けを更に逆順にふり直す Fill-in が CM の場合より少なくなる
108 / *** *** CM *** subroutine CM (N, NL, NU, INL, IAL, INU, IAU, & NCOLORtot, COLORindex, NEWtoOLD, OLDtoNEW) cm(1/5) implicit REAL*8(A-H,O-Z) integer, dimension(n) :: INL, INU, NEWtoOLD, OLDtoNEW integer, dimension(0:n) :: COLORindex integer, dimension(nl,n):: IAL integer, dimension(nu,n):: IAU integer, dimension(:,:), allocatable :: IW integer, dimension(:), allocatable :: INLw, INUw integer, dimension(:,:), allocatable :: IALw, IAUw
109 / INIT allocate (IW(N,2)) IW = 0 INmin= N NODmin= 0 do i= 1, N icon= 0 do k= 1, INL(i) icon= icon + 1 do k= 1, INU(i) icon= icon + 1 補助配列 cm(2/5) IW(i,1): ワーク配列 IW(i,2): 要素 i の所属レベル if (icon.lt.inmin) then INmin = icon NODmin= i 200 continue if (NODmin.eq.0) NODmin= 1 IW(NODmin,2)= 1 NEWtoOLD(1 )= NODmin OLDtoNEW(NODmin)= 1 icol= 1
110 / INIT allocate (IW(N,2)) IW = 0 INmin= N NODmin= 0 do i= 1, N icon= 0 do k= 1, INL(i) icon= icon + 1 do k= 1, INU(i) icon= icon + 1 cm(2/5) 接続要素数 ( 次数 ) が最小の要素を探索 NODmin if (icon.lt.inmin) then INmin = icon NODmin= i 200 continue if (NODmin.eq.0) NODmin= 1 IW(NODmin,2)= 1 NEWtoOLD(1 )= NODmin OLDtoNEW(NODmin)= 1 icol= 1
111 / INIT allocate (IW(N,2)) cm(2/5) IW = 0 INmin= N NODmin= 0 do i= 1, N icon= 0 do k= 1, INL(i) icon= icon + 1 do k= 1, INU(i) icon= icon + 1 if (icon.lt.inmin) then INmin = icon NODmin= i 200 continue if (NODmin.eq.0) NODmin= 1 IW(NODmin,2)= 1 NEWtoOLD(1 )= NODmin OLDtoNEW(NODmin)= 1 icol= 1 NODmin の所属レベル IW(NODmin,2 を 1 とする NODmin を新しい番号付けにおける 1 番の要素とする
112 / COLORING icoug= 1 do icol= 2, N icou = 0 do i= 1, N if (IW(i,2).eq.icol-1) then do k= 1, INL(i) in= IAL(k,i) if (IW(in,2).eq.0) then IW(in,2)= -icol icou = icou + 1 IW(icou,1)= in do k= 1, INU(i) in= IAU(k,i) if (IW(in,2).eq.0) then IW(in,2)= -icol icou = icou + 1 IW(icou,1)= in cm(3/5) icoug : 全体のカウンタ icou : レベル内のカウンタ レベル に関するループ if (icou.eq.0) then do i= 1, N if (IW(i,2).eq.0) then icou= icou + 1 IW(i,2)= -icol IW(icou,1)= i goto continue
113 / COLORING icoug= 1 do icol= 2, N icou = 0 do i= 1, N if (IW(i,2).eq.icol-1) then do k= 1, INL(i) in= IAL(k,i) if (IW(in,2).eq.0) then IW(in,2)= -icol icou = icou + 1 IW(icou,1)= in do k= 1, INU(i) in= IAU(k,i) if (IW(in,2).eq.0) then IW(in,2)= -icol icou = icou + 1 IW(icou,1)= in if (icou.eq.0) then do i= 1, N if (IW(i,2).eq.0) then icou= icou + 1 IW(i,2)= -icol IW(icou,1)= i goto continue cm(3/5) icoug : 全体のカウンタ icou : レベル内のカウンタ レベル 内での, 各要素に関するループ IW(i,2)=icol-1 ( 所属レベル番号 :icol-1) である要素 i に接続しており, かつ, 所属レベルが決定していない要素 in に関して, 所属レベル番号 icol の要素の候補として,IW(in,2)= -icol とする レベル内カウンタ icou=icou+1 とする また, 見つかった 順番に : IW(ic,1)= in (ic= 1~icou) とする
114 / どういうことかというと icoug : 全体のカウンタ icou : レベル内のカウンタ icol=4 IW(i,2)= icol-1=3: i=3,6,9 レベル 内での, 各要素に関するループ IW(i,2)=icol-1 ( 所属レベル番号 :icol-1) である要素 i に接続しており, かつ, 所属レベルが決定していない要素 in に関して, 所属レベル番号 icol の要素の候補として,IW(in,2)= -icol とする レベル内カウンタ icou=icou+1 とする また, 見つかった 順番に : IW(ic,1)= in (ic= 1~icou) とする
115 / どういうことかというと icoug : 全体のカウンタ icou : レベル内のカウンタ icol=4 IW(i,2)= icol-1=3: i=3,6,9 IW( 4,2)= -4 IW( 7,2)= -4 IW(10,2)= -4 IW(13,2)= -4 IW(1,1)= 4 IW(2,1)= 7 IW(3,1)= 10 IW(4,1)= 13 レベル 内での, 各要素に関するループ IW(i,2)=icol-1 ( 所属レベル番号 :icol-1) である要素 i に接続しており, かつ, 所属レベルが決定していない要素 in に関して, 所属レベル番号 icol の要素の候補として,IW(in,2)= -icol とする レベル内カウンタ icou=icou+1 とする また, 見つかった 順番に : IW(ic,1)= in (ic= 1~icou) とする
116 / COLORING icoug= 1 do icol= 2, N icou = 0 do i= 1, N if (IW(i,2).eq.icol-1) then do k= 1, INL(i) in= IAL(k,i) if (IW(in,2).eq.0) then IW(in,2)= -icol icou = icou + 1 IW(icou,1)= in do k= 1, INU(i) in= IAU(k,i) if (IW(in,2).eq.0) then IW(in,2)= -icol icou = icou + 1 IW(icou,1)= in if (icou.eq.0) then do i= 1, N if (IW(i,2).eq.0) then icou= icou + 1 IW(i,2)= -icol IW(icou,1)= i goto continue cm(3/5) icoug : 全体のカウンタ icou : レベル内のカウンタ レベル 内での, 各要素に関するループ もし icou=0 となったら, まだ所属レベルが決定しない要素の中で最も要素番号が小さいものを選び出す ( 通常はこのループは通らない )
117 / COLORING cm(4/5) do ic= 1, icou inc= IW(ic,1) if (IW(inC,2).ne.0) then do k= 1, INL(inC) in= IAL(k,inC) if (IW(in,2).le.0) IW(in,2)= 0 do k= 1, INU(inC) in= IAU(k,inC) if (IW(in,2).le.0) IW(in,2)= 0 do ic= 1, icou inc= IW(ic,1) if (IW(inC,2).ne.0) then icoug = icoug + 1 IW(inC,2)= icol if (icoug.eq.n) exit 所属レベル icol の候補となっている要素の番号が,IW(ic,1)(ic=1~icou) に格納されている 各要素 inc=iw(ic,1)(ic=1~icou) に隣接する要素 in のうちで, 所属レベル icol の候補となっているものがある場合, 要素 in を候補の中からはずす ( 隣接する要素同士は同じレベルには属することができない ) そのような要素に対して : IW(in,2)=0 とする
118 / どういうことかというと 例えば 1 の所属レベル =icol-1 とする 所属レベル icol の候補となっている要素の番号が,IW(ic,1)(ic=1~icou) に格納されている 各要素 inc=iw(ic,1)(ic=1~icou) に隣接する要素 in のうちで, 所属レベル icol の候補となっているものがある場合, 要素 in を候補の中からはずす ( 隣接する要素同士は同じレベルには属することができない ) そのような要素に対して : IW(in,2)=0 とする
119 / どういうことかというと 所属レベル icol の候補となる節点は 2,4,5 の 3 点, したがって : IW(2,2)= -icol IW(4,2)= -icol IW(5,2)= -icol IW(1,1)= 2 IW(2,1)= 4 IW(3,1)= 5 所属レベル icol の候補となっている要素の番号が,IW(ic,1)(ic=1~icou) に格納されている 各要素 inc=iw(ic,1)(ic=1~icou) に隣接する要素 in のうちで, 所属レベル icol の候補となっているものがある場合, 要素 in を候補の中からはずす ( 隣接する要素同士は同じレベルには属することができない ) そのような要素に対して : IW(in,2)=0 とする
120 / どういうことかというと 所属レベル 5 は 2 と隣接しているため, 2 と同じレベルに属することはできない : IW(2,2)= -icol IW(4,2)= -icol IW(5,2)= 0 所属レベル icol の候補となっている要素の番号が,IW(ic,1)(ic=1~icou) に格納されている 各要素 inc=iw(ic,1)(ic=1~icou) に隣接する要素 in のうちで, 所属レベル icol の候補となっているものがある場合, 要素 in を候補の中からはずす ( 隣接する要素同士は同じレベルには属することができない ) そのような要素に対して : IW(in,2)=0 とする
121 / COLORING do ic= 1, icou inc= IW(ic,1) if (IW(inC,2).ne.0) then do k= 1, INL(inC) in= IAL(k,inC) if (IW(in,2).le.0) IW(in,2)= 0 do k= 1, INU(inC) in= IAU(k,inC) if (IW(in,2).le.0) IW(in,2)= 0 do ic= 1, icou inc= IW(ic,1) if (IW(inC,2).ne.0) then icoug = icoug + 1 IW(inC,2)= icol if (icoug.eq.n) exit cm(4/5) icoug : 全体のカウンタ icou : レベル内のカウンタ IW(inC,2)=-icol の要素 inc が最終的にレベル番号 icol に所属する このような要素に対して : IW(inC,2)= icol とする レベル番号が決定した要素数のカウンタ icoug を 1 つ増やす
122 / どういうことかというと 所属レベル 5 は 2 と隣接しているため, 2 と同じレベルに属することはできない : IW(inC,2)=-icol の要素 inc が最終的にレベル番号 icol に所属する このような要素に対して : IW(inC,2)= icol とする レベル番号が決定した要素数のカウンタ icoug を 1 つ増やす IW(2,2)= -icol IW(4,2)= -icol IW(5,2)= 0 2 と 4 のレベル番号を icol とする : IW(2,2)= icol IW(4,2)= icol
123 / COLORING do ic= 1, icou inc= IW(ic,1) if (IW(inC,2).ne.0) then do k= 1, INL(inC) in= IAL(k,inC) if (IW(in,2).le.0) IW(in,2)= 0 do k= 1, INU(inC) in= IAU(k,inC) if (IW(in,2).le.0) IW(in,2)= 0 cm(4/5) icoug : 全体のカウンタ icou : レベル内のカウンタ do ic= 1, icou inc= IW(ic,1) if (IW(inC,2).ne.0) then icoug = icoug + 1 IW(inC,2)= icol if (icoug.eq.n) exit icoug=n となっていたら, 全要素の所属レベルが決まったことになるので, 終了 そうでない場合は, レベル数を一つ増やして, 探索を継続する
124 / FINAL COLORING continue NCOLORtot= icol icoug= 0 do ic= 1, NCOLORtot icou= 0 do i= 1, N if (IW(i,2).eq.ic) then icou = icou + 1 icoug= icoug + 1 NEWtoOLD(icoug)= i OLDtoNEW(i )= icoug COLORindex(ic)= icou COLORindex(0)= 0 do ic= 1, NCOLORtot COLORindex(ic)= COLORindex(ic-1) + COLORindex(ic) cm(5/5) icoug=n となった時点でのレベル数 icol を総レベル数 NCOLORtot とする 各要素所属レベルに従って, レベル番号の少ない方から, 要素の再番号付けを行なう OLDtoNEW(old_ID)= new_id NEWtoOLD(new_ID)= old_id この時点では COLORindex には各色の要素数が入っている MATRIX transfer return end
Microsoft PowerPoint - omp-c-02.ppt [互換モード]
![Microsoft PowerPoint - omp-c-02.ppt [互換モード]](/thumbs/93/114146751.jpg "Microsoft PowerPoint - omp-c-02.ppt [互換モード]")
科学技術計算のための マルチコアプログラミング入門 C 言語編第 Ⅱ 部 : オーダリング 中島研吾 東京大学情報基盤センター 2 データ依存性の解決策は? オーダリング (Ordering) について Red-Black,Multicolor(MC) Cuthill-McKee(CM),Reverse-CM(RCM) オーダリングと収束の関係 オーダリングの実装 オーダリング付 ICCG 法の実装
OpenMP/OpenACC によるマルチコア メニィコア並列プログラミング入門 Fortran 編第 Ⅳ 部 :OpenMP による並列化 + 演習 中島研吾 東京大学情報基盤センター
OpenMP/OpenACC によるマルチコア メニィコア並列プログラミング入門 Fortran 編第 Ⅳ 部 :OpenMP による並列化 + 演習 中島研吾 東京大学情報基盤センター OMP-3 1 OpenMP 並列化 L2-sol を OpenMP によって並列化する 並列化にあたってはスレッド数を PEsmpTOT によってプログラム内で調節できる方法を適用する 基本方針 同じ 色 ( または
Microsoft PowerPoint - omp-03.ppt [互換モード]
![Microsoft PowerPoint - omp-03.ppt [互換モード]](/thumbs/81/84630076.jpg "Microsoft PowerPoint - omp-03.ppt [互換モード]")
Parallel Programming for Multicore Processors using OpenMP Part III: Parallel Version + Exercise Kengo Nakajima Information Technology enter Programming for Parallel omputing (616-2057) Seminar on Advanced
情報処理概論（第二日目）
情報処理概論 工学部物質科学工学科応用化学コース機能物質化学クラス 第 8 回 2005 年 6 月 9 日 前回の演習の解答例 多項式の計算 ( 前半 ): program poly implicit none integer, parameter :: number = 5 real(8), dimension(0:number) :: a real(8) :: x, total integer
memo
計数工学プログラミング演習 ( 第 4 回 ) 2016/05/10 DEPARTMENT OF MATHEMATICA INFORMATICS 1 内容 リスト 疎行列 2 連結リスト (inked ists) オブジェクトをある線形順序に並べて格納するデータ構造 単方向連結リスト (signly linked list) の要素 x キーフィールド key ポインタフィールド next x->next:
FORTRAN( と C) によるプログラミング 5 ファイル入出力 ここではファイルからデータを読みこんだり ファイルにデータを書き出したりするプログラムを作成してみます はじめに テキスト形式で書かれたデータファイルに書かれているデータを読みこんで配列に代入し 標準出力に書き出すプログラムを作り
FORTRAN( と C) によるプログラミング 5 ファイル入出力 ここではファイルからデータを読みこんだり ファイルにデータを書き出したりするプログラムを作成してみます はじめに テキスト形式で書かれたデータファイルに書かれているデータを読みこんで配列に代入し 標準出力に書き出すプログラムを作ります FORTRAN の場合 OPEN 文でファイルを開いた後 標準入力の場合と同様に READ 文でデータを読みこみます
GeoFEM開発の経験から
FrontISTR における並列計算のしくみ < 領域分割に基づく並列 FEM> メッシュ分割 領域分割 領域分割 ( パーティショニングツール ) 全体制御 解析制御 メッシュ hecmw_ctrl.dat 境界条件 材料物性 計算制御パラメータ 可視化パラメータ 領域分割ツール 逐次計算 並列計算 Front ISTR FEM の主な演算 FrontISTR における並列計算のしくみ < 領域分割に基づく並列
<4D F736F F F696E74202D D F95C097F D834F E F93FC96E5284D F96E291E85F8DE391E52E >
SX-ACE 並列プログラミング入門 (MPI) ( 演習補足資料 ) 大阪大学サイバーメディアセンター日本電気株式会社 演習問題の構成 ディレクトリ構成 MPI/ -- practice_1 演習問題 1 -- practice_2 演習問題 2 -- practice_3 演習問題 3 -- practice_4 演習問題 4 -- practice_5 演習問題 5 -- practice_6
Microsoft Word - DF-Salford解説09.doc
Digital Fortran 解説 2009/April 1. プログラム形態とデ - タ構成 最小自乗法プログラム (testlsm.for) m 組の実験データ (x i,y i ) に最も近似する直線式 (y=ax+b) を最小自乗法で決定する 入力データは組数 mと m 組の (x i,y i ) 値 出力データは直線式の係数 a,bとなる 入力データ m=4 (x i,y i ) X=1.50
情報処理Ⅰ
Java フローチャート -1- フローチャート ( 流れ図 ) プログラムの処理手順 ( アルゴリズム ) を図示したもの 記号の種類は下記のとおり 端子記号 ( 開始 終了 ) 処理記号計算, 代入等 条件の判定 条件 No ループ処理 LOOP start Yes データの入力 出力 print など 定義済み処理処理名 end サンプルグログラム ( 大文字 小文字変換 ) 大文字を入力して下さい
. (.8.). t + t m ü(t + t) + c u(t + t) + k u(t + t) = f(t + t) () m ü f. () c u k u t + t u Taylor t 3 u(t + t) = u(t) + t! u(t) + ( t)! = u(t) + t u(
3 8. (.8.)............................................................................................3.............................................4 Nermark β..........................................
フローチャートの書き方
アルゴリズム ( 算法 ) 入門 1 プログラムの作成 機械工学専攻泉聡志 http://masudahp.web.fc2.com/flowchart/index.html 参照 1 何をどのように処理させたいのか どのようなデータを入力し どのような結果を出力させるのか問題を明確にする 2 問題の内容どおりに処理させるための手順を考える ( フローチャートの作成 )~アルゴリズム( 算法 ) の作成
untitled
Fortran90 ( ) 17 12 29 1 Fortran90 Fortran90 FORTRAN77 Fortran90 1 Fortran90 module 1.1 Windows Windows UNIX Cygwin (http://www.cygwin.com) C\: Install Cygwin f77 emacs latex ps2eps dvips Fortran90 Intel
Taro-スタック（公開版）.jtd
0. 目次 1. 1. 1 配列によるの実現 1. 2 再帰的なデータ構造によるの実現 1. 3 地図情報処理 1. 4 問題 問題 1 グラフ探索問題 - 1 - 1. は データの出し入れが一カ所で行われ 操作は追加と削除ができるデータ構造をいう 出入口 追加 削除 操作 最初 111 追加 111 222 追加 111 222 333 追加 111 222 333 444 追加 111 222
科学技術計算のための マルチコアプログラミング入門第 Ⅰ 部 : 概要, 対象アプリケーション,OpenMP 中島研吾 大島聡史 林雅江 東京大学情報基盤センター
科学技術計算のための マルチコアプログラミング入門第 Ⅰ 部 : 概要, 対象アプリケーション,OpenMP 中島研吾 大島聡史 林雅江 東京大学情報基盤センター OMP- 本セミナーの背景 マイクロプロセッサのマルチコア化, メニーコア化 低消費電力, 様々なプログラミングモデル OpenMP 指示行 ( ディレクティヴ ) を挿入するだけで手軽に 並列化 ができるため, 広く使用されている 様々な解説書
始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル
![始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル](/thumbs/89/99127345.jpg "始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル")
概略設計書 作成者築山修治作成日 2012 年 10 月 1 日 概要 ( どのような入力に対して, どのような出力をするかの概要説明 ) * 木 T および質問点対の集合 P が与えられたとき, 各質問点対 p = (v,w) P の最下位共通先祖 ( すなわち木 T において点 v と w の共通の先祖 a で,a の真の子孫には v と w の共通の先祖が無いような点 ) を見出す関数である.
Microsoft PowerPoint - 03_What is OpenMP 4.0 other_Jan18
OpenMP* 4.x における拡張 OpenMP 4.0 と 4.5 の機能拡張 内容 OpenMP* 3.1 から 4.0 への拡張 OpenMP* 4.0 から 4.5 への拡張 2 追加された機能 (3.1 -> 4.0) C/C++ 配列シンタックスの拡張 SIMD と SIMD 対応関数 デバイスオフロード task 構 の依存性 taskgroup 構 cancel 句と cancellation
cp-7. 配列
cp-7. 配列 (C プログラムの書き方を, パソコン演習で学ぶシリーズ ) https://www.kkaneko.jp/cc/adp/index.html 金子邦彦 1 本日の内容 例題 1. 月の日数配列とは. 配列の宣言. 配列の添え字. 例題 2. ベクトルの内積例題 3. 合計点と平均点例題 4. 棒グラフを描く配列と繰り返し計算の関係例題 5. 行列の和 2 次元配列 2 今日の到達目標
データ構造
アルゴリズム及び実習 3 馬青 1 バブルソート 考え方 : 隣接する二つのデータを比較し データの大小関係が逆のとき 二つのデータの入れ替えを行って整列を行う方法である 2 バブルソートの手順 配列 a[0],a[1],,a[n-1] をソートする場合 ステップ 1: 配列 a[0] と a[1],a[1] と a[2],,a[n-2] と a[n-1] と となり同士を比較 ( 大小が逆であれば
データ構造
アルゴリズム及び実習 7 馬青 1 表探索 定義表探索とは 表の形で格納されているデータの中から条件に合ったデータを取り出してくる操作である 但し 表は配列 ( 連結 ) リストなどで実現できるので 以降 表 の代わりに直接 配列 や リスト などの表現を用いる場合が多い 表探索をただ 探索 と呼ぶ場合が多い 用語レコード : 表の中にある個々のデータをレコード (record) と呼ぶ フィールド
Microsoft PowerPoint - C_Programming(3).pptx
H23 年度秋学期情報スキル活用 入門 担当 : 田中基彦 ( 工学部共通教育科 ) Email: ak_tanaka@isc.chubu.ac.jp 授業のホームページ学術情報センター > 教育支援 > 情報リテラシー 授業の日程 講義内容提出課題 連絡事項を掲載 > 定期的にアクセスして確認する C 言語によるプログラミング (3) 制御文 繰り返し文 if, while, switch, for,
Microsoft PowerPoint - ad11-09.pptx
無向グラフと有向グラフ 無向グラフ G=(V, E) 頂点集合 V 頂点の対を表す枝の集合 E e=(u,v) 頂点 u, v は枝 e の端点 f c 0 a 1 e b d 有向グラフ G=(V, E) 頂点集合 V 頂点の順序対を表す枝の集合 E e=(u,v) 頂点 uは枝 eの始点頂点 vは枝 eの終点 f c 0 a 1 e b d グラフのデータ構造 グラフ G=(V, E) を表現するデータ構造
(Microsoft PowerPoint \211\211\217K3_4\201i\216R\226{_\211\272\215\342\201j.ppt [\214\335\212\267\203\202\201[\203h])
![(Microsoft PowerPoint \211\211\217K3_4\201i\216R\226{_\211\272\215\342\201j.ppt [\214\335\212\267\203\202\201[\203h])](/thumbs/101/148628642.jpg "(Microsoft PowerPoint \211\211\217K3_4\201i\216R\226{_\211\272\215\342\201j.ppt [\214\335\212\267\203\202\201[\203h])")
RIKEN AICS Summer School 演習 3 4 MPI による並列計算 2012 年 8 月 8 日 神戸大学大学院システム情報学研究科山本有作理化学研究所計算科学研究機構下坂健則 1 演習の目標 講義 6 並列アルゴリズム基礎 で学んだアルゴリズムのいくつかを,MPI を用いて並列化してみる これを通じて, 基本的な並列化手法と,MPI 通信関数の使い方を身に付ける 2 取り上げる例題と学習項目
Microsoft PowerPoint - omp-f-01.ppt [互換モード]
![Microsoft PowerPoint - omp-f-01.ppt [互換モード]](/thumbs/96/130060654.jpg "Microsoft PowerPoint - omp-f-01.ppt [互換モード]")
科学技術計算のための マルチコアプログラミング入門 Fortr 編第 Ⅰ 部 : 概要 対象アプリケーション OpeMP 中島研吾 東京大学情報基盤センター OMP- 本編の背景 マイクロプロセッサのマルチコア化 メニーコア化 低消費電力 様々なプログラミングモデル OpeMP 指示行 ディレクティヴ を挿入するだけで手軽に 並列化 ができるため 広く使用されている 様々な解説書 データ依存性 t
1F90/kouhou_hf90.dvi
Fortran90 3 33 1 2 Fortran90 FORTRAN 1956 IBM IBM704 FORTRAN(FORmula TRANslation ) 1965 FORTRAN66 1978 FORTRAN77 1991 Fortran90 Fortran90 Fortran Fortran90 6 Fortran90 77 90 90 Fortran90 [ ] Fortran90
Taro-再帰関数Ⅱ（公開版）.jtd
0. 目次 6. 2 項係数 7. 二分探索 8. 最大値探索 9. 集合 {1,2,,n} 上の部分集合生成 - 1 - 6. 2 項係数 再帰的定義 2 項係数 c(n,r) は つぎのように 定義される c(n,r) = c(n-1,r) + c(n-1,r-1) (n 2,1 r n-1) = 1 (n 0, r=0 ) = 1 (n 1, r=n ) c(n,r) 0 1 2 3 4 5
PowerPoint プレゼンテーション
計算機実習 Ⅰ FORTRAN 担当 2018.05.29 本日の課題 プログラムの基本ルールを理解し 以下が含まれるプログラムを作成する (1) 文法の基礎 ( フローチャートなど ) (2) 変数宣言 (3) 入出力 (4) 四則演算 (5) 組込関数 (6) 判定文 (7) リダイレクション PROGRAM MAIN INTEGER I, J, K REAL A, B, C CHARACTER
(Basic Theory of Information Processing) Fortran Fortan Fortan Fortan 1
(Basic Theory of Information Processing) Fortran Fortan Fortan Fortan 1 17 Fortran Formular Tranlator Lapack Fortran FORTRAN, FORTRAN66, FORTRAN77, FORTRAN90, FORTRAN95 17.1 A Z ( ) 0 9, _, =, +, -, *,
Microsoft PowerPoint - KN-2006NOV16.ppt
局所細分化メッシュに基づく並列有限 要素法における前処理付き反復法 Preconditioned Iterative Methods for Parallel Finite-Element Applications with Adaptive Mesh Refinement 中島研吾 (1) 兵藤守 (2) (1) 東京大学大学院理学系研究科地球惑星科学専攻 (2) 地球シミュレータセンター固体地球シミュレーション研究グループ
プラズマ核融合学会誌５月号【８１－５】／内外情報＿ソフト【注：欧フォント特殊！】
PROGRAM PLOTDATA USE NUM_KINDS, ONLY : wp=>dp, i4b USE MYLIB, ONLY : GET_SIZE, GET_DATA INTEGER(i4b) :: ntime, nx REAL(wp), ALLOCATABLE :: time(:), x(:), Temp(:,:) Fortran Temp, temp, TEMP temporal REAL(wp)
次に示す数値の並びを昇順にソートするものとする このソートでは配列の末尾側から操作を行っていく まず 末尾の数値 9 と 8 に着目する 昇順にソートするので この値を交換すると以下の数値の並びになる 次に末尾側から 2 番目と 3 番目の 1
4. ソート ( 教科書 p.205-p.273) 整列すなわちソートは アプリケーションを作成する際には良く使われる基本的な操作であり 今までに数多くのソートのアルゴリズムが考えられてきた 今回はこれらソートのアルゴリズムについて学習していく ソートとはソートとは与えられたデータの集合をキーとなる項目の値の大小関係に基づき 一定の順序で並べ替える操作である ソートには図 1 に示すように キーの値の小さいデータを先頭に並べる
Fortran 勉強会 第 5 回 辻野智紀
Fortran 勉強会 第 5 回 辻野智紀 今回のお品書き サブルーチンの分割コンパイル ライブラリ 静的ライブラリ 動的ライブラリ モジュール その前に 以下の URL から STPK ライブラリをインストールしておいて下さい. http://www.gfd-dennou.org/library/davis/stpk 前回参加された方はインストール済みのはず. サブルーチンの分割コンパイル サブルーチンの独立化
Microsoft PowerPoint - algo ppt [互換モード]
![Microsoft PowerPoint - algo ppt [互換モード]](/thumbs/65/53901879.jpg "Microsoft PowerPoint - algo ppt [互換モード]")
( 復習 ) アルゴリズムとは アルゴリズム概論 - 探索 () - アルゴリズム 問題を解くための曖昧さのない手順 与えられた問題を解くための機械的操作からなる有限の手続き 機械的操作 : 単純な演算, 代入, 比較など 安本慶一 yasumoto[at]is.naist.jp プログラムとの違い プログラムはアルゴリズムをプログラミング言語で表現したもの アルゴリズムは自然言語でも, プログラミング言語でも表現できる
memo
数理情報工学演習第一 C プログラミング演習 ( 第 5 回 ) 2015/05/11 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : プロトタイプ宣言 ヘッダーファイル, プログラムの分割 課題 : 疎行列 2 プロトタイプ宣言 3 C 言語では, 関数や変数は使用する前 ( ソースの上のほう ) に定義されている必要がある. double sub(int
C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ
C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 今回のプログラミングの課題 次のステップによって 徐々に難易度の高いプログラムを作成する ( 参照用の番号は よくわかる C 言語 のページ番号 ) 1. キーボード入力された整数 10 個の中から最大のものを答える 2. 整数を要素とする配列 (p.57-59) に初期値を与えておき
画像ファイルを扱う これまでに学んだ条件分岐, 繰り返し, 配列, ファイル入出力を使って, 画像を扱うプログラムにチャレンジしてみよう
第 14 回 応用 情報処理演習 ( テキスト : 第 10 章 ) 画像ファイルを扱う これまでに学んだ条件分岐, 繰り返し, 配列, ファイル入出力を使って, 画像を扱うプログラムにチャレンジしてみよう 特定色の画素の検出 ( テキスト 134 ページ ) 画像データが保存されているファイルを読み込んで, 特定色の画素の位置を検出するプログラムを作成しなさい 元画像生成画像 ( 結果の画像 )
文字数は1~6なので 同じ本数の枝を持つパスで生成される呪文の長さは最大で6 倍の差がある 例えば 上図のようなケースを考える 1サイクル終了した時点では スター節点のところに最強呪文として aaaaaac が求まる しかしながら サイクルを繰り返していくと やがてスター節点のところに aaaaaa
[Problem E] 最強の呪文 例えば 上図のような場合を考えると 節点 0( スター ) から節点 1 に至るパスの最強の呪文は aa であるが 節点 0 から節点 2 に至るパスの最強の呪文は aabc であり 節点 0 と節点 1 の間のパスとして最強の aa は用いられていない したがって スターから各節点への最強の呪文を求めていく方法は旨く機能しないと考えられる 一方 上図において 節点
Taro-最大値探索法の開発（公開版
最大値探索法の開発 0. 目次 1. 開発過程 1 目標 1 : 4 個のデータの最大値を求める 目標 2 : 4 個のデータの最大値を求める 改良 : 多数のデータに対応するため 配列を使う 目標 3 : n 個のデータの最大値を求める 改良 : コードを簡潔に記述するため for 文を使う 目標 4 : n 個のデータの最大値を求める 改良 : プログラムをわかりやすくするため 関数を使う 目標
[Problem D] ぐらぐら 一般に n 個の物体があり i 番目の物体の重心の x 座標を x i, 重さを w i とすると 全体の n 重心の x 座標と重さ w は x = ( x w ) / w, w = w となる i= 1 i i n i= 1 i 良さそうな方法は思いつかなかった
![[Problem D] ぐらぐら 一般に n 個の物体があり i 番目の物体の重心の x 座標を x i, 重さを w i とすると 全体の n 重心の x 座標と重さ w は x = ( x w ) / w, w = w となる i= 1 i i n i= 1 i 良さそうな方法は思いつかなかった](/thumbs/98/134835460.jpg "[Problem D] ぐらぐら 一般に n 個の物体があり i 番目の物体の重心の x 座標を x i, 重さを w i とすると 全体の n 重心の x 座標と重さ w は x = ( x w ) / w, w = w となる i= 1 i i n i= 1 i 良さそうな方法は思いつかなかった")
[Problem D] ぐらぐら 一般に n 個の物体があり 番目の物体の重心の x 座標を x, 重さを w とすると 全体の n 重心の x 座標と重さ w は x = ( x w ) / w, w = w となる = n = 良さそうな方法は思いつかなかった アイデア募集中!!! ので 少し強引に解いている 入力データの読み込みは w と h を scanf で読み込み getchar でその行の行末コードを読み込み
120802_MPI.ppt
CPU CPU CPU CPU CPU SMP Symmetric MultiProcessing CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU CP OpenMP MPI MPI CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU MPI MPI+OpenMP CPU CPU CPU CPU CPU CPU CPU CP
ex04_2012.ppt
2012 年度計算機システム演習第 4 回 2012.05.07 第 2 回課題の補足 } TSUBAMEへのログイン } TSUBAMEは学内からのログインはパスワードで可能 } } } } しかし 演習室ではパスワードでログインできない設定 } 公開鍵認証でログイン 公開鍵, 秘密鍵の生成 } ターミナルを開く } $ ssh-keygen } Enter file in which to save
all.dvi
fortran 1996 4 18 2007 6 11 2012 11 12 1 3 1.1..................................... 3 1.2.............................. 3 2 fortran I 5 2.1 write................................ 5 2.2.................................
プログラミングI第10回
プログラミング 1 第 10 回 構造体 (3) 応用 リスト操作 この資料にあるサンプルプログラムは /home/course/prog1/public_html/2007/hw/lec/sources/ 下に置いてありますから 各自自分のディレクトリにコピーして コンパイル 実行してみてください Prog1 2007 Lec 101 Programming1 Group 19992007 データ構造
Taro-プログラミングの基礎Ⅱ（公
0. 目次 2. プログラムの作成 2. 1 コラッツ問題 自然数 n から出発して n が偶数ならば 2 で割り n が奇数ならば 3 倍して 1 を足す操作を行う この操作を繰り返すと最後に 1 になると予想されている 問題 1 自然数 aの操作回数を求めよ 問題 2 自然数 aから bまでのなかで 最大操作回数となる自然数を求めよ 2. 2 耐久数 正整数の各桁の数字を掛け 得られた結果についても同様の操作を繰り返す
演習2
神戸市立工業高等専門学校電気工学科 / 電子工学科専門科目 数値解析 2017.6.2 演習 2 山浦剛 (tyamaura@riken.jp) 講義資料ページ h t t p://clim ate.aic s. riken. jp/m embers/yamaura/num erical_analysis. html 曲線の推定 N 次多項式ラグランジュ補間 y = p N x = σ N x x
Microsoft PowerPoint - GeoFEM.ppt [互換モード]
![Microsoft PowerPoint - GeoFEM.ppt [互換モード]](/thumbs/82/86058026.jpg "Microsoft PowerPoint - GeoFEM.ppt [互換モード]")
三次元並列有限要素法への OpenMP/MPI ハイブリッド 並列プログラミングモデル適用 中島研吾東京大学情報基盤センター RIKEN AICS Spring School 2014 2 Hybrid 並列プログラミング スレッド並列 + メッセージパッシング OpenMP+ MPI CUDA + MPI, OpenACC + MPI 個人的には自動並列化 +MPI のことを ハイブリッド とは呼んでほしくない
Microsoft Word - VBA基礎(3).docx
上に中和滴定のフローチャートを示しました この中で溶液の色を判断する部分があります このような判断はプログラムではどのように行うのでしょうか 判断に使う命令は IF 文を使います IF は英語で もし何々なら という意味になります 条件判断条件判断には次の命令を使います If 条件式 1 Then ElseIf 条件式 2 Then ElseIf 条件式 3 Then 実行文群 1 実行文群 2 実行文群
< 中略 > 24 0 NNE 次に 指定した日時の時間降水量と気温を 観測地点の一覧表に載っているすべての地点について出力するプログラムを作成してみます 観測地点の一覧表は index.txt というファイルで与えられています このファイルを読みこむためのサブルーチンが AMD
地上気象観測データの解析 1 AMeDAS データの解析 研究を進めるにあたって データ解析用のプログラムを自分で作成する必要が生じることがあります ここでは 自分で FORTRAN または C でプログラムを作成し CD-ROM に入った気象観測データ ( 気象庁による AMeDAS の観測データ ) を読みこんで解析します データを読みこむためのサブルーチンや関数はあらかじめ作成してあります それらのサブルーチンや関数を使って自分でプログラムを書いてデータを解析していきます
Microsoft Word - 資料 docx
y = Asin 2πt T t t = t i i 1 n+1 i i+1 Δt t t i = Δt i 1 ( ) y i = Asin 2πt i T 29 (x, y) t ( ) x = Asin 2πmt y = Asin( 2πnt + δ ) m, n δ (x, y) m, n 30 L A x y A L x 31 plot sine curve program sine implicit
格子点データの解析 1 月平均全球客観解析データの解析 客観解析データや衛星観測データのような格子点データは バイナリ形式のデータファイルに記録されていることが多いです バイナリ形式のデータファイルは テキスト形式の場合とは異なり 直接中身を見ることができません プログラムを書いてデータを読み出して
格子点データの解析 1 月平均全球客観解析データの解析 客観解析データや衛星観測データのような格子点データは バイナリ形式のデータファイルに記録されていることが多いです バイナリ形式のデータファイルは テキスト形式の場合とは異なり 直接中身を見ることができません プログラムを書いてデータを読み出して解析するのが普通です ここでは 全球客観解析データを用いてバイナリ形式のファイルに記録された格子点データの解析について学びたいと思います
インテル(R) Visual Fortran Composer XE 2013 Windows版 入門ガイド
Visual Fortran Composer XE 2013 Windows* エクセルソフト株式会社 www.xlsoft.com Rev. 1.1 (2012/12/10) Copyright 1998-2013 XLsoft Corporation. All Rights Reserved. 1 / 53 ... 3... 4... 4... 5 Visual Studio... 9...
プログラミング入門１
プログラミング入門 1 第 5 回 繰り返し (while ループ ) 授業開始前に ログオン後 不要なファイルを削除し て待機してください Java 1 第 5 回 2 参考書について 参考書は自分にあったものをぜひ手元において自習してください 授業の WEB 教材は勉強の入り口へみなさんを案内するのが目的でつくられている これで十分という訳ではない 第 1 回に紹介した本以外にも良書がたくさんある
演習1
神戸市立工業高等専門学校電気工学科 / 電子工学科専門科目 数値解析 2019.5.10 演習 1 山浦剛 (tyamaura@riken.jp) 講義資料ページ http://r-ccs-climate.riken.jp/members/yamaura/numerical_analysis.html Fortran とは? Fortran(= FORmula TRANslation ) は 1950
スーパーコンピューティングニュース特集号 原稿
T2K オープンスパコン ( 東大 ) チューニング連載講座番外編 Hybrid 並列プログラミングモデルの評価 (I) 中島研吾 東京大学情報基盤センター 1. はじめに本 スーパーコンピューティングニュース では,2008 年 5 月号から 2009 年 3 月号まで 6 巻,1 年間にわたって T2K オープンスパコン ( 東大 ) チューニング講座 1 を連載し, 各方面から好評をいただいた.
ポインタ変数
プログラミング及び実習 5 馬青 1 文字処理 数値処理 : 整数 浮動小数点数 単一の文字は と ( シングルクォーテーション ) で囲んで表現される 文字のデータ型は char または int である int を用いたほうが ライブラリの関数の引数の型と一致する 以下は全部 int の使用に統一する 従って int ch; で文字変数を宣言しておくと ch= A ; のように ch に文字 A
OpenMP¤òÍѤ¤¤¿ÊÂÎó·×»»¡Ê£±¡Ë
2012 5 24 scalar Open MP Hello World Do (omp do) (omp workshare) (shared, private) π (reduction) PU PU PU 2 16 OpenMP FORTRAN/C/C++ MPI OpenMP 1997 FORTRAN Ver. 1.0 API 1998 C/C++ Ver. 1.0 API 2000 FORTRAN
Microsoft Word - 3new.doc
プログラミング演習 II 講義資料 3 ポインタ I - ポインタの基礎 1 ポインタとは ポインタとはポインタは, アドレス ( データが格納されている場所 ) を扱うデータ型です つまり, アドレスを通してデータを間接的に処理します ポインタを使用する場合の, 処理の手順は以下のようになります 1 ポインタ変数を宣言する 2 ポインタ変数へアドレスを割り当てる 3 ポインタ変数を用いて処理 (
第２回
第 4 回基本データ構造 1 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 1 配列 スタック キューとその操作 4-1. 配列とその操作 配列型 同じ型の変数を並べたもの 配列にする型は 基本型 配列型 構造体 ポインタいずれでもよい 要素の並べ方を 次元 という 1 次元配列 ( 直線状 ) 2 次元配列 ( 平面状 ) 3 次元配列 ( 立体状 ) a[5]
Microsoft PowerPoint - 06.pptx
アルゴリズムとデータ構造第 6 回 : 探索問題に対応するデータ構造 (2) 担当 : 上原隆平 (uehara) 2015/04/22 内容 スタック (stack): 最後に追加されたデータが最初に取り出される 待ち行列 / キュー (queue): 最初に追加されたデータが最初に取り出される ヒープ (heap): 蓄えられたデータのうち小さいものから順に取り出される 配列による実装 連結リストによる実装
OpenMP¤òÍѤ¤¤¿ÊÂÎó·×»»¡Ê£±¡Ë
2011 5 26 scalar Open MP Hello World Do (omp do) (omp workshare) (shared, private) π (reduction) scalar magny-cours, 48 scalar scalar 1 % scp. ssh / authorized keys 133. 30. 112. 246 2 48 % ssh 133.30.112.246
4 分岐処理と繰返し処理 ( 教科書 P.32) プログラムの基本的処理は三つある. (1) 順次処理 : 上から下に順番に処理する ぶんきそろ (2) 分岐処理 : 条件が揃えば, 処理する はんぷく (3) 反復処理 : 条件が揃うまで処理を繰り返す 全てのプログラムは (1) から (3) の
4 分岐処理と繰返し処理 ( 教科書 P.32) プログラムの基本的処理は三つある. (1) 順次処理 : 上から下に順番に処理する ぶんきそろ (2) 分岐処理 : 条件が揃えば, 処理する はんぷく (3) 反復処理 : 条件が揃うまで処理を繰り返す 全てのプログラムは (1) から (3) の組み合わせで作れる. ここでは (2) と (3) について扱う. 4.1 分岐処理 4.1.1 if
Microsoft Word - 03-数値計算の基礎.docx
δx f x 0 + δ x n=0 a n = f ( n) ( x 0 ) n δx n f x x=0 sin x = x x3 3 + x5 5 x7 7 +... x ( ) = a n δ x n ( ) = sin x ak = (-mod(k,2))**(k/2) / fact_k 10 11 I = f x dx a ΔS = f ( x)h I = f a h I = h b (
0 21 カラー反射率 slope aspect 図 2.9: 復元結果例 2.4 画像生成技術としての計算フォトグラフィ 3 次元情報を復元することにより, 画像生成 ( レンダリング ) に応用することが可能である. 近年, コンピュータにより, カメラで直接得られない画像を生成する技術分野が生
0 21 カラー反射率 slope aspect 図 2.9: 復元結果例 2.4 画像生成技術としての計算フォトグラフィ 3 次元情報を復元することにより, 画像生成 ( レンダリング ) に応用することが可能である. 近年, コンピュータにより, カメラで直接得られない画像を生成する技術分野が生まれ, コンピューテーショナルフォトグラフィ ( 計算フォトグラフィ ) と呼ばれている.3 次元画像認識技術の計算フォトグラフィへの応用として,
スライド 1
数値解析 平成 30 年度前期第 10 週 [6 月 12 日 ] 静岡大学工学研究科機械工学専攻ロボット 計測情報分野創造科学技術大学院情報科学専攻 三浦憲二郎 講義アウトライン [6 月 12 日 ] 連立 1 次方程式の直接解法 ガウス消去法 ( 復習 ) 部分ピボット選択付きガウス消去法 連立 1 次方程式 連立 1 次方程式の重要性 非線形の問題は基本的には解けない. 非線形問題を線形化して解く.
kiso2-09.key
座席指定はありません 計算機基礎実習II 2018 のウェブページか 第9回 ら 以下の課題に自力で取り組んで下さい 計算機基礎実習II 第7回の復習課題(rev07) 第9回の基本課題(base09) 第8回試験の結果 中間試験に関するコメント コンパイルできない不完全なプログラムなど プログラミングに慣れていない あるいは複雑な問題は 要件 をバラして段階的にプログラムを作成する exam08-2.c
Microsoft PowerPoint - 講義10改.pptx
計算機プログラミング ( 後半組 ) Computer Programming (2nd half group) 担当 : 城﨑知至 Instructor: Tomoyuki JOHZAKI 第 9 回ファイルの入出力 Lesson 9 input/output statements 教科書 7.3 章 1 ファイル入出力 : サンプル 1 下記プログラムを outin1.f90 として作成し コンパイル実
memo
計数工学プログラミング演習 ( 第 3 回 ) 2016/04/26 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 内容 ポインタ malloc 構造体 2 ポインタ あるメモリ領域 ( アドレス ) を代入できる変数 型は一致している必要がある 定義時には値は不定 ( 何も指していない ) 実際にはどこかのメモリを指しているので, #include
情報活用資料
y = Asin 2πt T t t = t i i 1 n+1 i i+1 Δt t t i = Δt i 1 ( ) y i = Asin 2πt i T 21 (x, y) t ( ) x = Asin 2πmt y = Asin( 2πnt + δ ) m, n δ (x, y) m, n 22 L A x y A L x 23 ls -l gnuplot gnuplot> plot "sine.dat"
メソッドのまとめ
配列 (2) 2 次元配列, String http://jv2005.cis.k.hosei.c.jp/ 授業の前に自己点検 配列変数に格納される配列の ID と配列の実体の区別ができていますか 配列変数の宣言と配列の実体の生成の区別ができていますか メソッドの引数に配列が渡されるとき 実際に渡されるものは何ですか このことの重要な帰結は何ですか 引数の値渡しと参照渡しということばを例を挙げて説明できますか
< 中略 > 24 0 NNE 次に 指定した日時の時間降水量と気温を 観測地点の一覧表に載っているすべての地点について出力するプログラムを作成してみます 観測地点の一覧表は index.txt というファイルで与えられています このファイルを読みこむためのサブルーチンが AMD
気象観測データの解析 1 AMeDAS データの解析 研究を進めるにあたって データ解析用のプログラムを自分で作成する必要が生じることがあります ここでは 自分で FORTRAN または C でプログラムを作成し CD-ROM に入った気象観測データ ( 気象庁による AMeDAS の観測データ ) を読みこんで解析します データを読みこむためのサブルーチンや関数はあらかじめ作成してあります それらのサブルーチンや関数を使って自分でプログラムを書いてデータを解析していきます
Microsoft PowerPoint - 11-omp.pptx
並列有限要素法による 三次元定常熱伝導解析プログラム OpenMP+ ハイブリッド並列化 中島研吾東京大学情報基盤センター 2 Hybrid 並列プログラミング スレッド並列 + メッセージパッシング OpenMP+ MPI UDA + MPI, OpenA + MPI 個人的には自動並列化 +MPI のことを ハイブリッド とは呼んでほしくない 自動並列化に頼るのは危険である 東大センターでは現在自動並列化機能はコンパイラの要件にしていない
Taro-再帰関数Ⅲ（公開版）.jtd
0. 目次 1 1. ソート 1 1. 1 挿入ソート 1 1. 2 クイックソート 1 1. 3 マージソート - 1 - 1 1. ソート 1 1. 1 挿入ソート 挿入ソートを再帰関数 isort を用いて書く 整列しているデータ (a[1] から a[n-1] まで ) に a[n] を挿入する操作を繰り返す 再帰的定義 isort(a[1],,a[n]) = insert(isort(a[1],,a[n-1]),a[n])
<4D F736F F D20332E322E332E819C97AC91CC89F090CD82A982E78CA982E9466F E393082CC8D5C91A291CC90AB945C955D89BF5F8D8296D85F F8D F5F E646F63>
3.2.3. 流体解析から見る Fortran90 の構造体性能評価 宇宙航空研究開発機構 高木亮治 1. はじめに Fortran90 では 構造体 動的配列 ポインターなど様々な便利な機能が追加され ユーザーがプログラムを作成する際に選択の幅が広がりより便利になった 一方で 実際のアプリケーションプログラムを開発する際には 解析対象となる物理現象を記述する数学モデルやそれらを解析するための計算手法が内包する階層構造を反映したプログラムを作成できるかどうかは一つの重要な観点であると考えられる
gengo1-8
問題提起その 1 一文字ずつ文字 ( 数字 ) を読み込み それぞれの文字が何回入力されたかを数えて出力するプログラム int code, count_0=0, count_1=0, count_2=0, count_3=0,..., count_9=0; while( (code=getchar())!= EOF ){ } switch(code){ case 0 : count_0++; break;
1 u t = au (finite difference) u t = au Von Neumann
1 u t = au 3 1.1 (finite difference)............................. 3 1.2 u t = au.................................. 3 1.3 Von Neumann............... 5 1.4 Von Neumann............... 6 1.5............................
Microsoft PowerPoint - KHPCSS pptx
KOBE HPC サマースクール 2018( 初級 ) 9. 1 対 1 通信関数, 集団通信関数 2018/8/8 KOBE HPC サマースクール 2018 1 2018/8/8 KOBE HPC サマースクール 2018 2 MPI プログラム (M-2):1 対 1 通信関数 問題 1 から 100 までの整数の和を 2 並列で求めなさい. プログラムの方針 プロセス0: 1から50までの和を求める.
簡単な検索と整列（ソート）
フローチャート (2) アルゴリズム論第 2 回講義 2011 年 10 月 7 日 ( 金 ) 反復構造 ( 一定回数のループ処理 ) START 100 回同じ処理を繰り返す お風呂で子供が指をおって数を数える感じ 繰り返し数を記憶する変数をカウンター ( 変数名 I をよく使う ) と呼ぶ カウンターを初期化して, 100 回繰り返したかどうか判定してそうならば終了そうでなければ処理を実行して
演習１： 演習準備
演習 1: 演習準備 2013 年 8 月 6 日神戸大学大学院システム情報学研究科森下浩二 1 演習 1 の内容 神戸大 X10(π-omputer) について システム概要 ログイン方法 コンパイルとジョブ実行方法 OpenMP の演習 ( 入門編 ) 1. parallel 構文 実行時ライブラリ関数 2. ループ構文 3. shared 節 private 節 4. reduction 節
2006年10月5日（木）実施
2010 年 7 月 2 日 ( 金 ) 実施 ファイル処理ファイルとはファイル (file) は日常用語では紙などを綴じたものを表すが, コンピュータ用語ではデータの集合体を指す言葉である ファイルは例えば, 文書ファイルやプログラムファイルのように, 用途によって分類されることもあれば, また, テキストファイルやバイナリファイルのように, ファイルの作り方によって分類されることもある なお,
openmp1_Yaguchi_version_170530
並列計算とは /OpenMP の初歩 (1) 今 の内容 なぜ並列計算が必要か? スーパーコンピュータの性能動向 1ExaFLOPS 次世代スハ コン 京 1PFLOPS 性能 1TFLOPS 1GFLOPS スカラー機ベクトル機ベクトル並列機並列機 X-MP ncube2 CRAY-1 S-810 SR8000 VPP500 CM-5 ASCI-5 ASCI-4 S3800 T3E-900 SR2201
Microsoft PowerPoint - 05.pptx
アルゴリズムとデータ構造第 5 回 : データ構造 (1) 探索問題に対応するデータ構造 担当 : 上原隆平 (uehara) 2015/04/17 アルゴリズムとデータ構造 アルゴリズム : 問題を解く手順を記述 データ構造 : データや計算の途中結果を蓄える形式 計算の効率に大きく影響を与える 例 : 配列 連結リスト スタック キュー 優先順位付きキュー 木構造 今回と次回で探索問題を例に説明
コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n
コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n を入力してもらい その後 1 から n までの全ての整数の合計 sum を計算し 最後にその sum
Javaセキュアコーディングセミナー東京 第3回 入出力(File, Stream)と例外時の動作 演習解説
Java セキュアコーディングセミナー東京第 3 回入出力と例外時の動作 演習解説 2012 年 11 月 11 日 ( 日 ) JPCERT コーディネーションセンター脆弱性解析チーム戸田洋三 1 Hands-on Exercises コンパイルエラーに対処しよう ファイルからのデータ入力を実装しよう 2 Hands-on Exercise(1) サンプルコードの コンパイルエラーに対処しよう 3
Taro-リストⅢ（公開版）.jtd
リスト Ⅲ 0. 目次 2. 基本的な操作 2. 1 リストから要素の削除 2. 2 リストの複写 2. 3 リストの連結 2. 4 問題 問題 1 問題 2-1 - 2. 基本的な操作 2. 1 リストから要素の削除 まず 一般的な処理を書き つぎに 特別な処理を書く 一般的な処理は 処理 1 : リスト中に 削除するデータを見つけ 削除する場合への対応 特別な処理は 処理 2 : 先頭のデータを削除する場合への対応
OHP.dvi
0 7 4 0000 5.. 3. 4. 5. 0 0 00 Gauss PC 0 Gauss 3 Gauss Gauss 3 4 4 4 4 3 4 4 4 4 3 4 4 4 4 3 4 4 4 4 u [] u [3] u [4] u [4] P 0 = P 0 (),3,4 (,), (3,), (4,) 0,,,3,4 3 3 3 3 4 4 4 4 0 3 6 6 0 6 3 6 0 6
11042 計算機言語7回目 サポートページ:
11042 7 :https://goo.gl/678wgm November 27, 2017 10/2 1(print, ) 10/16 2(2, ) 10/23 (3 ) 10/31( ),11/6 (4 ) 11/13,, 1 (5 6 ) 11/20,, 2 (5 6 ) 11/27 (7 12/4 (9 ) 12/11 1 (10 ) 12/18 2 (10 ) 12/25 3 (11
スクールCOBOL2002
(h) 登録集原文の指定方法 . 登録集原文の指定方法 複数の COBOL プログラムに共通の記述を別のソースファイルとしておき COPY 文で取り込むことができます 登録集原文の概念図を下欄に示します このようにすると コーディング量を削減でき 記述ミスもなくなるため 開発効率を高めることができます ここでは 第 章で実習した reidai.cbl というソースファイルの DATA0 と YYMMDD
プレポスト【解説】
コース名 : シェルの機能とプログラミング ~UNIX/Linux の効率的使用を目指して ~ 1 UNIX および Linux の主な構成要素は シェル コマンド カーネルです プロセスとは コマンドやプログラムを実行する単位のことなので プロセスに関する記述は誤りです UNIX および Linux のユーザーインターフェースは シェル です コマンドを解釈するという機能から コマンドインタープリタであるともいえます
PowerPoint プレゼンテーション
プログラミング応用演習 第 5 回演習 前回までのお話 ポインタ ポインタを用いた文字列処理 構造体 ファイル 再帰的構造体 リスト構造 動的メモリ管理 今日のお題 ポインタやファイルなど これまでの内容の練習 教材 以前 以下に単語を収録したファイルがあることを紹介した : /usr/share/dict/words この中からランダムに単語を取り出したファイルを用意した http://sun.ac.jp/prof/yamagu/2019app/
ＪａｖａプログラミングⅠ
Java プログラミング Ⅰ 8 回目 for 文 今日の講義で学ぶ内容 for 文 変数のスコープ for 文の入れ子 繰り返し文 1 for 文 for 文最初に一度だけ初期化の式を処理します条件が true の場合 文を実行し 更新の式を処理して繰り返します条件が false の場合 for 文を終了します 条件は boolean 型で 関係演算子で表現される式などを記述します for( 初期化の式
課題 S1 解説 Fortran 編 中島研吾 東京大学情報基盤センター
課題 S1 解説 Fortran 編 中島研吾 東京大学情報基盤センター 内容 課題 S1 /a1.0~a1.3, /a2.0~a2.3 から局所ベクトル情報を読み込み, 全体ベクトルのノルム ( x ) を求めるプログラムを作成する (S1-1) file.f,file2.f をそれぞれ参考にする 下記の数値積分の結果を台形公式によって求めるプログラムを作成する
Microsoft PowerPoint - S1-ref-F.ppt [互換モード]
![Microsoft PowerPoint - S1-ref-F.ppt [互換モード]](/thumbs/86/94184661.jpg "Microsoft PowerPoint - S1-ref-F.ppt [互換モード]")
課題 S1 解説 Fortran 言語編 RIKEN AICS HPC Summer School 2014 中島研吾 ( 東大 情報基盤センター ) 横川三津夫 ( 神戸大 計算科学教育センター ) MPI Programming 課題 S1 (1/2) /a1.0~a1.3, /a2.0~a2.3 から局所ベクトル情報を読み込み, 全体ベクトルのノルム ( x ) を求めるプログラムを作成する
Microsoft PowerPoint - info1-8.ppt [互換モード]
![Microsoft PowerPoint - info1-8.ppt [互換モード]](/thumbs/88/114900953.jpg "Microsoft PowerPoint - info1-8.ppt [互換モード]")
平成 29 年度 情報基礎演習 Ⅰ 第 8 回演習 担当光武雄一 授業の Website: http://web.me.saga-u.ac.jp/~mitutake/info1/info1.html メールアドレス : mitutake@me.saga-u.ac.jp 第 8 回目演習内容 先週の課題解答と説明 合計値の計算法 マクローリン級数の計算 (57 ページ ) Report0523 の解答例
Microsoft PowerPoint - chap10_OOP.ppt
プログラミング講義 Chapter 10: オブジェクト指向プログラミング (Object-Oriented Programming=OOP) の入り口の入り口の入り口 秋山英三 F1027 1 例 : 部屋のデータを扱う // Test.java の内容 public class Test { public static void main(string[] args) { double length1,
Microsoft Word - 資料 (テイラー級数と数値積分).docx
δx δx n x=0 sin x = x x3 3 + x5 5 x7 7 +... x ak = (-mod(k,2))**(k/2) / fact_k ( ) = a n δ x n f x 0 + δ x a n = f ( n) ( x 0 ) n f ( x) = sin x n=0 58 I = b a ( ) f x dx ΔS = f ( x)h I = f a h h I = h
memo
計数工学プログラミング演習 ( 第 6 回 ) 2017/05/16 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : 再帰呼び出し 2 分探索木 深さ優先探索 課題 : 2 分探索木を用いたソート 2 再帰呼び出し 関数が, 自分自身を呼び出すこと (recursive call, recursion) 再帰を使ってアルゴリズムを設計すると, 簡単になることが多い
memo
計数工学プログラミング演習 ( 第 6 回 ) 2016/05/24 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : 再帰呼び出し 2 分探索木 深さ優先探索 課題 : 2 分探索木を用いたソート 2 再帰呼び出し 関数が, 自分自身を呼び出すこと (recursive call, recursion) 再帰を使ってアルゴリズムを設計すると, 簡単になることが多い
プログラム例 /* ACM-ICPC2009 国内予選 Problem C */ // // filename = pc1.c // コンパイル
[Problem C] 覆面計算 与えられた覆面計算に対して 等式を満たすような数字の割り当てが何通りあるか を求める問題であるので 各文字に対する数字の割り当てを順番に生成していき その割り当てが等式を満たすかどうかチェックすればよい 異なる文字には異なる数値 (0~9) が割り当てられるので 最大で 10! 約 360 万通りの組み合わせをチェックする必要がある (1 桁の場合を除いて最上位の桁は
Microsoft PowerPoint - DA2_2017.pptx
// データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (II)/ 全点対最短路 トポロジカル ソート順による緩和 トポロジカル ソート順に緩和 閉路のない有向グラフ限定 閉路がないならトポロジカル ソート順に緩和するのがベルマン フォードより速い Θ(V + E) 方針 グラフをトポロジカル ソートして頂点に線形順序を与える ソート順に頂点を選び, その頂点の出辺を緩和する 各頂点は一回だけ選択される