著者

湯淺 太一

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.35, no.1, pp.1_94-1_95, 2018-01-25 (Released:2018-03-26)

著者

山本 晃成 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.42, no.11, pp.37-51, 2001-11-15

---

プログラミング言語の中には末尾再帰の最適化と一級継続を必須としているものがある.たとえばScheme ,Standard ML や他の関数型言語のほとんどがその機能を必要としている.これらの言語は,末尾再帰の効率によるところが大きく,また,継続が操作可能であることが言語の重要な特色でもある.しかし,Java 仮想マシン(JVM )上で末尾再帰の最適化と一級継続を実現することは困難である.これはJVM の仕様がそれらを実現するための機構を十分に提供していないことが要因である.実際に,JVM のバイトコードを出力する様々なコンパイラが実装されているにもかかわらず,JVM の制限のために,言語が要求する完全な機能を実現できていないものが少なからず存在する.そこで,JVM で末尾再帰の最適化と一級継続を実現するために,いくつかのバイトコード命令とその実行を補うためのクラスを拡張することを検討する.様々な拡張方法や実現方法が考えられるが,JVM の基本設計は可能な限り尊重し,最低限の拡張でかつ効果的にこれらの機能を実現可能にすることを目標とする.There are several programming languages that require tail recursion optimization and first-class continuations.Scheme,Standard ML,and several other mostly functional languages require these features.These languages rely heavily on the efficiency of tail recursion,and the ability of controlling continuationsisone of the important features.However, it is difficult to implement tail recursion optimization and first-class continuations on the Java Virtual Machine (JVM),because the JVM specification does not provide features to realize them. Although variouscompilersare implemented that produce JVM byte code,some of them cannot realize full language features because of the restriction of the JVM specification.In this research, we propose byte code extensions and classes to support their execution to realize tail recursion optimization and first-class continuations on the JVM.Although there are various ways to extend it and implement them,we aim at having respect for the basic design of the JVM as far as possible and realizing them efficiently with minimum extensions.

著者

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

出版者

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

雑誌

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

著者

湯淺 太一 京都大学

雑誌

コンピュータソフトウェア = Computer software (ISSN:02896540)

巻号頁・発行日

vol.23, no.4, 2006-10-26

著者

鵜川 始陽 信岡 孝佳 海野 弘成 湯淺 太一

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.29, no.3, pp.3_143-3_156, 2012-07-25 (Released:2012-08-20)

---

ロックやメモリバリア命令の実行には多くのCPUサイクルを消費するため,並行GC(ごみ集め)では,書込みバリアからロックやメモリバリア命令を排除することが容易なインクリメンタルアップデートGCが使われることが多い.しかし,インクリメンタルアップデートGCの通常の実装では,マークフェーズ後にミューテータを止めて多くのオブジェクトをマークする可能性があり,実時間アプリケーションには向かない.本論文では,この処理が必要のないスナップショットGCを使った並行GCを提案する.提案するGCでは,ロックやメモリバリア命令の頻繁な使用を避けるために,ミューテータは書込みの履歴を溜めておいて,GCとハンドシェイクすることで,履歴をまとめてGCに渡す.このGCをDalvik VMに実装し,評価を行った.

著者

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

出版者

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

雑誌

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

著者

湯淺 太一 安本 太一 永野 佳孝 畑中 勝実

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.35, no.11, pp.2392-2402, 1994-11-15

被引用文献数

1

---

SIMD(Single Instruction,Mu1tiple Data)型超並列計算機上で動作する拡張。Common Lisp言語および処理系であるTUPLEについて報告する。TUPLEはSIMD型超並列計算の機能をCommonLispに付加したものである。従来のSIMD型計算機用のLisp言語とは異なり、膨大な数のCommonLispサブセットの処理系が並列に動作するという計算モデルをTUPLEは採用している。この目的のために、ターゲット・マシンの各PF(Processi・Element)は、固有のヒープをその局所メモリに保有する。これらのサブセット処理系を、フルセットのCommonLisp処理系が制御し、ユーザは、フルセット処理系を使って並列プログラムの開発と実行を行う。本稿は、TUPLEの言語と処理系の概要を紹介するとともに、1024台以上のPEを有するSIMD型超並列計算機MasParMP?1におけるTUPLEの実現について触れ、その性能評価結果を報告する。

著者

竹辺 靖昭 湯淺 太一

雑誌

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

巻号頁・発行日

vol.43, no.SIG08(PRO15), pp.98-109, 2002-09-15

---

現在の多くのWeb サイトでは,Web サーバ上で動作するプログラムで,データベースへのクエリを行い,動的にWeb ページを生成する処理が行われている.我々は,部分評価の手法を応用し,こうした動的Web ページの生成を高速化するシステムを開発している.このシステムは,Web サイトの開発において広く使用されているPHP という言語を対象とした部分評価器と,部分評価によって生成されたプログラムをWeb サーバに配置するシステムからなる.この部分評価器は,更新の頻度が低いデータを静的と見なすことにより,これらのデータへのクエリを部分評価時に行うことができる.部分評価および生成されたプログラムの配置は,これらのデータが更新されるタイミングなどで行われる.Web ページを生成する時点では,変換結果に残された動的な部分のみが実行される.これにより,リアルタイムに更新される情報を含むページやパーソナライズ機能を持つページなど,さまざまなタイプの動的Web ページを生成する負荷を低減することができる.本論文では,このシステムで使用している部分評価の手法および実装方法を紹介するとともに,パーソナライズ機能を持つWeb ページなどに対して実際にこの手法を適用した結果を報告する.

著者

湯淺 太一 奥乃 博 尾形 哲也

雑誌

情報処理

巻号頁・発行日

vol.52, no.9, pp.1191-1194, 2011-08-15

著者

西村 祥治 湯淺 太一 八杉 昌宏 小宮 常康

出版者

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

雑誌

情報処理学会論文誌プログラミング(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.局所性を重視した処理系実装方式の研究プログラミング言語の実装において,特に局所性を重視することによって,実行性能が飛躍的に向上することを実証した.その例として,階層的グループ化に基づくコピー型ごみ集めによる局所性改善をあげることができる.これは,スタック溢れに備えたキューを併用することにより,少量のスタックで大部分を深さ優先順にコピーするごみ集め方式のさらなる改良の提案であり,仮想記憶の局所性だけでなく,キャッシュの局所性も考慮した実装となっており,実際の計算機上で極めて効率の良い処理系を実現できる技術である.

著者

小宮 常康 湯淺 太一

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.28, no.3, pp.3_70-3_75, 2011-07-26 (Released:2011-09-26)

著者

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

雑誌

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

巻号頁・発行日

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

---

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

著者

湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.4, pp.1-16, 2003-03-15

参考文献数

21

被引用文献数

2

---

Java 言語によって開発するアプリケーションに組み込んで使用することを主要目的として設計したLisp ドライバを紹介する.設計にあたって重視した点は,(1) Lisp 処理系の実装ノウハウを持たないJava プログラマにも機能の追加・削除・変更が容易に行えること,(2) コンパクトな実装であること,(3) 性能が極端に悪くないこと,などである.これらの条件を満たすために,Java の持つ機能を有効に利用し,大域的な制御情報を排除し,自然なJava コーディングを採用して,ドライバを開発した.このドライバは,高度なLisp プログラム開発支援ツールを備えていないが,単独でLisp処理系として利用することも可能である.Lisp の言語機能としては,IEEE Scheme のほぼフルセットをサポートしている.処理系のソースコードはわずか約3 500 行,100K バイト程度である.実行性能はけっして良くないが,許容できる範囲に収まっている.We present a Lisp driver which is designed to be used primarily as an embedded systemin Java applications. The key design issues include: (1) it should be easy to extend, modify,and delete the functionality even for a Java programmer who is not familiar with Lisp implementation,(2) the driver itself should be compact enough, and (3) the performance shouldbe comparable, though not excellent. In order to develop a driver that solves these issues,we highly made use of Java features, avoided global control mechanisms, and applied widelyacceptable Java coding. Although the driver is not equipped with powerful tools to supportLisp programming, it can be used as a stand-alone Lisp processor. It supports the functionalityof nearly the full-set of IEEE Scheme. The current implementation consists only of 3,500lines or 100 Kbytes of source code. The runtime performance is not excellent, but remains inan acceptable range.1.

著者

湯淺 太一 奥乃 博 尾形 哲也

出版者

情報処理学会

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.52, no.9, pp.1191-1194, 2011-08-15

著者

湯淺 太一 貴島 寿郎 小西 浩

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.78, no.2, pp.200-209, 1995-02-25

被引用文献数

10

---

NCXは,超並列計算実用化のための重要な計算モデルの一つであるデータ並列に基づくプログラミングのために設計された拡張C言語である.C言語からの移行が容易であること,効率の良い処理系が低コストで実現できこと,統一のとれた言語であること,などを目指して設計された.フルセットのC言語を実行する能力をもつ仮想プロセッサ群を基本とし,プロセッサ間通信などのデータ並列計算機能を,ベースとなるC言語の設計方針にできるだけ従って設計されている.さまざまなアーキテクチャ上で使用されることを前提としており,実際にいくつかの異なるアーキテクチャをターゲットとした処理系の開発が現在進められている.本論文では,NCXの主要な拡張機能を,プログラム例と共に概説し,仮想プロセッサという単純明解な概念を基本としながら,データ並列計算に十分な機能をNCXが提供できることを示した.

著者

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

雑誌

情報処理学会論文誌プログラミング(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と比較評価および検討を行った.

著者

上田 和紀 吉瀬 謙二 土村 展之 湯淺 太一 権藤 克彦 本位田 真一

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.26, no.4, pp.4_2-4_16, 2009-10-27 (Released:2009-12-27)