配列の縮約表現による大規模ワークフローの効率的実装手法  [in Japanese] Efficient Implementation of Large-scale Workflows Based on Array Contraction  [in Japanese]

Access this Article

Search this Article

Abstract

我々は大規模ワークフロー記述用の並列スクリプト言語 MegaScript を開発している.MegaScript はオブジェクト指向言語であり,個々のタスクや通信路であるストリームなどをオブジェクトで表す.このため柔軟な記述が可能である一方,タスク数に応じたオブジェクトが生成されるため,実行可能なワークフローの規模がマスタノードのメモリ量で制約される,スケジューリングやタスク転送のオーバヘッドが大きくなる,といった問題がある.そこで本発表では,配列の縮約表現を用いて等価なワークフローを表すことで,生成されるオブジェクト数を大幅に削減する手法を提案する.本手法はタスク配列など API クラスのメソッド内に実装され,配列の要素アクセスをトリガとして内部の縮約・非縮約表現を動的に切り替える.このためユーザに内部の実装を隠蔽でき,言語インタプリタ本体の変更が必要ない.さらに,サブワークフロー記述用のクラスを導入することにより,階層型の並列性を持つワークフローも効率良く縮約できる.ランダムなワークフローを用いた性能評価の結果,完全に縮約可能な場合はタスク数に依存せず生成される API オブジェクト数を 300 程度,必要メモリ量を 100KB 程度に削減することができた.We are developing a parallel script programming language MegaScript for large-scale workflows. MegaScript is an OOPL and each task and communication channel called stream is represented as an object. Although this feature enables flexible description of various workflows, the same number of objects are created for large amount of tasks. Thus, the execution of large-scale workflows is limited by the memory size of the master node and task scheduling / transfer overheads are increased. Therefore, we propose a scheme largely reducing the number of objects using array contraction. Our scheme can be implemented within the methods of API classes and dynamically shifts internal representation triggered by the access to array elements. Thus, encapsulating internal implementation to the user is possible, and the modification of MegaScript interpreter is not needed. Furthermore, we introduce a new class for subworkflows to contract hierarchically parallel workflows efficiently. As a result of evaluation, the number of API objects in fully-contracted random workflow representations was approximately 300 in average, independent from the number of tasks. The required memory size was also reduced to approximately 100KB in average.

Journal

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

    情報処理学会論文誌プログラミング(PRO) 4(3), 98-98, 2011-06-29

Codes

  • NII Article ID (NAID)
    110008616698
  • NII NACSIS-CAT ID (NCID)
    AA11464814
  • Text Lang
    JPN
  • Article Type
    Article
  • ISSN
    1882-7802
  • Data Source
    NII-ELS  IPSJ 
Page Top