論 文
電力潮流 計算 にお ける連立 一次方程 式 の直接写像形
並列処理 に よる高速化 可能性 について
非会員
稲
吉
宏
明(筑
波大)
正 員
大
澤
靖
治(神
戸大)
正
員 本
間
琢
也(筑
波大)
A Feasibility
Study of Direct-Mapping-Type
Parallel
Processing
Method
to Solve
Linear
Equations
in Load Flow Calculations
Hiroaki Inayoshi, Non-member (University of Tsukuba), Yasuharu Ohsawa, Member (Kobe
University), Takuya Homma, Member (University of Tsukuba)
Owing to the growing size and complexity in power systems, system analysis, such as the transient
calculation, take much time hence fast calculation methods are required. Although the parallel
processing is a hopeful method, there was a difficulty in the parallel solution of the linear equation
which appears in the power-flow calculation through the Newton-Raphson method.
This paper aims at the fast calculation of the power-flow ploblem via parallel processing. In order
to improve the suitability to the parallel solution of the differential equation in transient calculation,
we assume the use of a direct-mapping-type parallel processing machine, which directly maps the
network of a power system onto the network of processors. Under this assumption, we propose a
new parallel-processing-oriented method, where the linear equation is solved by linear-iterations
between nodes with the Aitken acceleration. We simulate the method on three model power systems
and compare this Parallel Iterative Method (PIM) with a Parallel Direct Method (PDM), which
uses the banded matrix, according to the number of operations required. As the results, we can
expect that the PIM may solve the linear equations faster than the PDM with m processors,
although the PIM might be inferior to the PDM with mxm processors, where m denotes the half
band-width of the banded matrix.
キー ワー ド:電 力 潮 流 計 算,並 列 処 理,直 接 写 像,高 速 化,エ イ トケ ン加 速,反 復 解 法 1.ま え が き 高品質 の 電 力 を需 要 家 に安 定 に供 給 す るた め に は, 電力系統 の 計 画 時 や 運 用 時 にお け る解 析 計 算 が 不 可 欠 である。 しか し,電 力 系 統 の 大 規 模 化 ・複 雑 化 に つ れ この解析 計 算 に か な りの 時 間 を要 す る よ う に な っ て お り,計 算 の 高速 化 が 望 まれ て い るω。 この ため,並 列 処 理 の 適 用 に よ り系 統 解 析 を 高速 化 しよ うとい う研 究 が 数 多 くな さ れ て い る(2)∼(7)。こ れ らは並 列処 理 の手 法 の 観 点 か ら以 下 の よ う に 分 類 で きる。 (I)系 統 の ネ ッ ト ワー クの トポ ロ ジー を あ る程 度 保 存 す る方 法 (II) トポ ロ ジー を陽 的 に は保 存 しな い 方 法 後 者 に属 す る例 と して は,帯 行 列 化 され た 連 立 一 次 方 程 式 を,行 列 の 半 帯 幅(ま た は そ の2乗)台 の プ ロ セ ッサ ア レイ で 解 く方法(2)が あ る。 前 者 は 更 に, (i) シ ス テ ム を 幾 つ か の サ ブ シ ス テ ム(ブ ロ ッ ク)に 分 割 し,そ れ ら を単 位 と して 並列 処 理 を 行 う方 法 電学論B,111巻8号,平 成3年 869
(ii) シ ス テ ム を構 成 す る各 ノー ドに プ ロセ ッサ を 割 当 て,ノ ー ド を単 位 として 並 列 処 理 を行 う方 法 に 分 類 で き る。(i)の 基 本 的 考 え は,ブ ロ ック間 の相 互 作 用 が 可 能 な 限 り小 さ くな る よ うな 分 割 に よ り,各 ブ ロ ック を近 似 的 に独 立 な も の と して 扱 お う と い う点 に あ る。 従 って,ブ ロ ッ ク分 割 を細 か くした 極 限 と し て(i)が(ii)を 含 む と い う こ とで は な く,考 え方 の異 な る方 法 とみ な す べ きで あ る。 (i)の 例 と して,分 割 され た ブ ロ ッ クの 数 と並 列 処 理 時 間 との 関 係 な どの 報 告(3)や,ブ ロ ッ ク分 割 と逆 行 列 補 助 定 理 を利 用 し た 状 態 推 定 の 並 列 解 法 ω が あ る。 また(i)の 拡 張 と して,オ ーバ ラ ッ プの あ る ブ ロ ック分 割 も考 え られ て い る(5)。 他 方,分 類(I)と(II)の 中 間的 な例 と して,ま ば らな連 立 一 次 方 程 式 を解 く際 に ノ ー ド間 の 接 続 を “factor-ization path graph” とい う形 に 変 形 し,こ れ を も と
に した並 列 解 法 も提 案 され て い る(6)。 しか しな が ら,以 下 の3点 の よ うな 事 情 を考 慮 す る と分 類(II)の 並 列 処 理 方 法 が 望 ま し く思 わ れ る。 (1) 過 渡 計 算 にお け る微 分 方程 式 の 計 算 は,ノ ー ドご とに独 立 に 行 え る点 (2)潮 流 計 算 で の 各 ノ ー ドの ミス マ ッ チ の 計 算 や,ニ ュー トンーラ フ ソ ン法(以 下,NR法 と略 記)を 用 い る際 の ヤ コ ビ行 列 要 素 の計 算 は,系 統 で 隣 接 して い る ノー ドの情 報 が あれ ば,各 ノ ー ドで 独 立 に計 算 で きる 点 (3)前 記 分 類(II)でNR法 を 行 う際 に 必 要 と な る 上 記(2)の 計 算 時 の オ ー バ ヘ ッ ドが 不 要 で あ る点 〔文 献(2)の プ ロ セ ッサ ア レイ で この 計 算 を行 う とす れ ば,プ ロ セ ッサ 間 の デ ー タ転 送 が か な り複 雑 に な り,他 方 一 つ の ホ ス ト(ま た は 中心 プ ロセ ッサ 〉 で ま とめ て計 算 す るな ら,こ の ホ ス トか らア レ イへ の デ ー タ の再:割当 が オ ー バ ヘ ッ ド とな る 〕。 そ こで本 論 文 で は,分 類GDの 例 と して,電 力 系統 の ネ ッ トワー クの トポ ロ ジー を そ の ま ま プ ロ セ ッサ の ネ ッ トワ ー クに 写 像 値 接 写 像)す る形 の 並 列 処 理 を 想 定 し,こ の 可能 性 につ い て考 察 す る。 た だ し,高 速 化 す る対 象 は,解 析 計 算 の うち で大 きな ウ ェ イ トを 占 め て い る電 力潮 流 計 算 に つ い て の み と した 。ま ず,潮 流 計 算 に お け る近 接作 用 性 を最 大 隈 に利 用 し得 る ア ル ゴ リズ ム と して,NR法 に お け る連 立 一 次 方 程 式 を ノ ード 間 の 線 形 反復 に よ り解 く と同 時 に,こ れ に エ イ ト ケ ン加 速 を加 え る解 法 を示 す 。 そ して,シ ミュ レー シ ョ ン に よ り必 要 反 復 回 数 な どの測 定 を行 い,上 記 の 形 の 並 列 処 理 で どの 程 度 の 高 速 化 が 可 能 で あ る か を,他 解 法 との 比 較 に よ り明 らか に す る 。 更 に,分 類(ii)の 考 え方 を状 態推 定 に応 用 し た 論 文 が あ るが(7),こ れ と の 比 較 に つ い て も言 及 す る。 2,NR法 に よ る電 力 潮 流 計 算 の 定 式 化 〈2・1>諸 記 号 の 定 義 N:系 統 の ノ ー ド数 ακ≡{ノ ー ド κ に 直 接 つ な が っ て い る ノー ドの 集 合:κ を の ぞ く} βκ≡毎κに κ を含 めた 集 合} Nhk≡akの 要 素 数 篇 ノー ド κ の “手(hand)” の 数 Nhmax≡ max{NHκ};for{κ} 〈2・2>ヤ コ ビ行 列 の 要 素 ノ ー ド電 圧 を 直 角座 標 表 示 し た と き,NR法 に お け る ヤ コ ビ行 列 」 の う ち で,ノ ー ドの ペ アKと 五 に対 応 す る2×2ブ ロ ッ ク行 列 を
(1)
で 表 す 。 普 通 の行 列 と違 い,ノ ー ドの ペ ア ご とに2行 2列 の 行 列 が 対 応 して い るの は,ノ ー ドが 来知 数 二 つ と方 程 式 二つ に 対 応 し て い る こ と に よ る。 各 ノ ー ド Kに 対 し,Lが ど ん な 関 係 に あ る か に よ っ てJκLは 以 下 の よ う に な る。 た だ し,以 下 で添 字 κ やLが 自 明な と き は 省略 す る。 PQ指 定 の とき PV指 定 の と き PQ指 定 の と き PV指 定 の と き(2)
(3)
(4)
こ こ で, YKL =GKL-jBKL;ノ ー ド間 の ア ド ミ タ ン ス VK=eK+jfK;ノ ー ド電 圧並列処理 による電 力潮流計算の高速化
(14)
また,電 力 な ど指 定 値(添 字Sで 示 す)か らの 誤 差 を ⊿ Pk≡(Pk)s-Pk;有 効 電 力誤 差 ⊿Qk≡(Qk)s-Qk;無 効 電 力 誤 差 と し,こ れ か ら,(5)
(6)
PQ指 定 の と き PV指 定 の と き ・ ・指 定 値 ミスマ ッチ ・ ・電 圧 修 正 量(7)
と定 義 す る。上 記 の よ う に与 え られ る1鷹 お よ び ミス マッチwkに 対 し,NR法 に よ る潮 流計 算 で は,(8)
を,κ=1∼N(た だ し,ス ラ ッ ク ノ ー ドは 除 く)ま で連 立 させ た2(N-1)次 元 連 立 一 次 方 程 式 を2κ に つ いて解 くこ と を繰 返 す 。 3,RR法 に お け る 連 立 一 次 方 程 式 の 並 列 反 復 解 法 〈3・1>反 復 解 法 の 局 所 的 表 現 解 くべ き連 立 一 次方程式(8)に 対 し,ワ ー ド ・ヘ イ ル 法(8)では, と近 似 し て,(9)
(10)
を(8)式 の 近似 解 と した 。 この手 法 を反 復 解 法 に応 用 する。す な わ ち,(8)武 の 両 辺 にJ-1kkをか け,右 辺 を 左辺に移 項 す る と, が得 られ る。 両 辺 に2κ を加 え て,(11)
(12)
(13)
とお き(た だ し,δ κL:ク ロ ネ ッ カ の デ ル タ 記 号)整 理 す る と, とい う反 復 公 式 が 得 ら れ る。 こ こ で,(11)式 で は 五 ∈ βκで あ った が,(14)式 でL∈ ακ と な って い る点 が 異 な る。(12)∼(14)式 か ら,こ の 解 法 に よ る と,HkL や ξκは あ る ノ ー ド とそ れ に 隣 接 す る ノ ー ドの 情 報 の み か ら計 算 で き,反 復 公 式 に よ る計 算 も,隣 接 す る ノ ー ド問 の み で で き る こ とが わ か る。 〈3・2>反 復 解 法 の 全 体 的 表 現 以 上 を ノ ー ド κ の み で な く,行 列 全 体 で 表 現 す る と以 下 の よ う に な る。 解 くべ き連 立 一 次 方程 式 を Jz=w……(15 )と表 す 。 D≡(Jの2×2ブ ロ ック対 角部 分)… …(16) の 逆 行 列 を用 い て(15)式 を 変形 す る と が 得 られ る(I:単 位 行 列)。 反 復 行 列:Hを とす れ ば,連 立一 次 方 程 式 の 反 復 解 法 の式:(17)
(18)
(19)
が 得 られ る。 この解 法 の 特徴 は(16)式 に あ る。 す な わ ち,普 通 の 反 復 解 法 で は0と し て 」 の 対 角 項 の み を用 い る が, 潮 流 計 算 に お ける ヤ コ ビ行 列 は,電 圧 の直 角座 標 表 現 を用 い た場 合 一 般 に, {｜J1｜or｜J4｜}<{｜J2｜or｜J3｜} す な わ ち,2行2列 の 対 角項J1,J4の 大 き さ が,非 対 角項J2,J3の そ れ よ り小 とな って 優 対 角 と な っ て い な い。 ゆ えに0と し て 」 の 対 角 項 の み を用 い た 場 合, 反 復 行 列 の 最 大 固 有 値 が1以 上 とな る 可 能 性 が 大 で あ る。 しか し,(16)式 に よ れ ば この 点 は 問 題 な くな り, あ とは対 角 ブ ロ ッ ク と非 対 角 ブ ロ ッ ク との 間 の値 の大 小 が 問 題 とな るだ け で あ る。 しか し これ につ い て は, 行 列 が ア ド ミ タ ンス 行 列(Y行 列)の 優 対 角 を 反 映 す る た め,優 対 角 の保 存 が 期 待 で き る。 ま た,(16)式 に よ る ペ ナ ル テ ィー と して(12)式 あ る い は(13)式 の よ うな計 算 が 必 要 とな るが, (i)各 ノー ドを独 立 に 計 算 で き る点,お よび (ii) 単 純 な2行2列 の 乗 算 で あ る点 な どか ら,計 算 負 荷 を そ れ ほ ど増 加 さ せ る わ け で は な い。 潮 流 計 算 全 体 の 処 理 をPAD表 現(9)す る と,図1の よ う に な る(図5も 参 照)。 図1の 二 つ の ル ー プ の う ち,外 側 の 反 復 の 各 ス テ ッ プ を 「NRス テ ップ 」 と呼 ぶ こ とに す る。 電 学 論B,111巻8号,平 成3年 871図1
並列 反復解 法のPAD表
現
Fig. 1. PAD representation of parallel iterative method.
図2線 形 反復 の 収 束 の様 子(一 次 元)
Fig. 2. Convergence
of linear
iteration
(one-dimension).
図3 エ イ トケ ン加 速 の 図 的 説 明 Fig. 3. Graphic explanation for Aitken acceleration. 4.エ イ トケ ン加 速 〈4・1>概 念 の 説 明 連 立 一 次 方 程 式:Jz=wの 解 をaと す る。 反 復 公 式(19)に よ る2のv番 目 の 近 似 値(≡z〔v〕〉の 誤 差:ε〔v〕 は
(20)
と表 せ る。 こ こ で,〃 次 元 行 列:HのM個 の 固 有 値 お よ び 固 有 ベ ク トル を そ れ ぞ れ{λ」お よ び{ui};i=1∼M とお く。初期誤 差:
(21)
(ci:定 数)……(22) と展 開 で き,(20)式 よ り(23)
と な る 。 と こ ろ で,反 復 式: 〔v〕=px〔v-1+q(p≠1,q:定 数) ……(24) で 得 られ る数 列:x〔v〕 の 一 般 項 は(25)
ただ し,A={limx〔v〕;v→∽}=q/(1-p) とな る こ とが簡 単 な計 算 で わ か る(こ れ は図2の よ う に収 束 す る〉。 他 方,x〔v+1〕=f(x〔v〕)で 得 ら れ る 数 列:{x〔v〕; v =1 ,2,…}の 収 束 を 速 め る手 法 の 一 つ で あ るエ イ ト ケ ン加 速 は,図3の よ う に2点P,Qを 通 る直 線 とy =xの 交 点:Rに よ っ て,よ り解 に 近 い 近 似 値x〔c〕 を得 よ う とす る。 ゆ え に,エ イ トケ ン加速 を図2の 数 列 に適 用 す れ ば,x 〔v〕=px〔v-1〕+q の反 復 演 算 を何 度 も繰 返 す こ と な く解 が 得 られ る。 と こ ろ が,(25)式 は,(23)式 で34僧 の べ き乗 和 の う ち の1項 だ け が残 った 式に対 応 して い る。 ゆ え に,(23) 式 でλ｜λi｜<1 (for ALLi)
な ら ば,固 有値 の 絶 対 値 の 大 き さの2番 目以 降 の成 分 が 十 分 小 さ くな っ た と こ ろ で は,(23)式(正 確 には 2{の)は(25)式 で 近 似 で き る。(25)式 は上 に述 べ た と お り,エ イ トケ ン加 速 に よ り簡 単 に解 が 求 まるの で, (19)式 の 収 束 は,反 復 行 列Hの 固 有 値 を絶 対 値 の大 き い 順 に{λ1,λ2,…λMと す れ ば,(｜λ1｜<1な ら ば) ｜λ2｜に 依 存 す る こ とが 結 論 付 け られ る。
並列処理 に よる電 力潮 流計算の高速化
〈4・2>エ イ トケ ン 加 速 用 の回 路 に つ い て 数 列{x〔v〕;v=0,1,2,…}に 対 し て, と定 義 す る(た だ し,⊿:後 退 差 分 演 算 子)。 数 列{x〔v〕:v=0,1,2,…}か ら加 速 さ れ た 数 列 を計算 す るに は,x〔v〕(≡a)に 対 し の二 つ の数 値 が あれ ば よ い 。 な ぜ な ら とす れ ば,を つ か っ て,加 速 さ れ た 値y〔v〕 が{α,buf, Del}の 三 つ の み か ら 得 ら れ る 。 ゆ え に,x〔v〕 を 計 算 し な が ら 同 時 にy〔v〕 を 得 る に は,図4の よ う に す れ ば よ い 。 M次 元 ベ ク ト ル 列{x〔v〕:v=0,1,2,…}に つ い て 図4数 列 頭 の とこ れ をエ イ トケ ン加 速 して得 ら れ る 数 列y〔v〕の を 同 時 に 計 算 す る アル ゴ リズ ム のPAD表 現
Fig. 4. PAD representation of the algo
rithm to calculate both x(v) and accerelat
ed y(v) simultaneously.
も,そ の 要 素 の 数 列{x(k)〔v〕:v=0,1,2,…}(k=1∼ M)を それ ぞれ 独 立 な数 列 と み な し て,独 立 に 加 速 す る こ とに よ り{y(k)〔v〕:v=2,3,4,…}(k=1∼M)が 得 られ る 。 た だ し,ベ ク トル列 に 対 し その ベ ク トル 要 素 間 の 相 互 作 用 を 考 慮 し,{y(k)〔v〕}の 計 算 に {x(k)〔v〕}のみ で な く,他 の ベ ク トル 要 素 の 値 も使 用 し て,加 速 さ れ た ベ ク トル 列 を 得 る 方 法 も存 在 す る(10)。し か し,こ の 方 法 は,一 つ の ベ ク トル 要 素 の 加 速 計 算 に,他 の す べ て のベ ク トル 要 素 を必 要 とす る た め,こ れ を各 ベ ク トル要 素 に つ い て 並 列 処 理 す る の は,必 要 とな る通 信 量 の 点 か らか な り照 難 で あ る。 前 述 の よ うに,ベ ク トル要 素 ご とに 独 立 にエ イ トケ ン加 速 を す る場 舎,当 然 なが ら この加 速 演 算 は,ベ ク トル要 素 ご と に並 列 に行 え る。 と こ ろ で,数 列{x〔v}お よ び それ を エ イ トケ ン加 速 し た数 列{y〔v〕}そ の もの は 必 要 な く,そ れ ら の 極 限 値 α(た だ し,α ∈x[v→∽ 〕=y〔v→00〕;y〔v〕 は x〔v〕を加 速 した も の で あ り,極 限 値 は 同 じ で あ る) の み が 要 求 され る場合,す な わ ち収 束 の様 子 を知 る必 要 が な く,収 束 値 の み が求 め ら れ る と き に は,数 列x 〔v〕お よびy〔v〕 を保 存 して お く必 要 はな い。 数 列 の収 束 判 定 は,図4の 点 線 部 分 で行 え るか ら, 収 束 値 の み 必 要 な 場 合,図4中 の{buf,Delお よ び temp}の 三 つ の 変 数 の み を 更 新 しな が ら保 存 し て お け ば よ く,{α,D1,D2,お よ びb}はvに つ い て の 各 反 復 ご とに計 算 す れ ば よい 。｜b-temp｜<ε を満 た した と き の δの 値 が 収 束値 で あ る 。 こ こで 重 要 な 点 は,収 束 値 の み が必 要 な 場 合,上 記 の よ うに エ イ トケ ン加 速 を行 うの に必 要 な メ モ リー 数 は,x〔v〕の を保 持 す る変 数 α を 含 め て{(buf, Del, temp),(α, D1,D2,b),お よ び ε}の計 八 つ で十 分 で あ る とい う点 で あ る。 これ は, 各 ノー ドに対 応 す るす べ ての プ ロ セ ッサ 内 にエ イ トケ ン加 速 専 用 の 回路 を付 加 す る場 合,加 速 専 用回 路 が 必 要 と す る面 積 が そ れ ほ ど大 き くな らず に す む こ とを意 味 す る。 <4・3>エ イ トケ ン加 速 の 実 際 の適 用 に つ い て 実 際 の加 速 計 算 は図5の よ うに して 行 わ れ る。 (1)反 復 に よ って 得 られ る22V個 の 電 圧 修 正 量 を そ れ ぞ れ独 立 な 数 列 とみ な す 点 (2)エ イ トケ ン加 速 は,線 形 反 復 中 に 陰 に行 わ れ,加 速 で得 ら れ る値 は 線 形 反 復 時 に は 利 用 さ れ な い点 の2点 に注 意 さ れ た い 。(2)に つ い て は,加 速 値 を線 形 反復 時 に利 用 す る方 法 も考 え られ る が,そ の 場 合, 全 ノ ー ドで 同 時 に 反 復 中 の2を 加 速 値 で置 き換 え る こ とが 必 要 で あ り,こ の タ イ ミ ング の 決 定 が 問 題 とな 電学論B,111巻8号,平 成3年 873図5一 つ の ノ ー ドで の 処 理 の 流 れ Fig. 5. Process flow in one node.
るた め,ま だ試 み て い な い 。 図5中,④ の 部 分 は 必 ず し も2の:更 新 ご と に 行 う 必 要 は な く,2の 更 新1回 ご と(l:整 数 の 定 数)で も構 わ な い 。 この 場 合 は,(23)式 のλiを(λi)で 置 き 換 えた もの と等 価 とな る。 5.線 形 反 復1回 あ た り の 演 算 時 間 (14)式 にお い て,そ の右 辺 の 計 算 に (2行2列 の 行 列)×(2行1列 ベ ク トル): の 演算 お よ び
(26)
(27)
の(Nhk+1)個 の 項 の加 算 が 行 わ れ る。 こ こ で,(26) 式 に つ い て は ど の プ ロ セ ッサ で も演 算 時 間 は 同 じで あ る が,後 者 の 演 算 時 間 は,Nhkの 値 に よ リ プ ロセ ッ サ ご とに 異 な る。 しか し プ ロ セ ッ サ 全 体 と し て み れ ば,最 も時 間 の か か る プ ロ セ ッ サ(=律 速 プ ロ セ ッ サ)す な わ ち,Nhk=Nhmaxで あ る よ うな プ ロ セ ッサ に よ り線 形 反 復1回 あ た りの 演 算 時 間 が 決 定 され る 。 この 律 速 プ ロ セ ッサ に お い て は,(27)式 の計 算 の た め に (NHmax+1)個 の 項 の 加 算……(28) を行 う必 要 が あ る。 しか し,加 算 に 二 進 木 構 造 を とれ ば,(29)
回 分 の 加 算 時 閥 で 計 算 で き る(ここ で,[x]は,灘 以 上 の最 小 の 整 数 を意 味 す る)。 他 方(26)武 に つ い て は(K,L)の 組 合 せ ご と に4個 の 乗 算 器 と2個 の 加 算 器 を もつ な ら ば,こ れ らを並列 に 動 作 さ せ る こ と に よ り,こ の 演 算 は 時 間 的 に は 〔1回 の 乗 算 と1回 の加 算 〕に要 す る時 間 で で きる。 ゆ え に,以 上 の こ とか ら線 形 反 復1回 あた り 1回 分 の 乗 算 時 間 と……(3 0)(1+A)回 分 の加 算 時 間……(31) が 必 要 な こ とが わ か る。 た だ し,加 速 演 算 に 関 して は,図5に あ る とお り各 ノ ー ドプ ロ セ ッサ 内 にエ イ トケ ン加 速 用 の回 路 を別 に 作 っ て お き,加 速 され た 数 列 の変 化 が 全 ノー ドであ る 値 以 内 に な っ た ら割 込 み を か け て,次 のNRス テ ッ プ に移 る と い う形 を 想 定 し て い る。 この場 合,加 速演 算 が線形 反 復 演 算 と は独 立 に(=並 列 に;た だ しデー タ の依 存 は あ る)行 え る こ とを利 用 して い るの で,加 速 に よ る演 算 量 また は演 算 時 間 の 増加 は 考 え な くて も よ い。 6.他 の 並 列 解 法 との 演 算 量 に 関 す る比 較 本 章 で は,他 の 並 列 解 法 との演 算 量 の 比較 を行 う。 た だ し,文 献(3),(5)な どの解 法 で は演算 量 が ブロ ック 分 割 に依 存 し,一 意 的 に 定 ま らな い の で,帯 行列 の帯 幅 の下 限 を与 えれ ば演 算 量 の 下 限 が 一意 的 に定 ま る文献(2)の 解 法(以 後,並 列 直 接 解 法 と呼 ぶ こ とに す る)を 比 較 対 象 とし て選 ん だ 。並列処理 に よる電 力潮流計算の高速化
<6・1>並 列 直 接 解 法 で 必 要 な演 算 数 文 献(2) の並 列直 接 解 法 で は,前 処 理 の オ ー ダ リン グ に よ り行 列 を 帯 幅8の 帯 行 列 に し た の ち,半 帯 幅m〔≡(B +1)/2〕 に 対 し,m2ま た はm個 の プ ロ セ ッサ を用 い てLU分 解 に よ る 直 接 解 法 を行 う。 この 際 に必 要 な 演 算量 は,行 列 サ イ ズ を η とし た と き近 似 的 にm 2個 の 場合:(LU分 解 お よび 前 進 ・後 退 代 入 に) 6(n-1)回 の 乗 除 算 と……(32) 5(n-1)回 の加 算:……(33) m個 の場 合:(同 上) (n-1)(m+4)回 の 乗 除 算 と……(34) (n-1)(m+3)回 の加 算……(35) で与 え られ る 〔詳 細 は 文 献(2)中 の 表1参 照〕。 た だ し,ハ ー ドウ ェ ア を汎 用 で な く専 用 化 す る こ とに よ り, デ ー タ転 送 所 要 時 間)《(浮 動 小 数 演 算 時 間) とす る こ とが 直 接 ・反 復 ど ち らの解 法 に対 し て も可 能 であ る と考 え られ る こ とか ら,以 下 の 議 論 で は デ ー タ 転送所 要 時 間 を 考 慮 し て い な い。 〈6・2>並 列 直 接 解 法 と並 列 反 復 解 法 の 例 題 系 統 で の比 較 図6∼ 図8は 各 々,文 献(11)の{39,118 お よび283}ノ ー ド系 統 に 対 し,NR法 の フ ラ ッ トス ター ト時 にお け る連 立一 次 方 程 弐 に反復 解 法(や エ イ トケ ン加速)を 適 用 し た結 果 を 示 す 。 た だ し,単 精 度 での加 速 演 算 は けた 落 ち の た め う ま くで きな い こ とか ら,計 算 は倍 精 度 で 行 っ た。 図6∼ 図8よ り,エ イ ト ケン加 速 が か な りの 効 果 を もつ こ とが わ か る。 図639ノ ー ド系 統 で の シ ミ ュ レ ー シ ョ ン 結 果Fig. 6. Result of simulation for 39-node system.
図7 118ノ ー ド 系 統 で の シ ミ ュ レ ー シ ョ ン 結 果
Fig. 7. Result of simulation for 118-node system.
図8283ノ ー ド系 統 で の シ ミ ュ レ ー シ ョ ン 結 果
Fig. 8. Result of simulation for 283-node system. 解 くべ き 式:Jz=wに 対 し,v回 目 の 近 似 値 をz 〔v〕とお き,近 似 解 に よ る ミス マ ッチ を
(36)
とす る。 図 の 縦 軸 に は,ミ ス マ ッ チベ ク トル の ノル ム (‖⊿w〔v〕‖)の対 数 を と り,横 軸 は 反 復 回 数vで あ る (ただ し ノル ム は最 大 絶 対 値 ノル ム を用 いた)。 τM≡(浮 動 小 数 乗 算 所 要 時 間) τa≡(浮動 小 数加 算 所 要 時 間) と し た と き,一 般 に はτa≦τMで あ る が,こ れ らの 値 は ハ ー ドウ ェ ア に よ っ て か な り変 わ るた め, (i)τa<<τMお よ び (ii)τa=τM 電 学 論B,111巻8号,平 成3年 875表1三つ の モ デ ル 系 統 の ノ ー ド数(N) な どの 値.
Table 1. Number of nodes etc for 3 model systems. の二 とお りの ケー ス を考 え る。 (i)の と き,m2個 の プ ロ セ ッ サ を用 い た 並 列 直 接 解 法 で の 演 算 量(≡DM)の は,(32)式 よ り
(37)
で 与 え られ,〃3個 の プ ロセ ッサ の 場 合 の そ れ(≡dM )は(34)式 よ り(38)
で 与 え ら れ る 。 ま た,(ii)の と き,m2個 の プ ロ セ ッ サ を 用 い た 並 列直 接 解 法 で の 演 算 量(≡Da)は,(32)+(33)式 よ り(39)
で 与 え ら れ,m個 の プ ロ セ ッ サ の 場 合 の そ れ(≡da) は(34)+(35)式 よ り(40)
で 与 え られ る。 上 記 の直 接 解 法 に 対 し並 列 反 復 解 法 で は,(i)の 場 合,(30)式 よ り反 復1回 あ た り1回 の 演 算 とみ な せ る。他 方(ii)の 場 合,(30)+(31)式 よ り反 復1回 あ た り(A+2)回 の 演 算 を要 す る。 これ ら を踏 ま えて(37) ∼(40)式 を ,反 復 計 算 にお け る 反復 回 数(以 下 の 式 の 左 辺)に 換 算 す る と,(41)
とな る こ とが わ か る。 図 中{(DM,dM),(Da,da)}は こ れ ら の値 を 示 して い る。 並 列 直 接 解 法 と並 列 反 復 解 法 との 比 較 は,連 立 一 次 方 程 式 の解 に 要 求 され る解 の 精 度 が,図 中 の(DM,dM)や(Da,da)の 線 と加 速 後 の ミ スマ ッチ の ノ ル ム の 曲 値)線 との 交 点 よ り上 に あ る (=反 復 解 法 の ほ うが 高 速)か,下 に あ る(=直 接 解 法 の ほ うが 高 速 〉 か に よ り行 う こ とが で きる。 図6∼ 図8か ら,Daま た はDMの 線 と交 わ る と き の 加 速 後 の ミス マ ッチ の 誤 差 ノル ム は,{39,118お よ び283}ノ ー ド系 統 に 対 し 各 々 約{(102.810-0.4),(10-1.6 10-0.4)お よ び(10-0.810-0.4)}で あ り,・daま た はdM の 線 と 交 わ る と き の そ れ は,同 様 に 各 々 約{(103.0 10-7.2),(10-5.810-12.8)お よ び(10-2.210-6.8)}で あ る 。 上 記 の ・τas《τM,また は ・τa=τMと い う場 合 分 け は 両 極 端 に相 当 し,実 際 の 範 とτMの 関 係 が これ ら の 中 間 に位 置 す る と考 え る な ら ぼ,上 の 添 字aとMは, 換 算 反 復 回数 に対 す る下 限 と上 限 を与 え る もの とみ な せ る 。 連 立 一 次 方 程 式 の 解 に要 求 さ れ る解 の 精 度 が ミ ス マ ッチ に お け る10-4の 誤 差 以 内 とす る な ら,上 記 の 値 か ら,三 つ の 例 題 系 統 に 対 し て は 並 列 反 復 解 法 は,m2個 の プ ロ セ ッサ を 用 い た 並 列 直 接 解 法 に は 劣 るが,m個 の プ ロ セ ッサ を 用 い た 並 列 直 接 解 法 と同 程 度 以 上 に高 速 に,潮 流 計 算 に お け る連 立 一次 方 程 式 を解 くと期 待 で き る とい え る。 た だ し,半 帯 幅 解 と して は,そ の下 限 の値 と して mmin=Nhmax+2; Nhmaxが 偶 数 の と き =Nh max+3;Nhmaxが 奇 数 の と き で 与 え た。 実 際 に はm≧mminで あ り(38),(40)式 か らdの 値 は も う 少 し 大 き く な り得 る 点 を注 意 して お く。 表1にN,mminな どの 値 を示 す 。 7.考 察 提 案 し た並 列 反復 解 法 の特 徴 を挙 げ る と以 下の よ う にな る。 (1)系 統 を プ ロセ ッサ ネ ッ トワー ク に直 接写 像 す る点:近 接 作 用 が 利 用 で きる 。 (2)反 復 行 列 の 作 り方=2×2ブ ロ ッ クの 利 用: γ 行 列 の 優 対 角 性 の保 存,お よ びH行 列 の計 算 が ノ ー ドご とで独 立 に可 能。 (3) エ イ トケ ン加 速 の 各 ノー ドで の利 用:線 形 反 復 に よ る近 似 解 が 各 ノ ー ドで 各 々 反 復 行 列 固 有値 の べ き乗 和 に な って い る こ と に基 づ く。 図6∼ 図8は,初 め のNRス テ ッ プ に お け る連 立 一 次 方程 式 につ い て示 した もの で あ り,2回 目以降 の NRス テ ッ プ に つ い て は,近 似 解 が 真 の解 に 近 づ くこ とに よ り,ミ ス マ ッ チ ノ ル ム の 初 期 値 は 小 さ くな る が,一 般 に電 圧 分 布 が フ ラッ ト状 態 か ら離 れ る につれ て,反 復 行 列 の 最 大 固 有 値 お よ び 第 二 最 大 固有 値 は増 大 す る傾 向 に あ る ら し く,図6∼ 図8の よ うな グラ フ で表 現 す る な らば,初 期 誤 差 に 根 当 す る 切 片 が下 に移 勤 す るか わ りに,曲(直)線 の 傾 きは 緩 や か にな り,収 束 が遅 くな る。 また,反 復 解 法 に は反 復 行 列 が収 束 し な い とき は解 が求 め られ な い とい う 欠点 が あ る。 しか並列 処理 による電 力潮流計算の高速化
しこの 反復 行 列 の 収 束 性 に つ い て は,こ の 解 法 で の 反 復行列 は,ヤ コ ビ ア ン行 列Jか ら一 意 的 に 決 ま り,J 行列 は γ 行 列 と(近 似)電 圧 分 布 か ら一 意 的 に 決 定 さ れ る こ とか ら,Y行 列 と電 圧 分 布 の 変 域 を 与 えれ ば 判定 で き る。 更 に,文 献(12)の 手 法 に よ れ ば/行 列 を固 定す る ので,収 束 す る よ うな行 列 に反 復 行 列 を 固 定すれ ば,線 形 反復 に 関 す る 限 り常 に 収 束 可 能 とな る ことが保 証 さ れ る。 な お,文 献(7)は,2×2小 行 列 か ら な る ブ ロ ッ ク 対角行 列 を利 用 した 点 ヤ コ ビ法 をア ル ゴ リズ ム と して 用い る点 で本 論 文 の 手 法 と共 通 して い るが,主 な相 違 点 は以 下 の とお りで あ る。 (1)計 算 対 象(文 献=状 態 推 定/本 論 文=潮 流 計 算) (2)解 法 の 方 針(最 小 二 乗 問 題 と し て/せ ず に 解 く) (3)加 速 方 法(加 速 係 数/エ イ トケ ン加 速) (2)に つ い て,最 小 二 乗 問題 と し て解 く こ とは,行 列が正定 値 化 され る た め,反 復 で の 収 束 が保 証 され る 反面,ノ ー ド間 の 依 存 関 係 が 増 え る。 す な わ ち隣 接 ノ ー ド間 の み で な く,隣 接 ノ ー ド に 隣 接 す る ノ ー ド 鱗 ・隣接 ノー ド)と もデ ー タ の や り と りが 必 要 に な り,プ ロセ ッサ 間 接 続 が 増 大 す る。 あ る い は」 この 隣 ・隣接 ノー ドの や り と り を, 自分〓 隣〓 隣 ・隣 接 と間接 的 に行 い,接 続 を減 らす と すれ ば,通 信 の オ ー バヘ ッ ドが 増 大 す る。 この こ とか ら(2)は, (i)収 束 保 証 の 有/無 を と るか (ii)プ ロセ ッサ 間 接 続 の 大/小 を とる か とい う トレー ドオ フ に お け る選 択 の違 い を 意 味 して い るといえ る。 8.む す び 電力潮 流 計 算 の 高 速 化 の 一 手 法 と して,電 力 系 統 の ネッ トワー ク をそ の ま まプ ロセ ッ サ の ネ ッ トワー ク に 直接写像 す る形 の 並 列 処 理 を想 定 し,NR法 に お け る 連立 一次 方程 式 の 解 法 と して ノ ー ド間 の線 形 反 復 と, これに エイ トケ ン加 速 を加 え る解 法 を考 え,3種 の 例 題系統 に対 し シ ミュ レ ー シ ョ ン に よ り必 要 反復 回 数 な どの測定 を行 い,同 時 に既 に提 案 され て い る連 立 一 次 方程式 の 並列 直 接 解 法 との 演 算 量 に関 す る比 較 を行 っ た。 その 結果 三 つ の例 題 系 統 に対 し て は,並 列 反 復 解 法は連立 一 次 方 程 式 を 帯 行 列 化 し た と き の 半 帯 幅m に対 し 彫2個 の プ ロ セッ サ を 用 い た 並 列 直 接 解 法 に は 劣るが,m個 の プ ロ セ ッ サ を用 い た 並 列 直 接 解 法 と 同程度 以上 に高 速 に,潮 流 計 算 に お け る連 立 一 次 方 程 式 を解 く と期 待 で き る こ とが明 らか とな った 。 本 論 文 は,NR法 に よ る潮 流 計 算 に お け る連 立 一 次 方 程 式 の並 列 処 理 方 法 を述 べ た もの で あ り,逐 次 処 理 で のNR法 の 問 題 点(難 収 束 な ケ ー ス な ど)は 解 決 され て い な い 。従 っ て,難 収 束 な 潮 流 計 算 を いか に並 列 処 理 で対 処 す るか が 問 題 とな る が,系 統 を直 接 写 像 す る手 法 は,ノ ー ドご と に プ ロ セ ッサ を割 当 て る こ と か ら,過 渡 解 析 に お け る発 電 機 ご との 計 算 が 独 立 に で き る な ど,問 題 の も つ並 列 度 を か な り引 出 せ る。 ゆ え に,系 統 解 析 全体 の 高 速 化 の た め に は,直 接 写 像 を利 用 で きる,NR法 以 外 の 潮 流 計 算 ア ル ゴ リ ズ ム の 開 発 が 今 後 の課 題 とな る と考 え ら れ る 。 末 筆 な が ら,本 論 文 作 成 に あ た り御 助 言 を賜 りま し た 筑 波 大 学 構 造 工 学 系 星 野 力 教授 に深 く感 謝 い た し ます 。 (平成2年6月5日 受 付,同3年1月14日 再 受 付) 文 献 (1) 「電 力 系 統 の 安 定 化 技 術 」,電 気 学 会 技 術 報 告(II部)No.238 (昭61-12) (2)北 原,他:「 帯 行 列 形 連 立 方程 式 の 並 列 処 理 に よ る 電 力 系 統 解 析 の 高 速 化 」,電 学 論B,109,205(平1-5)(3) S. Narita, et al.: "A Parallel Processing Algorithm for Fast Load-Flow and Stability Calculations", 7th PSCC, 0.1078 (1981)
(4)佐 々 木:「 電 力 系 統 の静 的状 態推 定 の 並 列 計 算 ア ル ゴ リズ ム に 関 す る一 研 究 一 逆 行 列 補 助 定 理 の 適 用 」,電 学 論B,61, 122(昭61-12)
(5) Han Zhenxiang, et al.: "Parallel Load Flow Algorithm Studies in Power Systems", 9th PSCC, p. 927 (1987) (6) A. Abur : "A Parallel Scheme for the Forward/Backward
Substitutions in Solving Sparse Linear Equations", IEEE Trans. Power Systems, 3, 1471 (1988)
(7) 佐 々 木:「 電 力 系 統 の 静 的 状 態 推 定 に お け る並 列 計 算 アル ゴ リズ ム につ い て の 一研 究 」,電 学 論B,57,101(昭57-12)
(8) J. Ward & H. Hale "Digital computer solution of power flow problems", Trans. Amer. Inst. Elect., Power Apparat us Syst.), 75, 398 (1956-6)
(9)川 合:PADプ ロ グ ラ ミン グ(昭60)岩 波 書 店 (10)伊 理:数 値 計 算(昭56)朝 倉 書 店
(11) North American Rockwell Information Systems Com pany : On-line stability analysis study RP70-1 for the Edison Electric Institute (1970)
(12)岩 本,他:「 非 線 形 性 を保 存 し た 高 速 潮 流 計 算 法 」,電 学 論 B,53,24(昭53-2) 稲 吉 宏 明(非 会 員) 昭 和40年2月20日 生 。62年3 月 筑 波 大 学 第 三 学 群 基 礎 工 学 類 卒 業 。 現 在,同 大 学 院博 士 課 程 工 学 研 究 科 在 学 中。 情 報 処 理 学 会 会 員 。 電学 論B,111巻8号,平 成3年 877
大 澤 靖 治(正 員) 昭 和21年11月25日 生 。46年3 月 京 都 大 学 大 学 院 工 学 研 究 科 修 士課 程 修 了 。 京 都 大 学 助 手(工 学 部), 筑 波 大 学 講 師(構 造 工 学 系),同 助 教 授 を経 て,平 成2年4月 神 戸 大 学 工 学 部 助 教 授 。 工 学博 士 。 主 と して,電 力 系 統 の安 定 度,超 電 導 エ ネ ル ギ ー 貯 蔵 の研 究 に 従 事 。IEEE,低 温 工 学 会,シ ス テ ム制 御 情 報 学 会,エ ネ ル ギー ・資 源 学 会 会 員 。
