著者

前田 敦司 山口 喜教

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.13, pp.47-57, 2003-10-15

参考文献数

15

被引用文献数

1

---

スタックアーキテクチャの仮想マシン命令を解釈実行するSchemeインタプリタの効率的な実装法について述べる.単純な命令セット定義から出発し,ベンチマークプログラムにおける命令列の実行頻度に応じて命令セットを最適化することで解釈実行のオーバへッドを最小化する体系的な手法を示す.本手法を用いて構成したインタプリタの性能評価を行い,インタプリタの移植性,対話性,デバッグの容易さを損なうことなく,ネイティブコードの20?40%程度の,比較的高い性能が得られていることを示す.An effcient implementation methodology for Scheme interpreters that interpretes stackoriented virtual machine instructions is presented. Starting from simple instruction set definition, we show how our systematic optimization techniques reduces the interpretation overhead based on dynamic frequency of instruction sequence. Evaluation shows that our interpreter can achieve 20 to 40 percent of the performance of native code, without losing portability, interactivity, and ease of debugging.

著者

山口 喜教 樋口 哲也 坂井 修一 Yoshinori Yamaguchi Tetsuya Higuchi Shuichi Sakai 電子技術総合研究所電子計算機部 電子技術総合研究所電子計算機部 電子技術総合研究所電子計算機部 Computer Systems Division Electrotechnical Laboratory Computer Systems Division Electrotechnical Laboratory Computer Systems Division Electrotechnical Laboratory

雑誌

人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence (ISSN:09128085)

巻号頁・発行日

vol.2, no.4, pp.459-471, 1987-12-01

著者

建部修見 児玉 祐悦 関口 智嗣 山口 喜教

出版者

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

雑誌

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

巻号頁・発行日

vol.40, no.5, pp.2246-2255, 1999-05-15

被引用文献数

5

---

MPIはpoint-to-point通信における対応する送信と受信のマッチングに関するコストが大きく 通信遅延が大きくなる原因となっている. 本研究では ノンブロッキング受信が先行発行される通信パターンにおいて 送信時に受信側に問い合わせることなくリモートメモリ書き込みにより送信を行う方式を提案し 高並列計算機EM-Xに実装しその評価を行った. その結果 通信遅延15.3μsec スループット31.4MB/sを達成し 他MPPに実装されているMPIに比べ優位な性能を示した. 本手法は 他システムにおいても適応可能であり ハードウェアスペックどおりの低遅延 高スループットを得るためには重要な方式と考えられる.MPI point-to-point communication is a basic operation, however it requires runtime-matching of send and receive that causes to reduce performance. This paper proposes a new approach to send messages by remote memory write without inquiring of the receiver under a communication pattern such that the corresponding nonblocking receive is issued in advance. Basically, this approach makes it possible to gain low latency and high bandwidth as the hardware specification. MPI-EMX, our implementation of the MPI on the EM-X multi-processor, achieves a zero-byte latency of 15.3 μsec and a maximum bandwidth of 31.4 MB/s, which can compete with commercial MPPs. This approach to reduce communication latency is widely applicable to other systems and is quite a promising technique for achieving low latency and high bandwidth.

著者

白畑 有加 前田 敦司 山口 喜教

雑誌

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

巻号頁・発行日

vol.4, no.3, pp.97-97, 2011-06-29

---

プログラムの処理の流れを扱う概念に,継続がある.継続とは,ある処理のある瞬間における,「次にどのような処理を行うのか」 という処理過程の未来全体を表すものである.Scheme では継続をファーストクラスの機能としてサポートしており,call/cc 関数を用いて継続を扱うことができる.しかし,そのほかほとんどのプログラミング言語は継続を明示的に扱っていない.そのような言語に継続をファーストクラスの機能とし導入する手法として CPS 変換や例外処理を用いた手法など様々な研究がなされているが,導入後の実行効率が大幅に落ちてしまうという問題点をかかえている.本発表では対象言語を JavaScript とし,Pettyjohn らの手法をもとにした新しい,継続を導入する変換手法を提案する.変換後の実行効率の向上のため,継続から処理を再開するときのコードを別途定義する.これにより継続を使用しない場合の処理は変換前後で実行速度が変わらない.また,継続による処理の再開位置を示す Resumption Point を導入することで変換後のコードの重複を削減した.さらに,本発表では継続をキャプチャするタイミングに例外処理を用いる手法と 2 返戻値法の両方を使い分ける.このハイブリッドな継続のキャプチャ手法の採用により,さらに変換後の実行効率の向上を見込むことができる.Continuation is an idea which deals with flow of control inprograms. Although Scheme has continuation as a first-class feature, most other programming languages don't support it explicitly. Various approaches have proposed to adopt the continuation as a first-class feature in such languages, e.g., CPS conversion and stack-traversal and rebuilding using exception. But these conversions have significant impact on execution efficiency and slows down the execution of programs after conversion considerably. In this presentation, we propose a new transformation algorithm based on Pettyjohn, et al.'s approach, which can introduce continuation more efficiently to programming languages that don't support them (we use JavaScript as a specific example). To improve execution efficiency after transformation, we separately generate the code run in ordinary execution and the code executed when continuation is invoked. When executed without using continuations, the execution efficiency after transformation is almost equal to the one before transformation. Since we separately generate the code for two cases, code size may increase after conversions. This code expansion is reduced by sharing code using labels called Resumption Point, which marks the point to resume when continuations are invoked. We use two techniques for stack traversal when capturing continuations: exception handling and two return values method. We combine these two techniques to get better performance in continuation capturing, and believe our approach has the advantages over existing techniques.

著者

前田 敦司 遠藤 匠 山口 喜教

出版者

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

雑誌

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

巻号頁・発行日

vol.45, no.5, pp.83-83, 2004-05-15

---

マークスイープアルゴリズムに基づくインクリメンタルガーベジコレクタは,停止時間をごく短時間に抑えることが可能であるが,効率が悪く,CPU時間が増加する.この性能低下の原因は,一括型GCと比較してマークする時期が早いことに起因するmark/cons比の悪化,GCルーチンを呼び出す回数の増加,write barrierのオーバヘッドなどによる.一方,世代別ガーベジコレクタは高いCPU効率が得られ,また平均の停止時間は比較的短いため良いレスポンスが得られるが,旧世代領域のGC( メジャーコレクション)の際には長い時間にわたって計算処理が停止してしまい,リアルタイム応用には適さない.本発表では,世代別GCがある意味でインクリメンタルGCの一種と見なせることを指摘する.この観察に基づき,新世代領域のGC(マイナーコレクション)のたびに,インクリメンタルに旧世代領域のガーベジコレクションを行う新しいGCアルゴリズムを提案する.インクリメンタル化のために必要となるライトバリアは,世代別ガーベジコレクタの実装にいずれにせよ必要なライトバリアと同じ仕組みを利用する.このアルゴリズムは,通常の世代別ガーベジコレクタに近い効率を保ちながら,停止時間を短く保ち,ガーベジコレクタのリアルタイム性を向上させることができる.Incremental garbage collectors based on mark-sweep algorithms can minimize the pause time caused by garbage collection at the expense of increased CPU time. The main reasons for this performance degradation include: (1) mark/cons ratio gets worse in incremental collectors because objects are marked earlier than in non-incremental counterparts, (2) increase in number of calls to collector routine and (3) write barrier overhead. Generational collectors, on the other hand, can achieve high efficiency and relatively short average pause time, while occasional long pause for collection of old generation space (major collection) makes these collectors unsuitable for real-time applications. In this presentation we point out that certain class of generational collectors can be viewed as a special case of incremental garbage collection. Based on this observation, we propose a new GC algorithm which incrementally reclaims old generation space every time a minor collection is performed. Write barrier for generational collector is also used for incremental collection. With this algorithm, we can improve real-time response of garbage collector by keeping pause time short, with little overhead added to ordinary generational collectors.

著者

山口 大貴 前田 敦司 山口 喜教

雑誌

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

巻号頁・発行日

vol.5, no.3, pp.63-63, 2012-08-20

---

多くのスクリプト言語同様,RubyはCやJavaといった従来の言語と比較して非常に複雑な文法を持っている.そのため,構文解析器の作成において現在主流となっている,yacc(またはbison)とlexを用いて構文解析器と字句解析器を生成しそれらを組み合わせる手法では,文法の記述や実装が困難であったり実装が複雑化しメンテナンスが困難となってしまったりする場合がある.たとえばRubyでは,文字列リテラルに任意の式を埋め込み可能な文法を実現するため等の理由で,手書きの字句解析器を含めて8000行以上にもおよぶ巨大な文法定義を行っている.これは,現在用いられている構文解析アルゴリズムが字句解析をベースとしているために,字句解析器に状態を付加する等のアドホックな実装を行わなければこのような文法を実現することができないためである.そこで本研究では,Parsing Expression Grammar(PEG)をベースとした,強力な解析力を持つ構文解析アルゴリズムPackrat ParsingをRuby処理系(JRuby)に導入することを提案する.Packrat Parsingを実際にRuby処理系に用いることで,従来の構文解析アルゴリズムで問題となっていた部分を改善し,文法定義の保守性を向上させることが本研究の目標である.本研究の構文解析器の実装は,PEGをベースとした文法定義をPackrat Parser生成系Rats!に与えることで行い,その文法定義は従来の文法定義を変換することで作成する.また提案手法による処理系と従来手法による処理系に対して実際のスクリプトを使用した比較評価を行い,その結果として,提案手法によって文法定義の保守性が向上することを示す.

著者

山口 大貴 前田 敦司 山口 喜教

雑誌

全国大会講演論文集

巻号頁・発行日

vol.72, pp.501-502, 2010-03-08

著者

水島 宏太 前田 敦司 山口 喜教

出版者

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

雑誌

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

巻号頁・発行日

vol.49, no.1, pp.117-126, 2008-01-15

---

Packrat parsingは,バックトラック付き再帰下降構文解析にメモ化を組み合わせた構文解析法であり,parsing expression grammar(以下PEG)で記述できる広範囲の文法を入力サイズの線形時間で解析することができるという特徴を持っている.しかし,packrat parsingには,メモ化を行うために入力サイズに比例する記憶領域を要するという欠点がある.本論文では,カット演算子をPEGに加えることにより,不要な記憶領域を削除する機能を持つpackratパーザ生成系を提案する.カットはPrologから借用した概念であり,構文規則中でカットより後ろでバックトラックが不要な場合にそのことを処理系に指示し,不必要なバックトラックが起こらないようにするための機能である.カットの評価によって,ある入力位置より前にバックトラックしないということが判明した場合,その入力位置より前にバックトラックしたときのために使用されているメモ化領域を動的に削除し,再利用することができる.我々は,構文規則中にカットを適切に挿入することで,多くの実用的文法について有界なメモリ量で解析できるパーザを生成可能と考えている.一方,カットによるメモリ効率の改善は,パーザ生成系のユーザが手動でカットを挿入しなければならないという問題点があるが,本論文ではこの問題点を解決するために,解析する言語の構文の意味を変えない範囲でカットを自動的に挿入する手法と,不要なメモ化が行われている箇所を検出して必要な記憶領域を静的に削減するための手法についても提案する.Packrat parsing is a parsing technique that combines memoization with backtracking recursive descent parser. It can handle any grammars that can be expressed in powerful grammar notation called parsing expression grammar (PEG). Generated parsers can analyze its input in linear time. However, to memoize intermediate result, packrat parsing requires storage area proportional to the input size. In this paper, we propose the packrat parser generator system that disposes unnecessary storage area by adding the notion of a cut operator to PEG. Cut operators is the notion we borrowed from Prolog that can be used by programmers to 'cut off' an alternative execution branch of a choice point in a syntax rule when the alternative should not be tried for suppressing unnecessary backtracking. When an alternative is removed by execution of a cut operator (and thus the parser can make sure that no backtracking can occur before a particular input positon), the memoization storage kept against backtracking can be deallocated and reclaimed dynamically. We believe that, for most pratical grammars,parsers which only use bounded memory size can be generated by appropriate insertion of cut operators in syntax rules. Although memory efficiency that can be achieved by hand-insertion of cut operators would be valuable, it is awesome and error-prone. In this paper, we also propose a technique to reduce required storage area by statically detecting syntax rules which memoization is unnecessary and another technique for automatically inserting cut operators without changing meanings of syntax rules.

著者

島田 俊夫 坂村 健 山口 喜教

雑誌

情報処理

巻号頁・発行日

vol.18, no.4, 1977-04-15

著者

遠藤 仁 前田 敦司 山口 喜教

雑誌

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

巻号頁・発行日

vol.4, no.4, pp.38-38, 2011-09-22

---

CPU の性能向上手法がクロックの高周波化からマルチコア化へとシフトした現在,CPU の性能を活用するために処理の並列化を図ることはますます重要性を増している.広く用いられているプログラミング言語の構文解析手法の多くは,有限の (多くの場合 1 つの) トークンを先読みすることによって逐次的に処理を進めるものであり,並列化は困難である.筆者らは,バックトラックによる再帰下降構文解析とメモ化を組み合わせた構文解析アルゴリズムである packrat parsing において,下位の非終端記号の解析結果を記録するメモ化表を,別のスレッドを用いてあらかじめ埋めておくことによって,上位の構文解析スレッドの動作を高速化できるのではないかと考えた.本研究では,Medeiros らの PEG 仮想マシンにメモ化機能を加えて packrat parsing 仮想マシンとし,さらに上記のアイディアを用いて並列化を行った.PEG で表記した文法を与えると,構文木を作成する並列 packrat parser を生成するパーザジェネレータを試作し,生成されたパーザに対して実際のプログラムを入力として評価実験を行い,並列処理の有効性を確認した.Parallelization of programs is getting more importance because recent performance improvement is driven mainly by increasing number of cores, rather than increase in clock frequency. Many of parsing algorithms used in programming language implementations rely on directing their actions by lookahead of finite (in many cases, only one) tokens, thus severly limiting the possibility of parallel processing. Packrat parsing is a variant of backtracking recursive descent parsing combined with memoization. In packrat parsing, memoization table for low-level nonterminals can be filled by distinct prefetch thread to accelerate processing of higher-level nonterminals. Following the idea, we have parallelized packrat parsing abstract machine, which is based on PEG machine by Medeiros. We built a parser generator that generates parallel packrat parser from grammar description written in PEG. We evaluated performance of the generated parser using real program as input, confirming the effectiveness of our approach.

著者

山口 喜教 角田 良明 阿江 忠

出版者

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

雑誌

電子情報通信学会技術研究報告. CPSY, コンピュータシステム

巻号頁・発行日

vol.97, no.569, pp.13-16, 1998-02-25

参考文献数

2

被引用文献数

3

---

1997年9月8日から9月12日までイタリアのコモにおいて、開催されたコンプレックスコンピュータシステム国際会議(ICECCS'97)の概要について報告する。ICECCSは、コンピュータシステムの複雑さに対処するための工学的な問題について議論するための会議で、1997年が3回目の開催となる。

著者

山名 早人 小池 汎平 児玉 祐悦 坂根 広史 山口 喜教

雑誌

全国大会講演論文集

巻号頁・発行日

vol.56, pp.297-298, 1998-03-17

被引用文献数

2

著者

飯星 貴裕 山口 喜教 前田 敦司

出版者

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

雑誌

電子情報通信学会技術研究報告. CPSY, コンピュータシステム (ISSN:09135685)

巻号頁・発行日

vol.108, no.180, pp.1-6, 2008-07-29

被引用文献数

1

---

ネットワークのセキュリティシステムの一つにネットワーク侵入検知システム(NIDS)がある.このNIDSのスループットを向上させるため,ボトルネックとなっているパターンマッチング処理を専用ハードウェアで行う試みがなされている.しかしながら,一般的に専用ハードウェアには膨大なパターン集合とのマッチングを高速に行うために,回路規模を大きくせざるをえないという問題がある.そこで,本稿ではパターンマッチング回路の回路規模の増大を抑えるために,NFAハイブリッドアーキテクチャに着目した.このアーキテクチャは,その特性上高い回路効率を持つと考えられるが,必ずしも詳細な評価が行われていない.ここでは,NFAハイブリッドアーキテクチャの詳細な回路を実装・評価した上で,さらに回路効率を向上させるための手法を考案し,評価を行った.その結果,入力文字数が小さいときにおいて,従来のNFAアーキテクチャよりも高い回路効率を持つことを実証し,さらに提案した効率化手法が有効であることを示した.

著者

戸田 賢二 西田 健次 高橋 栄一 Nick Michell 山口 喜教

出版者

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

雑誌

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

巻号頁・発行日

vol.36, no.7, pp.1619-1629, 1995-07-15

被引用文献数

13

---

実時間並列計算機用相互結合網の構成要素として用いるルータチップの設計およびその性能について報告する。本ルータはパケット交換型で4入力4出力であり、多段網における優先度逆転現象の発生を抑える方式として我々の提案した「優先度先送り方式」を採用している。優先度は32ビット、入力ポートごとに8パケットの優先度キューを持ち、データ転送レートはポート当たり190メガバイト/秒、パイプラインは25ナノ秒ピッチの2段構成である。この性能は優先度制御を行わない通常の方式のルータと比較し遜色のないものである。