著者

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

雑誌

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

巻号頁・発行日

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

---

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

著者

鵜川 始陽 湯淺 太一 小宮 常康 八杉 昌宏

出版者

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

雑誌

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

巻号頁・発行日

vol.42, no.11, pp.25-36, 2001-11-15

参考文献数

12

---

「ぶぶ」は,Java 言語とのシームレスなインタフェースを備えたオブジェクト指向型のScheme 処理系である.Java の機能を最大限に利用しつつScheme を使って対話的にプログラミングができることを目標としており,Scheme の継続機能,Java の例外処理機能の両方に対応していることが望まれる.ぶぶではScheme とJava で記述したメソッドを相互に呼び出し合うことができる.Scheme部分の実行には専用に確保した制御スタックを使っているが,Java 部分の実行にはJava VM の制御スタックを使っている.したがって,完全なファーストクラスの継続を実現するためには,Java の継続も得なければならない.しかし,Java 言語はこのような手段を提供していない.そこで,継続オブジェクトを生成するときは実行中のScheme 部分だけの継続をヒープに保存しておき,Java 部分の継続はJava VM の制御スタック上に残しておくことにした.継続を呼び出すときにJava 部分の継続が制御スタック上に残っているかどうかを調べ,残っていれば完全な継続呼び出しとして動作する.残っていないときはScheme 部分だけの部分継続として呼び出す.また,Java の例外処理機能をScheme で記述したプログラムでも直接利用できるようにした.この例外処理機能は継続機能と同時に使うことができる."Bubu" is an object-oriented Scheme system with seamless interface to Java. Because the goal of Bubu is to provide an interactive environment of Scheme and draw out maximum functionality of Java, we expect it to support both first-class continuations of Scheme and the exception system of Java. In Bubu, methods written in Java and Scheme can call each other. The control stack for methods in Scheme is implemented by using an array object of Java. On the other hand, methods in Java uses the control stack of Java VM. Therefore, when a first-class continuation is captured, a continuation of Java must be also saved to heap. However, Java does not support this facility. In our proposal, when a continuation is captured, only a continuation of Scheme part is saved to heap and the continuation of Java part is left on the control stack of Java VM. When the continuation is called, whether the continuation of Java part is left on the stack of Java VM or not is checked, and if left, this call works as a traditional continuation call. If not, this works as a partial continuation call which has only the Scheme part. In addition, we developed a seamless interface to the Java exception system which can cooperate with the continuation facility.

著者

皆川 宜久 鵜川 始陽 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.11, pp.71-71, 2005-08-15

---

継続とは,計算のある時点の残りの計算である.Scheme では,これをファーストクラスのオブジェクトとして扱え,コルーチンやマルチスレッドなどの機能を実現するのに有用である.ML 言語において一級継続の機能を搭載した処理系としては,Standard ML of New Jersey がある.この処理系はスタックを用いず関数フレームをすべてヒープ領域に割り付けているため,定数オーダの時間で継続の生成を実現している.しかし,一般に関数フレーム生成時にスタックを用いた方が,高速であり,メモリ効率も良い.本研究では,スタックを用いているML 処理系に対し,一級継続の実装を行った.この場合,継続の生成時にスタックの内容をヒープにコピーするスタック法が一般的である.実際,スタックを用いたScheme 処理系で多く採用されている.この方法は動作が単純で実装しやすいなどの利点がある.一方,継続生成のたびにスタックのコピーが行われるので,生成時間,メモリ効率の点などで効率が悪いことがある.そこで本研究では,その効率化手法である遅延スタックコピー法を採用した.この手法は,継続を使用したプログラムの効率を高める一方,オブジェクトの生成時や代入時にオーバヘッドが存在するという欠点がある.そこで,コンパイル時にML の型情報を利用して,そのオーバヘッドを軽減する手法を提案し,実装,評価を行った.A continuation is the remaining task at a point in a computation. In Scheme, a continuation can be captured as a first-class object. This is useful for implementing coroutines and multi-threading. Standard ML of New Jersey is an implemenation of ML with first-class continuations. This system allocates all activation records into the heap, and this feature allows capturing continuations in constant order time. In general, however, a stack is more efficent in terms of execution time and memory space to allocate activation records. We implemented first-class continuations in a stack-based ML system. In order to implement first-class continuations, we adapted the stack strategy which is used in many stack-based implementations of Scheme. With this strategy, the entire stack contents are copied into the heap whenever a continuation is captured. This strategy is simple and easy to implement, but capturing continuations requires a lot of time and memory space. Thus, we employed the lazy stack copying strategy, which is based on the stack strategy but more efficent. While this strategy is useful when creating continuations, there is an overhead when creating and modifying objects. We propose a technique to reduce this overhead by using the type information of ML at compile time, and we applied this techinique to the ML system and evaluated it.

著者

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

出版者

情報処理学会

雑誌

情報処理学会論文誌プログラミング(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.42, no.11, pp.96-96, 2001-11-15

---

Evaluation Strategyとは,並列プログラムを記述する一手法で,アルゴリズムと動的な振舞を分けてプログラムを記述することを可能にする.これはlazyな言語であるHaskellで提案されている手法である.遅延評価は評価する式を動的に決定するため,式の評価順序は不定である.しかし,評価要求を与えることによってそれを制御することは可能であり,Evaluation Strategyはこれを利用している.本発表ではこの手法をStrictな言語であるSchemeに導入する.導入にあたっては,Schemeに遅延評価の仕組みが必要である.Schemeにはdelay,forceがあり,これらを用いた遅延評価を実現することは可能であるが,プログラムの至るところに埋め込む必要があり,エレガントな手法ではない.本発表ではSchemeの言語機能として遅延評価系を導入し,そのインタフェースを用意することで遅延評価を容易に利用できる仕組みを提案する.それによって,Scheme上でEvaluation Strategyを実現する.Evaluation Strategy is a method to describe parallel programs, which enables us to describe the dynamic behavior of a program separately from the algorithm. It is proposed for a lazy programming language, Haskell. Since lazy evaluation dynamically decides which expression should be evaluated next, the evaluation order depends on execution. However, it is controllable by giving evaluation request to expressions and Evaluation Strategy uses this gauge, Scheme. For this purpose, it is necessary to introduce lazy evaluation mechanism into Scheme. Since Scheme has delay and force, we could construct lazy evaluation by using them. But we have to insert delay and force all over a program and it is not an elegant way. In this presentation, we propose to introduce lazy evaluator into Scheme and to provide lazy and touch as the interface to use it easily. Using this mechanism, we implement Evaluation Strategy on Scheme.

著者

湯淺 太一 近山 隆 上田 和紀 森 眞一郎 八杉 昌宏 小宮 常康 五島 正裕

出版者

京都大学

雑誌

特定領域研究

巻号頁・発行日

2001

---

本研究では,計算機システムが備えている広域性と局所性の両方に対応できる適切な計算量モデルとソフトウェアシステムの構築を可能にするために,計算連続体と呼ぶ概念に基づいて,さまざまな観点から,計算に関する既存概念の再検討,統合,および発展を図ってきた.主要な研究成果は次のとおりである.1.計算連続体モデルによる計算量解析本プロジェクトでは,単一計算機内のメモリ階層から計算機間のネットワーク遅延の差異までを,統一的に,かつ簡潔に表現できる計算量モデルとして「計算連続体モデル」を提案し,このモデルに基づいた計算量解析結果が,従来方法よりも現実の計算に近いものであることを示した.また,複雑な並列アルゴリズムに対しても,その振舞いが把握できるように,計算連続体モデルの仮想機械を設計し,実装した.2.並行言語モデルLMNtalに関する研究また本プロジェクトでは,階層グラフの書換えに基づくスケーラブルな並列言語モデルとしてLMNtalを設計し,このモデルの改良を進めてきた.このモデル上でプロセス構造の解析技術を確立するとともに,実用に供するプログラミング言語としての実装を行った.階層グラフ書換えは,多重集合書換え計算モデルや自己組織化に基づく計算モデルなどを特別な場合として含んでおり,既存の多くの計算モデルの架け橋となることが期待できる.3.局所性を重視した処理系実装方式の研究プログラミング言語の実装において,特に局所性を重視することによって,実行性能が飛躍的に向上することを実証した.その例として,階層的グループ化に基づくコピー型ごみ集めによる局所性改善をあげることができる.これは,スタック溢れに備えたキューを併用することにより,少量のスタックで大部分を深さ優先順にコピーするごみ集め方式のさらなる改良の提案であり,仮想記憶の局所性だけでなく,キャッシュの局所性も考慮した実装となっており,実際の計算機上で極めて効率の良い処理系を実現できる技術である.

著者

鵜川 始陽 皆川 宜久 小宮 常康 八杉 昌宏 湯淺 太一

雑誌

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

巻号頁・発行日

vol.44, no.SIG13(PRO18), pp.72-83, 2003-10-15

---

実行にスタックを利用している処理系でファーストクラスの継続を生成する場合,スタックの内容をヒープにコピーするのが一般的である.スタックの内容をヒープにコピーする戦略には様々なものが提案されているが,実際の処理系の多くはスタック法を採用している.スタック法では継続の生成のたびに処理系のスタック全体の内容をヒープにコピーする.このように,スタック法は動作が単純なので簡単に実装でき,また他言語呼び出しをサポートした処理系でも利用できるという長所がある.しかし,継続の生成に時間がかかり,また,メモリ効率が悪いという欠点があり,利用の妨げとなる場合もある.本発表では,スタック法による継続の生成に対する効率化手法として,スタックのコピーの遅延を提案する.継続の生成によりコピーされるスタックの内容は,継続を生成した関数からリターンするまでスタック上にも残っている.したがって,スタックのコピーを継続を生成した関数からリターンするまで遅らせてもよい.もし,生成した継続が,スタックをコピーする前にごみになれば,スタックのコピーを省略できる.本発表では,さらに,スタックコピーの遅延により可能となる,継続オブジェクトの部分的共有も提案する.これらの効率化手法をScheme処理系に組み込んで性能を評価したところ,継続を使ったプログラムの実行効率が改善された.

著者

湯淺 太一 中川 雄一郎 小宮 常康 八杉 昌宏

雑誌

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

巻号頁・発行日

vol.41, no.SIG09(PRO8), pp.87-99, 2000-11-15

---

Lispなどの大多数のリスト処理システムでは,不用セルを回収するためにごみ集め(GC)が行われる.一般的に採用されているGCは,ごみ集めの間プログラムの実行が中断されるので実時間処理には適さない.この問題を解決するために,ごみ集めの一連の処理を小さな部分処理に細分化し,プログラムの実行と並行してごみ集め処理を少しずつ進行させる実時間方式のGCが提案されている.代表的な実時間GCであるスナップショットGCは,スタックなどのルート領域から直接指されているセルをGC開始時にすべてマークしておかなければならない.この間の実行停止時間は,ルート領域の大きさによっては,無視できなくなる.そこで,関数からのリターン時にマーク漏れがないようにチェックすることで,スタックから直接指されているセルを関数フレーム単位でマークする方法を提案する.スタック上のルート領域をフレーム単位でマークしていき,ある関数からリターンする際に次の関数フレームがマークされているかどうかをチェックし,マークされていなければその関数フレームをマークしてからリターンする.これをリターン・バリアと呼ぶことにする.ルート領域のマークが終了したら,従来のスナップショットGCと同様に残りのセルをマークする.本論文では,Common Lisp処理系KCL(Kyoto Common Lisp)上でリターン・バリアを実装し,GCによる実行停止時間について,従来のスナップショットGCと比較評価および検討を行った.

著者

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

雑誌

情報処理学会論文誌プログラミング(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.44, no.13, pp.72-83, 2003-10-15

---

実行にスタックを利用している処理系でファーストクラスの継続を生成する場合,スタックの内容をヒープにコピーするのが一般的である.スタックの内容をヒープにコピーする戦略には様々なものが提案されているが,実際の処理系の多くはスタック法を採用している.スタック法では継続の生成のたびに処理系のスタック全体の内容をヒープにコピーする.このように,スタック法は動作が単純なので簡単に実装でき,また他言語呼び出しをサポートした処理系でも利用できるという長所がある.しかし,継続の生成に時間がかかり,また,メモリ効率が悪いという欠点があり,利用の妨げとなる場合もある.本発表では,スタック法による継続の生成に対する効率化手法として,スタックのコピーの遅延を提案する.継続の生成によりコピーされるスタックの内容は,継続を生成した関数からリターンするまでスタック上にも残っている.したがって,スタックのコピーを継続を生成した関数からリターンするまで遅らせてもよい.もし,生成した継続が,スタックをコピーする前にごみになれば,スタックのコピーを省略できる.本発表では,さらに,スタックコピーの遅延により可能となる,継続オブジェクトの部分的共有も提案する.これらの効率化手法をScheme処理系に組み込んで性能を評価したところ,継続を使ったプログラムの実行効率が改善された.In order to capture first-class continuations, most stack-based implementations copy contents of the stack to the heap. While various implementation strategies for copying are proposed, most implementations employ the stack strategy. With this strategy, the entire stack contents are copied to the heap whenever a continuation is captured. This simple strategy is easy to implement and can be used for implementations with foreign language interface. However, continuations with this strategy spend a lot of time and memory for their creations and invocations, and this week point often discourages programmers from using first-class continuations. We propose a lazy stack copying technique. The contents of the stack to copy will be preserved on the stack until returning from the function that is capturing the continuation. So we delay stack copying for a continuation until the function returns. We can avoid stack copying if it is detected that the continuation became a garbage before the function returs. In addition, we propose another technique, partial sharing of the copied stack, which is realized by using the lazy stack copying technique. We applied these techniques to Scheme interpreters and found that the proposed techniques improve runtime and memory efficiency of programs that use continuations.

著者

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

出版者

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

雑誌

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

著者

湯淺 太一 中川 雄一郎 小宮 常康 八杉 昌宏

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.9, pp.87-99, 2000-11-15

被引用文献数

8

---

Lispなどの大多数のリスト処理システムでは,不用セルを回収するためにごみ集め(GC)が行われる.一般的に採用されているGCは,ごみ集めの間プログラムの実行が中断されるので実時間処理には適さない.この問題を解決するために,ごみ集めの一連の処理を小さな部分処理に細分化し,プログラムの実行と並行してごみ集め処理を少しずつ進行させる実時間方式のGCが提案されている.代表的な実時間GCであるスナップショットGCは,スタックなどのルート領域から直接指されているセルをGC開始時にすべてマークしておかなければならない.この間の実行停止時間は,ルート領域の大きさによっては,無視できなくなる.そこで,関数からのリターン時にマーク漏れがないようにチェックすることで,スタックから直接指されているセルを関数フレーム単位でマークする方法を提案する.スタック上のルート領域をフレーム単位でマークしていき,ある関数からリターンする際に次の関数フレームがマークされているかどうかをチェックし,マークされていなければその関数フレームをマークしてからリターンする.これをリターン・バリアと呼ぶことにする.ルート領域のマークが終了したら,従来のスナップショットGCと同様に残りのセルをマークする.本論文では,Common Lisp処理系KCL(Kyoto Common Lisp)上でリターン・バリアを実装し,GCによる実行停止時間について,従来のスナップショットGCと比較評価および検討を行った.Garbage collection (GC) is the most popular method in list processing systems such as Lisp to reclaim discarded cells. GC periodically suspends the execution of the main list processing program. In order to avoid this problem, realtime GC which runs in parallel with the main program so that the time for each list processing primitive is bounded by some small constant has been proposed. The snapshot GC, which is one of the most popular realtime GC methods, has to mark all cells directly pointed to from the root area at the beginning of a GC process. The suspension of the main program by this root marking cannot be ignored when the root area is large. This paper proposes ``return barrier'' in order to divide the process of root marking into small chunks and to reduce the suspension time of the main program. The root area on the stack is marked frame by frame each time a new cell is requierd. When a function returns, the garbage collector checks if cells pointed to from the frame of the caller function have been already marked, and marks them if not. After marking all cells directly pointed to from the root area, other cells are marked as in the original snapshot GC .In this paper, we implemented the snapshot GC equipped with the return barrier in KCL (Kyoto Common Lisp). We compare and discuss the suspension times of this GC and the original snapshot GC.

著者

森住 大樹 小宮 常康 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.45, no.12, pp.94-94, 2004-11-15

---

実時間処理を妨げる要因の1 つとしてごみ集めがあげられる.ごみ集めが一括して行われる場合には,その間プログラムの実行は一時的に停止することとなり,実時間処理の妨げとなる.この問題に対処するため,実時間処理に対応したごみ集めも考慮されているが,Real-Time Specification forJava(RTSJ)では,ごみ集めの方式自体には制限を加えることなく,実時間処理を可能としている.Lisp もごみ集めの機能を持つプログラミング言語の1 つである.本発表では,RTSJ の方法を取り入れることによって実時間処理にも利用できるように設計,実装したLisp を紹介する.具体的には,従来のヒープとは別にスコープメモリと呼ばれる実時間処理用のメモリ領域を導入する.スコープメモリはごみ集めにより使用済みのメモリ領域を回収するのではなく,ある程度の大きさでまとめて確保し,必要がなくなったら一度に破棄する.細かいメモリ管理の手間が必要なく,使用中のデータの破棄やメモリリークの恐れもない設計となっており,ごみ集めの利便性を損なうこともない.実装にあたっては,Java により記述されたScheme 処理系であるJAKLD とRTSJ を満たすJava 処理系を組み合わせることにより,効率良く実装を行うことを可能とした.Lisp に新たに追加する機能はRTSJ のJava 処理系にも含まれるものであり,実装ではJAKLD を改良しJava の機能を有効利用した.また,JAKLD を基に作成されたL 処理系に対しても,設計と実装を行った.実装されたLisp 処理系は,それ自身十分に動作するものであり,また,より高性能の本格的な処理系を作成する際に参考となりうるものでもある.Design and Implementation of Lisp System with Memory Management suitable for Real-Time Processing. Garbage collection (GC) is one of the factors obstruct real-time processing. In case that GC is executed at a time, it stops temporarily execution of program and obstructs real-time processing. For the purpose of dealing with this problem, GC corresponding to realtime processing are devised, but Real-Time Specification for Java (RTSJ) realizes real-time processing without adding restrictions to a method of GC itself. Lisp is one of programming languages with GC. At this presentation, we introduce Lisp which is designed and implemented for real-time processing by taking in the method of RTSJ. Specifically, the memory area called scope memory for real-time processing is introduced apart from the conventional heap. At a scope memory area, GC does not collects used memory, but a certain size memory is secured at a time and deleted at a time if it is not necessary. Because it is designed not to need complicated work for memory management and not to concern about deletion of necessary data and memory leak, the convenience of GC is not spoiled. It made the implementation efficient to combine JAKLD which is a Scheme system described by Java and a Java system of RTSJ. The function newly added to Lisp is included also in a Java system of RTSJ, and the function of Java was available at the implementation by improving JAKLD. We also designed and implemented to L system created from JAKLD. The implemented Lisp system works enough in it self, and it may also be referred when a more highly efficient system is created.

著者

米田 匡史 鵜川 始陽 花井 亮 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.47, no.11, pp.38-49, 2006-07-15

---

リージョン推論と呼ばれる静的にオブジェクトの寿命を見積もる手法に基づくメモリ管理が,Tofteらによって提案されている.リージョン推論に基づくメモリ管理では,オブジェクトはリージョンと呼ばれるメモリブロックのいずれかに生成される.リージョンは特定のスコープを抜けると解放され,そのリージョン内に生成されたオブジェクトも同時に解放される.そのため,再帰呼び出しのように,関数呼び出しが連続する場合にはリージョンの解放ができない.Tofteらの処理系では,今後の計算においてアクセスされる可能性のあるオブジェクトが入っていないリージョンにオブジェクトを生成する際に,そのリージョンに入っているオブジェクトに上書きして生成しようとしている.しかし,関数がリージョンをリージョン変数に受け取ることができるため,リージョン変数のエイリアスが生じ,静的にオブジェクトを上書きしてもよいと判定できる箇所が限られる.本論文では,問題となるエイリアスが存在するかどうかを,実行時にオブジェクトを生成する際に調べる手法を提案する.これにより,Tofteらの手法では上書きしてよいか分からなかったオブジェクト生成の箇所で,より厳密に判定できるようになる.その結果,メモリ効率が向上し,これまで妥当なメモリ使用量で動かなかったプログラムが動くようになると期待される.A technique for memory management based on region inference, which statically estimates the life-time of objects, was proposed by Tofte, et al. With this technique, objects are created in one of the memory blocks, called regions. Each region is deallocated when the control flow exits its corresponding scope and all objects in the region are deallocated at that time. This means that systems cannot deallocate regions while function calls are repeated without returning. This often happens in the case of recursive function calls. Tofte implemented a system which creates a new object by overwriting existing objects in a region if the region has no object that might be accessed in the rest of the computation. However, there are not a few points of object creation at which his static analysis cannot find it possible to overwrite. This is because functions may receive regions as region variables and there may be aliases of region variables. In this paper, we propose a technique to improve memory usage by checking the existence of problematic aliases at runtime. Our technique can determine exactly whether it is possible to overwrite in many points of object creation where Tofte's analysis fails. As a result, we expect more programs to run with a relatively small amount of memory in region-based systems.