著者

丸山 真佐夫 山本 繁弘 大野 和彦 中島 浩

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.43, no.3, pp.80-80, 2002-03-15

---

再演実行を基礎とする従来の並列プログラムのデバッギング手法では,バグの原因をたどる過程で,頻繁にプログラムの再実行をしなくてはならない.実行の行き過ぎによる再実行の回数を減らすためには,実行途中でブレークポイント設定が必要になり,ユーザの負担が大きくなる.そこで我々は,再演実行手法に基づきながら,プログラム先頭からの再実行をせずに並列プログラムを過去の状態に戻し,そこから実行を再開することを可能にする"巻き戻し実行"機構を提案する.本提案の巻き戻し実行機構では,並列プログラムを構成する任意のプロセスを,任意の受信イベントの時点に戻すことができ,これを基礎にすべてのプロセスまたは一部のプロセスだけをプログラムの途中から実行させることができる.我々は並列言語Orgel に対して巻き戻し実行機構を実装し,性能評価を行った.その結果通常実行に対して,イベント順序保存実行で7%,巻き戻しのための状態保存実行で13%増という,小さいオーバヘッドで動作させることができた.In debugging a parallel program with conventional replay based method, the programmer has to rerun the program repeatedly from its beginning, because the code the programmer wants to examine next might have already gone beyond the breakpoint. To prevent the program from overrunning, the programmer must set breakpoints with much care in the complicated parallel program. Thus we propose a rollback mechanism, which allows the programmer to rerun the program halfway of it. Using this mechanism, the programmer may rollback any process of the target program to any receive event on its event graph. We applied our rollback mechanism to a parallel programming language named Orgel, and evaluate the overhead of logging and rollback. The result shows that execution time of event logging and computational state saving mode for rollback are only 7% and 13% larger than normal execution respectively.

著者

深野 佑公 山本 繁弘 大野 和彦 中島 浩

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.44, no.2, pp.47-47, 2003-02-15

---

我々は並列言語Orgel の開発を行っている.Orgel は,並行/並列の実行単位であるエージェントをストリームと呼ぶ通信路で結び,明示的なメッセージ送信を行う言語である.Orgel では,プログラマが問題をエージェントという並列実行単位に切り分けることに加え,ストリームによる通信路接続網の構造をすべて宣言的に記述するので,コンパイル時に並列モデルが明確になっており精度の高い静的解析が可能である.本発表では,このOrgel の特徴を生かして,動的なオーバヘッドを最小限にした最適化を行う手法を提案する.プログラム全体の構造および粒度,通信量が完全に把握できれば,すべて静的に最適化することも可能である.しかし,Orgel では再帰的な接続も記述できるため,実際に生成されるエージェント個数および構造は必ずしも静的には決まらない.また,通信対象は分かっても送信するメッセージの個数やエージェントの粒度は実行時にしか分からない.したがって,各プロセッサの処理量が偏らないよう静的に全体をスケジューリングすることは困難である.そこで,コンパイラは静的にエージェントの持つ量的な性質を解析し,エージェント割当てやスケジューリングをするための情報をランタイムに渡す.ランタイムは,この情報をもとにノード数やプロセッサの現在の負荷などを考慮して,負荷が均等になり通信量が多いエージェントは同一プロセッサになるように割り当てる.また,同一プロセッサ内では依存解析等に基づいてスケジューリングを行う.本手法を実装し,14 クイーンを解くプログラムで従来のOrgel ランタイムと性能比較を行った.その結果,従来版と比べ最大1.7 倍の速度向上が得られた.We are developing a parallel language called Orgel.In the execution model of Orgel,a set of agents are connected with abstract communication channels called streams.The agents run in parallel sending asynchronous messages through the streams.In an Orgel program, each unit of parallel execution is speci ?ed as an agent by the programmer.The connections among agents and streams are declaratively speci ?ed.Thus,parallel execution model is clear and the highly accurate static analysis is possible.Utilizing these features,we propose an optimization scheme that minimizing the dynamic overhead.If the complete structure of the whole program is known at compile time,static optimization will be sufficiently effective. However,in Orgel,the number of agents and structures actually generated are not always static,because recursive connection is supported.Moreover,although a communicating pairs of agents are known at compile time,the number of messages and the granularity of agents are known only at runtime.Therefore,it is difficult to balance loads on the processor by whole static scheduling.Thus,in our scheme the compiler outputs an analysis result to instruct the runtime how to allocate and/or schedule an agent when its quantitative attributes are known. Considering the number of processors and the present load of each processor,the runtime uses this information for optimization;it allocates agents balancing loads and minimizing inter-node communication.It also schedules agents on each node considering dependencies. We designed and implemented the system.As the result of evaluation using 14-Queen solver, we obtained 170%speed-up.

著者

山本 繁弘 大野 和彦 中島 浩

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.43, no.3, pp.83-83, 2002-03-15

---

我々は並列言語Orgelの開発を行っている.Orgelは,並行/並列の実行単位であるエージェントをストリームと呼ぶ通信路で結び,明示的なメッセージ送信を行う言語である.Orgelでは,プログラマが問題をエージェントという並列実行単位に切り分けることに加え,ストリームによる通信路接続網の構造をすべて宣言的に記述するので,コンパイル時に並列モデルが明確になっており精度の高い静的解析が可能である.本発表では,このOrgelの特徴を生かして,動的なオーバヘッドを最小限にした最適化を行う手法を提案する.プログラム全体の構造および粒度,通信量が完全に把握できれば,すべて静的に最適化することも可能である.しかし,Orgelでは再帰的な接続も記述できるため,実際に生成されるエージェント個数および構造は必ずしも静的には決まらない.また,通信対象は分かっても送信するメッセージの個数やエージェントの粒度は実行時にしか分からない.したがって,各プロセッサの処理量が偏らないよう静的に全体をスケジューリングすることは困難である.そこで,量的な性質が分かった時点でエージェントを,割当てやスケジューリングできるように,コンパイラは静的解析による結果をランタイムに渡す.ランタイムは,この情報をもとにノード数やプロセッサの現在の負荷などを考慮して,負荷が均等になり通信量が多いエージェントは同一プロセッサになるように割り当てる.また,同一プロセッサ内では依存解析などに基づいてスケジューリングを行う.We are developing a parallel language called Orgel.In the execution model of Orgel,a set of agents are connected with abstract communication channels called streams.The agents run in parallel sending asynchronous messages through the streams.In an Orgel program, each unit of parallel execution is speci fied as an agent by the programmer.The connections among agents and streams are declaratively speci fied.Thus,parallel execution model is clear and the highly accurate static analysis is possible.Utilizing these features,we propose an optimization scheme that minimizing the dynamic overhead.If the complete structure of the whole program is known at compile time,static optimization will be sufficiently effective. However,in Orgel,the number of agents and structures actually generated are not always static,because recursive connection is supported.Moreover,although a communicating pairs of agents are known at compile time,the number of messages and the granularity of agents are known only at runtime.Therefore,it is difficult to balance loads on the processor by whole static scheduling.Thus,in our scheme the compiler outputs an analysis result to instruct the runtime how to allocate and/or schedule an agent when its quantitative attributes are known. Considering the number of processors and the present load of each processor,the runtime uses this information for optimization;it allocates agents balancing loads and minimizing inter-node communication.It also schedules agents on each node considering dependencies.