著者

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

雑誌

情報処理学会論文誌プログラミング(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.

著者

新名 庸生 佐藤 雅彦 馬谷 誠二 八杉 昌宏 湯淺 太一

雑誌

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

巻号頁・発行日

vol.3, no.5, pp.31-31, 2010-12-10

---

プログラミング言語Zには簡潔で厳密なセマンティックが与えられており,将来的にはZで記述したプログラムついてもその数学的,論理的性質を素直に記述,証明できる言語になることを目指している.今回はZのコア言語となるpure Zと,Javaで書かれたLisp処理系JAKLDを基にしたpure Zの実装を紹介する.JAKLDは携帯電話でも動くコンパクトさと改造しやすさからpure Zの実装に適している.今回のpure Zの実装は今後の拡張に備え,コンパクトさと改造のしやすさを引き継いだ実装になっている.The programming language Z is given a simple and strict semantics, and we expect we will be able to easily describe mathematical and logical properties of programs written in Z in the future. In this search, we introduce a core language of Z called pure Z and its implementation based on JAKLD, a Lisp system written in Java. JAKLD is suitable for the purpose because it is so compact that some versions of it runs on mobile phones and designed so that it will be easy to add, delete, and modify its functionalities. Our implementation of pure Z keeps the compactness and easiness for the next extension.

著者

八杉 昌宏 馬谷 誠二 鎌田十三郎 田畑 悠介 伊藤 智一 小宮 常康 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.42, no.11, pp.1-13, 2001-11-15

被引用文献数

4

---

MIMD 型並列計算機における効率の良い並列処理のための,メソッドの実行時置換と構造化されたスレッドによる並列処理を特徴とするオブジェクト指向並列言語OPA を開発している.本論文では,その共有メモリ型並列計算機用のコード生成手法について述べる.コンパイル時には,オブジェクトへのメモリアクセスやコンテキストスイッチ時のメモリアクセスを削減するための解析を行う.また実装方式としては,プロセッサ間通信とスレッドスケジューリングにはlock-free バッファ管理方式,スレッド内スケジューリングには関数フレーム二重表現方式と値ベースサスペンドチェック方式,同期処理には重み付きカウント方式などを用いている.値ベースのチェックにより,1 呼び出しあたり1 分岐命令追加程度のオーバヘッドで高速なコンテキストスイッチを可能とした.We are developing an object-oriented parallel language OPA for effcient parallel processing on MIMD computers,which features dynamic method replacement and structured parallel processing using multiple threads.In this paper,the code generation techniques for shared-memory parallel computers are presented.The compiler performs analyses to reduce the memory access to objects and the memory access on context switches.The implementation techniques include a lock-free buffering method for inter-processor communication and thread scheduling,a double function-frame representation method and a value-based suspension check method for intra-thread scheduling,and an weighted counting method for synchronization.The value-based check enables fast context switches with small overhead for an additional branch instruction per call.

著者

近山 隆 湯淺 太一 上田 和紀 田浦 健次朗 遠藤 敏夫 横山 大作 田浦 健次朗 遠藤 敏夫 横山 大作 馬谷 誠二

出版者

東京大学

雑誌

特定領域研究

巻号頁・発行日

2006

---

爆発的に増加する大量の情報を効率的に扱うソフトウェアの構成には、広域に分散配置した高度な並列性を持つ情報システムを柔軟に記述できるソフトウェアの枠組が基本技術として必要となる。このためのプログラミング言語やミドルウェアのシステムと、複雑なソフトウェアの正当性を検証するためのシステムを対象に研究を進め、具体的なシステムを提案、設計、実装し、その性能を検証した。代表的成果ソフトウェアは公開している。