著者

諏訪 将大 八杉 昌宏 平石 拓 馬谷 誠二

雑誌

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

巻号頁・発行日

vol.9, no.1, pp.15-15, 2016-02-26

---

我々は分散進捗管理のためのシステムとしてメッセージ媒介システム(MMS)を開発している.本発表ではMMS中の不必要なメッセージの削除方法について述べる.MMSは並列アプリケーションや並列言語処理系の開発に有用であり,MMSを介して与えられた計算の部分的計算結果をメッセージとして多数のワーカが交換できる.一部ワーカが障害により停止してもよいような並列分散手法により,MMSは与えられた計算の進捗を管理する.開発の初期段階においては,アプリケーション独自の樹状再帰的計算の一部を表すための可変長アドレスを各ワーカが使ってよいものとしてMMSを設計した.このアプローチで計算速度の向上と耐障害性が達成されたが,書き込まれたメッセージが単調に増え,メモリ使用状況へ大きな影響があった.本研究では不必要なメッセージを削除できるようMMSの設計と実装を変更し,その効果を評価する.

著者

八杉 昌宏 小島 啓史 小宮 常康 平石 拓 馬谷 誠二 湯淺 太一

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.3, no.5, pp.1-17, 2010-12-10

---

Scheme処理系は真に末尾再帰的であることが要求されており,アクティブな末尾呼び出しの数に制限がない場合もサポートしなくてはならない.Clingerは真の末尾再帰の形式的定義の1つを空間効率の点から与えており,その定義に従えば,末尾呼び出しの最適化(末尾呼び出しをトランポリンなどによりジャンプに置き換えて実装する方法)だけでなく,BakerのCPS(継続渡しスタイル)変換を用いたC言語におけるSchemeの実装手法も,真に末尾再帰的と分類できる.Bakerの実装手法は,CPS変換された末尾呼び出しにおいて新たな継続を生成せず,C言語の実行スタックに対してもごみ集めを行うため,空間効率が良い.本論文では拡張C言語による真に末尾再帰的なSchemeインタプリタの実装手法を提案する.本手法はCPS変換を用いず,Cの実行スタックがあふれそうになれば,残りの計算に必要な"Frame"オブジェクトのみを含むリストとして表現された空間効率の良い一級継続を生成し,すぐさまその継続を呼び出すというアイディアに基づく.ごみ集めや継続のキャプチャにおいては,実行スタックに合法的にアクセスできる,つまりデータ構造や変数の値としてアクセスできるL-closureという言語機構を用いている.ベースとなるSchemeインタプリタは,Javaアプリケーション組み込み用LispドライバであるJAKLDをもとにC言語で再実装されたものとした.Implementations of Scheme are required to be properly tail-recursive and to support an unbounded number of active tail calls. Clinger proposed a formal definition of proper tail recursion based on space efficiency. The definition covers systematic tail call optimization, where every tail call is converted to a jump (with an optional trampoline), as well as Baker's implementation of Scheme in the C language with CPS (continuation-passing style) conversion. Baker's implementation is space-efficient, since no new continuation is created on a CPS-converted tail call and garbage is collected even on C's execution stack. We propose techniques to implement a properly tail-recursive Scheme interpreter in an extended C language. Our approach does not convert a program into CPS. The key idea is to avoid stack overflow by creating a space-efficient first-class continuation represented as a list containing only the "Frame" objects necessary for the rest of computation and immediately invoking the continuation. We use a language mechanism called "L-closures" to access the contents of the execution stack as values of legal data structures and variables for implementing garbage collection and capturing continuations. This research is based on a Scheme interpreter which is developed in the C language by referring to an existing Lisp driver called JAKLD that is intended to be embedded in Java applications.

著者

平石 拓 李 暁? 八杉 昌宏 馬谷 誠二 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.1, pp.40-56, 2005-01-15

被引用文献数

2

---

現在,実用的システムの開発にC 言語は欠かせないが,細粒度マルチスレッド機能などを追加するためにC 言語を拡張するのはそれほど容易ではない.言語拡張の実現方式としては,C コンパイラに手を加えるもの以外に,拡張C プログラムを変換し,C コードを生成する方式もある.後者の方式では,最初にプログラムを抽象構文木(AST)に変換し,拡張に必要な解析や変形などを行った後,C コード生成を行うことが多い.AST のデータ構造には従来,構造体,オブジェクト指向言語のオブジェクト,直和型のデータなどが用いられているが,本研究では,AST をS 式で表現し,それをそのままプログラムとして用いることを提案する.このため,S 式ベースの構文を持つC 言語,SC 言語を設計した.SC 言語では新しいコンストラクトの追加が容易であり,また,S 式は,変換時に便利な動的変数も備えたCommon Lisp 言語を使って簡単に入出力や解析や変形ができるため,言語拡張のrapid prototyping が可能となる.ただし,Common Lisp 言語ではパターンマッチングを直接書くことができないので,本研究では,backquote マクロの記法をパターン部にも用いた変形規則の表記も提案する.このようなSC 言語は他の高水準言語の中間言語として用いることも可能である.本論文では,実際にSC 言語に細粒度マルチスレッド機能を追加した例も示す.The C language is often indispensable for developing practical systems, but it is not so easy to extend the C language by adding a new feature such as fine-grained multithreading. We can implement language extension by modifying a C compiler, but sometimes we can do it by translating an extended C program into C code. In the latter method, we usually convert the source program to an Abstract Syntax Tree (AST), apply analysis or transformation necessary for the extension, and then generate C code. Structures, objects (in object-oriented languages), or variants are traditionally used as the data structure for an AST. In this research, we propose a new scheme where an AST is represented by an S-expression and such an S-expression is also used as (a part of) a program. For this purpose we have designed the SC language, the C language with S-expression-based syntax. This scheme allows rapid prototyping of language extension because (1) adding new constructs to the SC language is easy, (2) S-expressions can easily be read/printed, analyzed, and transformed in the Common Lisp language, which features dynamic variables useful for translation. Since pattern matching cannot be described directly in Common Lisp, we also propose denoting transformation rules with patterns using the backquote-macro notation. Such an SC language can also be used as an intermediate language for other high-level programming languages. This paper also shows a practical example where fine-grained multithreading features are added to the SC language.

著者

安部 達也 平石 拓 三宅 洋平 岩下 武史 中島 浩

雑誌

研究報告ハイパフォーマンスコンピューティング(HPC)

巻号頁・発行日

vol.2011, no.59, pp.1-8, 2011-07-20

---

分散制約充足問題を分散並列計算環境で解くにあたり,ジョブを処理の単位とする分散並列処理 (ジョブ並列) に特化したジョブ並列スクリプト言語 Xcrypt で処理を記述することにより,実際の分散並列計算環境であるところの,いわゆるスーパーコンピュータを利用する方法を紹介する.さらに,Xcrypt の遠隔ジョブ投入機構を利用することにより,制約が遠隔の計算機に分散された状態からの制約充足問題,つまり,真の意味での分散制約充足問題を簡便に取り扱うことができることを示す.We introduce a method of parallel executions based on the job unit (job-level parallel executions) for solving distributed constraint satisfaction problems (DCSPs) in parallel and distributed computation environments, the so-called today's many supercomputers. Throughout introducing the method we use the job-level parallel script language Xcrypt, specific to job-level parallel executions. We also show that Xcrypt provides us with a feature of submitting remotely jobs for solving realistic DCSPs (under the circumstances that constraints are truely distributed in separate computers).

著者

平石 拓

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.50, no.12, 2009-12-15