著者

小池 龍信 岩井 輝男 中西 正和

出版者

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

雑誌

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

巻号頁・発行日

vol.40, no.7, pp.1-8, 1999-08-15

参考文献数

8

被引用文献数

1

---

ごみ集め処理(GC)を必要とする言語がいくつか存在し Lisp言語などのような関数型言語処理系にはGCが不可欠である.これらの処理系は 実時間性に向いてないとされてきた.理由としては GCを行っている時に処理が一時中断することがあげられる.この中断時間をできるだけ減らすための研究がなされている.このようなGCを実時間GCと呼び その中の一つにTreadmill GCがある.Treadmill GCは複写式GCを改良したものである.このGCでは全てのオブジェクトを双方向環状リストで連結し GCは複写によるオブジェクトの移動ではなく 双方向ポインタのつけかえ(relink)で実現する.これにより複写式GCの利点を保持し さらにオブジェクトの移動を行わないため複写式GCで問題となるreadバリアが解消されている.Treadmill GCの時間的コストは生きているオブジェクトの数に比例する.よって生きているオブジェクトが多い場合には実時間性が乏しい.この問題点の解決方法として世代別GCの考えを取り入れた.世代別GCの考え方は ある程度生き続けたオブジェクトは半永久に生き残り また生成して間もないオブジェクトの殆どは寿命が短いというものである.本稿では 世代別GCの考えを取り入れたTreadmill GC(Opportunistic Treadmill GC)の提案及びその実現方法 さらにいくつかのベンチマークアプリケーションを実行し その実験結果から1回のGC時間 総実行時間を削減したことについて報告を行う.Real-time Garbage Collection is a study that makes pause time of GC as short as possible. Treadmill GC, one of the real-time GC algorithms, is improved Copying GC. In this scheme all objects are linked by cyclic doubly-linked lists (treadmill). Objects are not removed by copying, and objects' pointer of treadmill are relinked. This means that advantages of Copying GC are preserved, solving read barrier problem at the same time. We propose the "Opportunistic Treadmill GC", which is a Garbage Collection technique that the collector traces only short-life objects, setting long-life objects out of collector's view. There is a strong evidence that the overwhelming majority of objects die very young, although a small proportion may live for a long time. In Treadmill GC, pause time of GC is mostly the time for relinking alive objects. Especially in the original Treadmill GC, collector has to relink all alive object. However in Opportunistic Treadmill GC, collector only has to relink short-life objects of all alive objects. Hence we can make a pause time of GC shorter and improve effective real-time GC. Then we implemented the original Treadmill GC and Opportunistic Treadmill GC on an incremental garbage collector of the Lisp1.5 based system, and showed how efficient it is by a few experiments, in comparison with the original Treadmill GC, we could decrease average time of one GC execution as well as total execution time. We refined incremental GC so that the real-time systems with our Opportunistic Treadmill GC will be more useful.

著者

中西 正和 田中 詠子

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.35, no.11, pp.1014-1019, 1994-11-15

被引用文献数

5

著者

中西 正和

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.11, no.10, pp.619-623, 1970-10-15

被引用文献数

1

著者

中西 正和

雑誌

情報処理

巻号頁・発行日

vol.11, no.10, 1970-10-15

著者

高橋 聡子 岩井 輝男 田中 良夫 前田 敦司 中西 正和

出版者

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

雑誌

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

巻号頁・発行日

vol.38, no.5, pp.1050-1057, 1997-05-15

参考文献数

14

---

リスト処理プロセスとGCプロセスを同時に複数動作させることによって,リスト処理を並列化することによる処理時間の短縮が可能になった.しかし,セルの消費のペースはアプリケーションによって異なり,CPUの数も計算機によって異なるので,リスト処理プロセスの最適な数はアプリケーション,計算機によって異なると考えられる.本稿では,セルの消費速度やフリーセルの残量によってリスト処理プロセスとGCプロセスのCPU割当てを動的に決定する機能により,Lispの代表的なアプリケーションに対し,処理速度と実時間性とのバランスのとれた処理を行うことを可能とする並列Lispシステムの報告を行う.本システムの実装にあたっては,できるだけリスト処理の中断が生じることがなく,リスト処理に最大数のCPUが割り当てられるようCPU割当てのパラメータを設定し,CPU割当てを動的に決定した.その結果,リスト処理の中断がなくなり実行時間が短縮された.Parallel lisp system with parallel garbage collection(GC)can produce improvements in throughput by executing list processing in parallel.But,the optimal number of list processes and GC processes depends on machines and applications because the number of processors on a machine and cells which are consumed by various applications is different.In this paper,we report parallel lisp system which makes it possible to balance throughput and real time performance by dynamic allocation of CPU depending on speed of consuming cells and the number of remaining free cells.We dynamically changed CPU allocation according to the parameter which was set to avoid a disruption of list processing and allocateas many CPU as possible to list processing.Consequently,our system yielded improvements in throughput without any disruption of list processing.

著者

前田 敦司 中西 正和

雑誌

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

巻号頁・発行日

vol.38, no.3, pp.574-583, 1997-03-15

---

本論文では,幅優先で式の評価を行う新たな計算機アーキテクチャであるキューマシンを提案し,その実行モデルを用いて関数型言語を特殊なハードウェアのサポートのない密結合並列計算機上で効率良く自動並列実行する言語処理系の構築法を述べる.関数型言語においては複数の関数呼び出しを並列に処理することが可能であるが,すべての関数呼び出しの実行が終了するまで待って実行を再開するための同期オーバヘッドが問題となる.また,通常スタックに保持する局所的な実行の文脈をヒープ上に保持する必要があるため,メモリ管理のオーバヘッドも増大する.本論文では,キューマシンの実行モデルを模倣してスタックをキューに置き換えることにより上記のオーバヘッドを大幅に削減することができ,既存の計算機上で並列関数呼び出しが効率良く実現できることを示す.この手法を用いたプロトタイプ言語処理系の実行時間を密結合並列計算機で測定した結果,逐次実行ではCなどの他の(逐次)言語処理系に劣るものの,2CPU以上では他の処理系を上回り,高い台数効果が得られている.

著者

荻原 拓也 中西 正和

雑誌

全国大会講演論文集

巻号頁・発行日

vol.49, pp.229-230, 1994-09-20

---

ニューラルネットには様々な学習方法があるが、リカレントニューラルネットについてはあまり良い学習方法が見つかっていない。そこで、リカレントニューラルネットの新しい学習法獲得に向けて単純なゲームを用いて実験を行ない、その結果について考察する。

著者

冨田 勲 伊勢 正三 坂崎 紀 大照 完 川野 洋 神前 尚生 田口 友康 坪井 邦明 中西 正和 中村 勲

雑誌

情報処理

巻号頁・発行日

vol.29, no.6, 1988-06-15

著者

松井 祥悟 田中 良夫 前田 敦司 中西 正和

出版者

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

雑誌

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

巻号頁・発行日

vol.36, no.8, pp.1874-1884, 1995-08-15

参考文献数

12

被引用文献数

4

---

本論文では、並列型(parallel)および漸次型(incremental)ガーベジコレクションの基本アルゴリズムである相補型ガーベジコレクタ(Complementary Garbage Collector)の提案およびその評価を行う。このアルゴリズムは、増分更新型(incremental update)とスナップショット型(snapshot-at-begiming)という2つの基本アルゴリズムを相補的に組み合わせたものである。ゴミの回収効率の良さと正当な(無矛盾な)実装の容易さという両者の長所を併せ持つ。このアルゴリズムは、現在広く便用されているスナップショット型アルゴリズムを代替する。この型を基本アルゴリズムとしている現存の並列型および漸次型ガーベジコレクションに直ちに応用できる。Complementary Garbage Conectorを並列型mark-and-sweep法および潮次型mark-and-sweep法に組み込み、評価を行った結果、ゴミセルの回収効率は一括型GCと同程度まで改善されることが確認された。これにより実行速度、実時間性(無停止性)が改善された。

著者

田中 あずさ 米津 光浩 中西 正和

雑誌

全国大会講演論文集

巻号頁・発行日

vol.第51回, no.人工知能と認知科学, pp.43-44, 1995-09-20

---

Gerald M.Edelmanが神経グループ選択理論(NGS理論)を実証するために構築したシミュレーションシステムDarwinIIIのサブシステムOculomotor-systemを実装し,NGS理論を用いたニューラルネットワークの学習について考察する.

著者

石井 直樹 平石 智宣 延澤 志保 斎藤 博昭 中西 正和

出版者

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

雑誌

情報処理学会研究報告. SLP, 音声言語情報処理 (ISSN:09196072)

巻号頁・発行日

vol.31, pp.23-30, 2000-06-02

参考文献数

8

---

日本語略語を復元するシステムについて報告する。このシステムは、任意の日本語略語に対して、新聞記事コーパス中の語句および辞書中の語句のうちから、いくつかの復元規則を用いて、元の語になると考えられるものを順位を付けて出力するものである。復元規則として、「元の語が略語内の文字を全て、同じ順で含むこと」、「略語と元の語を構成する字種が等しいこと」、「元の語の文字数が略語を構成する字数の4倍以内であること」、「略語内の文字が元の語の中で不連続的に含まれていること」といったことを定めた。用いる復元規則の数を変えながら404の略語に対して実験を行い、7割以上の確からしさで復元に成功した。

著者

中西 正和

雑誌

情報処理

巻号頁・発行日

vol.11, no.7, 1970-07-15

著者

中西 正和

出版者

慶応義塾大学藤原記念工学部

雑誌

Proceedings of the Fujihara Memorial Faculty of Engineering Keio University

巻号頁・発行日

vol.21, no.86, pp.210(82)-210(82), 1968

---

Summaries of Doctor and Master Theses

著者

萩原 知章 岩井 輝男 中西 正和

雑誌

全国大会講演論文集

巻号頁・発行日

vol.第52回, no.ソフトウェア, pp.19-20, 1996-03-06

---

世界的に行われているLisp言語の標準化の活動の1つとして、国際標準機構ISOによるものがあり、ISLispと呼ばれている。ISLispの特徴は、Common Lispの仕様から使用頻度の低い機能を取り除いたものである。このため、Common Lispに比べ処理系の作成が容易である。また、オブジェクト指向機能も兼ね備えている。本研究では、ISLispに準拠したLispの実装をバイトコードインタプリタにより行なった。この実装は2段階に分けられる。第1段階(本システム):コンパイラがLispのプログラムを後置記法に直し、中間コードに変換する。そして、このコードに最適化を施し、バイトコードで書かれたファイルに変換する(これ以降この作業をコンパイルという)。第2段階:バイトコードインタプリタがバイトコードに変換されたプログラムを読み込み、解読し、スタック機械により実行する。本稿では、第1段階のコンパイラの実装および、中間コードに最適化を施した際の実行効率について述べる。

著者

三浦 泰介 山口 文彦 中西 正和

雑誌

全国大会講演論文集

巻号頁・発行日

vol.第56回, no.ソフトウェア科学・工学, pp.418-419, 1998-03-17

著者

中西正和

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.11, no.7, pp.426-427, 1970

被引用文献数

2

著者

田中良夫 松井 祥悟 前田 敦司 中西 正和

出版者

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

雑誌

情報処理学会記号処理研究会報告

巻号頁・発行日

vol.94, no.49, pp.17-24, 1994

被引用文献数

1

---

通常ガーベッジコレクション(GC)はリスト処理を中断して行なわれる.GCをリスト処理と並列に行なう(並列GC)ことにより,GCによる中断時間をなくし,リスト処理の実時間化が可能となる.並列GCではGCの処理中にリスト処理によってデータが書き換えられるので,GCの正当性を保証するために特殊な処理が必要となる.そのため並列GCは停止型GCに比べてあまり効率が上がらず,実用化されているものもほとんどない.mark and sweep方式の並列GCにおいては,ゴミセルの回収効率が停止型GCに比べて約1/2になってしまうことが知られている.これらの欠点の改善は,並列GCの実用化へ向けての重要な研究テーマである.本論文では,mark and sweep方式の並列GCの欠点を改善したGCである,Partial Marking GC(PMGC)の提案,実装および評価に関する報告を行なう. PMGCはmark and sweep型の並列GCに世代別GCの概念を導入したGCである.PMGCを実装し様々な実験を行なった結果,PMGCによってゴミセルの回収効率は従来の並列GCに比べ最大で2倍に改善されることが確認された.PMGCは並列GCの実用化に向けての有効なGCである.

著者

菱沼 千明 山下 堅治 中西 正和

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.17, no.11, pp.1002-1008, 1976-11-15

被引用文献数

1

---

This paper presents some usuful techniques for implementing LISP 1.5 interpreter. First, effective push down stack techniques are given in order to realize the recursive procedure peculiar to the function of LISP. Second, we show a method to curtail the excess a-list which is generated by universal functions when they evaluate iterative functions. The efficiency of those methods are also shown by comparing the mini-LISP, which is made to employ those methods, with other LISP 1.5 interpreters.

著者

植田 健治 山本 敬二 永田 守男 中西 正和

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.17, no.2, pp.155-157, 1976-02-15

著者

中西 正和

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.14, no.12, pp.961-967, 1973-12-15