著者

前田 敦司 遠藤 匠 山口 喜教

出版者

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

雑誌

情報処理学会論文誌プログラミング(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!に与えることで行い,その文法定義は従来の文法定義を変換することで作成する.また提案手法による処理系と従来手法による処理系に対して実際のスクリプトを使用した比較評価を行い,その結果として,提案手法によって文法定義の保守性が向上することを示す.

著者

横山 哲郎 今井 敬吾 曾 剛 冨山 宏之 高田 広章 結縁 祥治

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.2, no.2, pp.54-69, 2009-03-23

---

動的電圧制御 (DVS: dynamic voltage scaling) は,プロセッサへの供給電圧とその動作周波数をプログラム実行時に変化させる技術であり,現在,多くの商用プロセッサに実装されている.本稿では,デッドラインなどの制約のあるリアルタイムシステムを対象に,DVS システムにおいて動的エネルギー消費のより少ないプログラムを開発する方法論の 1 つを提示する.DVS システムで実行されるプログラムに動的エネルギー消費の最適化が有効であるためには,残り予測実行時間の実行早期の正確な見積りを容易にすることが重要である.そのため,プログラムは何を計算するかに加えどう計算するかをうまく指定する必要がある.しかし,プログラム改変によるエネルギー消費の最適化はプログラムのモジュール性を著しく損なう.本稿では,プログラムから独立し,エネルギー消費の最適化戦略を開発する手法を提案する.提案手法により,エネルギー消費の最適化を行うときに元のプログラムの部分正当性が容易に保存され,元のプログラムおよびエネルギー消費の最適化を行うための評価戦略が独立してそれぞれモジュール性を有するようになった.遅延評価などのプログラミング言語の特徴や構成的アルゴリズム論における組化などを活用することにより半自動化が実現できたことが,本開発法の特徴の 1 つである.本稿では,整列,選択,文字列検索などの基本的なアルゴリズムに提案手法を適用する.また,電力モデルを備えた命令セットシミュレータ(ISS: instruction set simulator)において実験を行い,エネルギー消費がどれだけ最適化されたかを評価する.基本的なアルゴリズムにおいて,本稿のアプローチが有効であることから,複雑なアルゴリズムに対しても本手法が効果的であることが期待される.DVS (dynamic voltage scaling) is a technique for scaling the processor's supply voltages and working frequencies. Several commercially available processors provide voltage/frequency controls. We propose a development method for deriving dynamically energy efficient programs on DVS-enabled real-time systems, which have several constraints such as deadline. In order to improve energy efficiency of programs on DVS systems, it is necessary to accurately estimate remaining predicted execution time in the early phase of the execution of programs. Thus, how to execute codes is as important as what codes to execute. However, the revision of programs for energy efficiency seriously harms their modularity. We separate concerns of the development of energy optimization strategy from the development of programs. As the result, partial correctness of original programs is preserved, and each of original programs and energy optimization strategy has modularity, independently. Lazy evaluation of functional programming languages and tupling in constructive algorithmics are employed for realizing the semi-automation of our development method. Our techniques are applied to basic algorithms such as sorting, selection, and string matching. Their energy efficiency is evaluated by using an instruction set simulator (ISS) with a power model.

著者

井上 拓 小松 秀昭 中谷 登志男

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.1, no.2, pp.1-8, 2008-09-26

---

近年,XMLなど多くの用途において,テキストデータの標準的な表現形式として,1文字を1~3バイトの可変長で表現するUTF-8エンコーディングが用いられている.一方,Java仮想マシンなど多くの処理系においては,文字列の内部表現として1文字が2バイトの固定長であるUTF-16エンコーディングが用いられている.そのため,Javaで記述されたWebアプリケーションサーバなどの多量のテキストデータを取り扱うワークロードにおいては,テキストデータをUTF-8とUTF-16との間で相互に変換する処理が大きな処理時間を占める場合があり,このテキストデータ変換処理の高速化はシステム全体の性能向上において重要な意味を持つ.本研究では,SIMD命令を用いてUTF-8からUTF-16への変換をはじめとする可変長符号化データのデコード処理を高速に行う手法を提案する.この手法では複数のデータを並列に処理することに加えて,条件分岐での分岐予測ミスによるオーバヘッドを減少させることで,大きな性能向上が得られる.本手法をPowerPCアーキテクチャのSIMD命令セットであるVMX命令を用いて実装し,様々なテキストデータを入力としてUTF-8文字列デコード処理の性能を計測した結果,SIMD命令を用いない既存の方法と比較して単純な例で10倍以上,実際のテキストデータを用いたケースでも2倍から10倍の性能向上が得られた.Recently UTF-8 encoding is widely used as a standard format for text data exchange. The Java programming language, however, uses UTF-16 encoding as its internal representation format for text data. As a result, data conversions between UTF-8 and UTF-16 consume considerable amount of CPU time in workloads that process large amount of text data, such as web application servers. Hence accelerating these conversions are important to improve the performance of many applications. In this paper, we present our new technique to accelerate decoding of variable-length formats, such as conversion from UTF-8 to UTF-16, by using SIMD instructions. The new technique can achieve higher performance by reducing overhead of branch mispredictions in addition to exploiting data parallelism of SIMD instructions. We implemented the technique using VMX instructions of the PowerPC architecture and evaluated its performance to decode various UTF-8 sequences on a PowerPC 970MP processor. As a result, we showed that our technique significantly accelerated the UTF-8 decoding compared to the existing method.

著者

芝 哲史 笹田 耕一 平木 敬

雑誌

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

巻号頁・発行日

vol.5, no.3, pp.1-22, 2012-08-20

---

近年,様々なスクリプト言語処理系に対してコンパイラが開発されている.これらのコンパイラは処理系に組み込む形で実装されることが多く,新しくコンパイラを開発するために,処理系そのものの再実装や,処理系の大幅な改変が行われている.このため,スクリプト言語処理系に対する新たなコンパイラの開発には多大な労力をともなう.そこで我々は,スクリプト言語RubyのCによって実装された処理系(CRuby)の機能を活用することで,処理系に対して新たに手を加えることなく動作するコンパイラCastOffを開発した.CastOffは,実行時コンパイル,コンパイル済みコードの再利用,プロファイル実行,アノテーションのサポート,脱最適化,再コンパイルなどの機能を持つ.これらの機能を,CastOffはCRubyのCによる拡張ライブラリ(C拡張)としてCRubyにいっさいの変更を加えずに実現している.本稿ではCastOffの設計と実装を述べ,CastOffの機能をRubyのC拡張でどう実現したかを詳細に解説する.そして,CastOffのようにライブラリとしてコンパイラを実装するために,どのような機能が必要かを議論する.

著者

河内谷清久仁 古関 聰 小野寺 民也

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.15, pp.13-23, 2003-11-15

被引用文献数

1

---

Javaでは言語の性質上,オブジェクトに対するロック操作が頻繁に行われる.これを高速化することは,システム全体の性能向上に非常に重要である.オブジェクトがそれぞれどのスレッドにロックされているかに着目した調査を行ったところ,特定のスレッドにのみ頻繁にロックされているという「スレッド局所性」が見られることが分かった.この性質に着目し本論文では,各オブジェクトごとに特定のスレッドに「ロック予約」を与え,ロック処理を高速化する手法について述べる.予約を持っているスレッドは,従来よりも軽い処理でそのオブジェクトのロックを行える.具体的には,従来ロック処理に不可欠と考えられていたcompare_and_swapなどの不可分命令ではなく,単純なメモリアクセス命令でロックを獲得/解放できる.予約者以外のスレッドがロックを行った時点でロック予約が解除され,以後そのオブジェクトは従来の方式でロックが行われる.この予約ロック機構を,IBM Java VMとJITコンパイラに実装し,いくつかのベンチマークを走らせたところ,従来のロック手法に比べて最大で53%の性能向上が確認された.In Java execution, lock operations are performed very frequently to realize exclusive oper-ations among multiple threads. Therefore, accelerating the lock performance has been very important to execute Java-based applications faster. We investigated the lock behavior of Java programs, focusing on the relation of each object and threads acquiring the object's lock. It turned out that for many objects, the lock is acquired by only one thread specific to the object, even in multi-threaded Java programs. By utilizing the thread locality, this paper shows a novel ultra-fast locking technique for Java. The algorithm allows locks to be reserved for threads. When a thread attempts to acquire a lock, it can do without any atomic operation if the lock is reserved for the thread. Otherwise, it cancels the reservation and falls back to a conventional locking algorithm. We have implemented the lock reservation mechanism in IBM's production virtual machine and JIT compiler. The results show that it achieved performance improvements up to 53%.

著者

加藤 紀夫 上田 和紀

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.1, pp.155-155, 2005-01-15

---

階層的グラフ構造の書換えに基づく並行言語において,プロセスが形作る構造に関する静的な性質を表現し,解析する新しい枠組みを提案する.本発表では,階層グラフ書換え言語としてLMNtal を例に取り,この言語に型体系を導入する具体的な方法を示す.LMNtal はグラフのノードとしてアトムを持ち,アトム間を結ぶ1 対1 のリンクを持つ.さらにアトムは膜と呼ばれる構文で階層化され,各膜がその膜内に対して局所的に適用される書換えルールを持つ.グラフ書き換え言語をプログラミング言語として見たときには,プログラムの書き方や処理系の最適化に関する指針に関する研究が求められる.しかし,従来の並行グラフ書換え言語は,LMNtal と違って一般のグラフ書き換えを実用に供するプログラミング言語にするというアプローチの研究が不足しているため,一般のプログラムに対して上述の指針を与えるために役に立つ解析技術はあまり存在しない.本発表で提案する型体系は,はじめにアトムをアクティブなものと,非アクティブなものに分類し,アクティブアトムにつながる可能性のあるプロセスやデータを解析することに基づいた強い型をプログラムに導入する.この型体系は,並行論理型言語のうえでの強モード体系をLMNtal に応用したものであるが,膜に関する性質を扱う点で新しい.本発表では,型体系の型安全性を証明する.We propose a new framework for formalizing and analyzing static properties on the shapes of processes in concurrent languages based on hierarchical graph rewriting. We take LMNtal as an example language and show a concrete method to introduce a type system to this language. LMNtal has atoms as graph nodes and one-to-one links that connect together atoms. Moreover, atoms are hierarchized with membranes and each membrane has rewriting rules local to itself. Viewed as programming languages, graph rewriting languages ask for research on how to write programs and how to optimize the runtime system. However, since the graph rewriting languages so far have lacked in research towards making themselves practical programming languages, few analysis techniques exist that can be used for solving the above issues. Our type system firstly classifies atoms into active ones and passive ones, and then introduces to the program strong types based on which processes as well as data can be connected to active atoms. The type system has been obtained by applying the strong mode system of concurrent logic languages to LMNtal, but is new in that it can deal with properties on membranes. The proof of the type safety will be shown.

著者

後藤 勇太 白田 佳章 木山 真人 芦原 評

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.4, no.3, pp.84-93, 2011-06-29

---

構文解析法で Packrat Parsing という手法がある.Packrat Parsing は,再帰下降構文解析にメモ化を組み合わせた手法であり,バックトラックや無限先読みを用いた解析において,線形時間で解析可能である.しかし,左再帰を含む文法は解析不可能である.そこで,従来は左再帰を含む文法を解析する際,左再帰部分を等価な右再帰に変換し,解析を行っていた.だが文法の変換を行うと構文木の構造が変化してしまう.また,特定の左再帰は変換できない.たとえば,閉路が存在する文法である.よって,この手法では解析できない文法がある.Warth らは,左再帰を含む文法を,右再帰への変換なしに解析を可能にした.しかし,Warth らの手法では,同一の入力位置で左再帰が複数発生する文法において,特定の入力の解析に失敗する.また,構文木の構造が意図したものとは異なるという問題がある.そこで本研究では,更新検知を用いて,左再帰を含む文法を右再帰への変換なしに解析でき,かつ従来手法の 2 つの問題点に対応する Packrat Parser を提案・実装し,評価を行った.Packrat Parsing is a kind of parsing method. Packrat Parsing is a combination of Recursive Descent Parsing and memoization that can parse backtracking and unlimited look-ahead in linear parse time. However, Packrat Parsing cannot parse left recursive grammars. Thus, traditional method transforms left recursive grammars into right recursive grammars. Unfortunately, syntax tree is changed by the transforming. Moreover, particular left recursive grammars cannot be transformed. Traditional method cannot parse particular grammars. Warth, et al. made possible to support left recursive grammars without transforming in Packrat Parsing. However, the method cannot parse some grammars that have multiple left recursions at an input position. Furthermore, syntax tree is be unintended consequence when the method parses particular grammars. This paper presents imprementation and evaluation of Packrat Parser with Update Detection that possible to support left recursive grammars without transforming, and grammars that have multiple left recursions at an input position.

著者

大須賀恭輔 結縁祥治 阿草 清滋

出版者

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

雑誌

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

巻号頁・発行日

vol.43, no.8, pp.119-119, 2002-09-15

---

本発表では実時間ステートチャートの振舞いに対してL¨uttgenらのSPL(Statechart Process Language )を時間遷移において拡張した体系として提案したSPLRTを用いて,実時間ステートチャートの動作シミュレートを行うツールの実装を行う.SPLRTは実時間ステートチャートの振舞いをラベルつき遷移システムによりモデル化した言語である.SPLRTはSPL の2つの動作意義,動作遷移,クロック遷移に遅延遷移を新たに加える.遅延遷移はマイクロステップレベルで稠密時間変数を扱う.これによりマクロステップレベルでの実時間の経過を実現可能とした.また,時間遷移を持つラベルつき遷移システムの動作を解析することにより,検証の基礎とすることができる.検証の基礎としてSPLRTにより動作定義し,設計者の意図どおりに実時間ステートチャートが動作するかをツールによって検証を行う.In this presentation, we implements the tool for a simulation of the behavior of real-time statecharts with SPLRT. SPLRT models the behavior of real-time statecharts as the labeled transition system derived from the operational semantics of SPLRT. SPLRT is an extension of SPL proposed by Luttgen et al in that delay transitions labeled by dense-time are incorporated. Analyzing the behavior of the labeled transition system with timed transition can be as the base of verification. We verify whether the real-time statechart behave as an intension of a designer with a tool.

著者

鈴木 弘 今城 哲二 中鉢欣秀 大岩 元

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.9, pp.102-102, 2000-11-15

---

我々は,日本人のためのプログラミング言語として,日本語による文章表現を基にしたプログラミング言語を設計し実装している.普段使用している日本語のほうが従来の英語的なプログラミング言語よりも書きやすく,読みやすいという考えに基づいている.日本語は英語のように単語を空白で区切ることなく,続けて書くのが一般的である.我々が設計しているプログラミング言語も一般的な日本語に合わせ,空白で区切ることをしない言語を前提にしている.これを分かち書きしないという意味で,非分かち書き日本語プログラミング言語とする.本論文では,非分かち書き日本語プログラミング言語,すなわちセパレータのないプログラミング言語に対しての字句解析について述べる.We design new programming language for Japanese. We think Japanese-based programming language is better than English-based programming language for Japanese. The feature of this language is that grammar are based on Japanese and tokens are not separated by space character like a sentence in Japanese. This paper discusses a lexical analysis method for non-separated Japanese-based programming language.

著者

丸山 真佐夫 山本 繁弘 大野 和彦 中島 浩

出版者

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

雑誌

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

巻号頁・発行日

vol.43, no.3, pp.80-80, 2002-03-15

---

再演実行を基礎とする従来の並列プログラムのデバッギング手法では,バグの原因をたどる過程で,頻繁にプログラムの再実行をしなくてはならない.実行の行き過ぎによる再実行の回数を減らすためには,実行途中でブレークポイント設定が必要になり,ユーザの負担が大きくなる.そこで我々は,再演実行手法に基づきながら,プログラム先頭からの再実行をせずに並列プログラムを過去の状態に戻し,そこから実行を再開することを可能にする"巻き戻し実行"機構を提案する.本提案の巻き戻し実行機構では,並列プログラムを構成する任意のプロセスを,任意の受信イベントの時点に戻すことができ,これを基礎にすべてのプロセスまたは一部のプロセスだけをプログラムの途中から実行させることができる.我々は並列言語Orgel に対して巻き戻し実行機構を実装し,性能評価を行った.その結果通常実行に対して,イベント順序保存実行で7%,巻き戻しのための状態保存実行で13%増という,小さいオーバヘッドで動作させることができた.In debugging a parallel program with conventional replay based method, the programmer has to rerun the program repeatedly from its beginning, because the code the programmer wants to examine next might have already gone beyond the breakpoint. To prevent the program from overrunning, the programmer must set breakpoints with much care in the complicated parallel program. Thus we propose a rollback mechanism, which allows the programmer to rerun the program halfway of it. Using this mechanism, the programmer may rollback any process of the target program to any receive event on its event graph. We applied our rollback mechanism to a parallel programming language named Orgel, and evaluate the overhead of logging and rollback. The result shows that execution time of event logging and computational state saving mode for rollback are only 7% and 13% larger than normal execution respectively.

著者

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

出版者

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

雑誌

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

著者

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

出版者

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

雑誌

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

著者

今城 哲二 鈴木 弘 大野 治 植村 俊亮

雑誌

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

巻号頁・発行日

vol.42, no.SIG02(PRO9), pp.102, 2001-02-15

---

約20年前からコンピュータでの漢字利用が普及し,標準プログラム言語で日本語データ処理が可能となった.日本語処理は,国際規格化されていて,いくつかの言語では,識別名にも漢字などマルチオクテット文字が使用できる.予約語まで日本語にした本格的な日本語プログラム言語も,分かち書きのレベルで,実用化されている.本発表では,分かち書きをしない,より日本語に近い日本語プログラム言語``まほろば''の設計思想と文法について述べ,プログラマおよび学生による記述実験による評価について報告する.

著者

今城哲司 鈴木 弘 大野 治 植村 俊亮

雑誌

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

巻号頁・発行日

vol.41, no.SIG04(PRO7), pp.90, 2000-06-15

---

約20年前からコンピュータでの漢字利用が普及し,標準プログラム言語で日本語データ処理が可能となった.日本語処理は,国際規格化されていて,いくつかの言語では,識別名にも漢字などマルチオクラット文字が使用できる.予約語まで日本語にした本格的な日本語プログラム言語も,分かち書きのレベルで,実用化されている.本論文では,分かち書きをしない,より日本語に近い日本語プログラム言語“まほろば”の設計思想と文法について述べ,実装実験による評価について報告する.

著者

勝原 達也 滝本 宗宏

雑誌

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

巻号頁・発行日

vol.48, no.SIG12(PRO34), pp.52-65, 2007-08-15

---

命令レベル並列性を高める有効な手法の 1 つとして、命令スケジューリングがある。特に、投機的実行を許す命令スケジューリングは、さらに並列度を高められる点で効果的であることが知られている。投機的実行は、元のプログラムに存在しなかった冗長性を導入する可能性があるので、1 つの命令をスケジュールするたびに共通部分式の削除を適用することが効果的である。本発表では、共通部分式の削除で取り除くことができない部分冗長性を扱う部分冗長除去に注目し、部分冗長除去に基づく大域命令スケジューリングを提案する。本手法は、あるプログラム点に対して、投機的命令スケジューリングを含むコードの上方移動を行うごとに、部分冗長除去のデータフロー解析を適用する。解析結果から最適化効果が認められる場合、実際にプログラムを変更することで、命令スケジューリングを実現する。部分冗長除去の性質は、プログラムの実行パスを長くしないことを保証し、大域命令スケジューリングで問題となる補償コードを最適なプログラム点に自動的に挿入する。また、本手法は、ループ構造を認識することなく、ループスケジューリング手法の 1 つである、ループシフティングを実現することができる。さらに本論文では、本手法を COINS コンパイラ・インフラストラクチャ上で実装し、最適化効果を検証する。

著者

住井英二郎 大根田裕一 米澤 明憲

雑誌

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

巻号頁・発行日

vol.45, no.SIG12(PRO23), pp.67-82, 2004-11-15

---

制御フローグラフに類似した一般的な命令型言語を,CPS(継続渡しスタイル)を中間表現としてコンパイルする方法を提案する.CPS とは,「残りの計算」(継続と呼ばれる)を表現する関数を生成することにより,すべての関数呼び出しや条件分岐を末尾位置においた関数型言語の一種であり,Scheme やML といった関数型言語のコンパイラに広く用いられている.命令型言語をCPS に変換することで,スタックフレームや例外ハンドラが継続として明示化され,関数適用や例外処理における複雑な制御の流れが明確化される.結果として,インライン展開や末尾呼び出し最適化を含む多くの最適化が容易に実現できる.我々は命令型言語をCPS に変換する過程の単純な定式化を与え,その正しさを証明する.

著者

柴田 謙 高前田 伸也

雑誌

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

巻号頁・発行日

vol.16, no.1, pp.19, 2023-01-13

---

近年,マルチコアCPUが主流となってきたが,現在主流の言語はシングルコアが主流の時代に設計された物が多く,並列実行を行って動作速度の向上を行うためには多くの場合で特別なライブラリや構文が必要になり,簡単に並列実行が行えるとはいえない.このマルチコアの利点を生かすため,特別な構文なしで並列実行を規定として行うプログラミング言語「Coa」を開発した.提案するプログラミング言語Coaは,並列実行を既定とするが,単につねに並列実行を行うとするとデータレース問題が生じる.この問題を避けるため,CPUのアウト・オブ・オーダ実行がデータ間の依存関係を検出するのと同様に,変数の依存関係を自動検出し,データレースが生じないように自動的に実行順序と並列性を制御する.このため,内部で並列実行を行いつつも外から見た振舞いは逐次実行と同様となり,プログラムの複雑さを増やさずに実行速度を向上できる.また,処理単位が小さく逐次実行のオーバヘッドが大きい場合に備え,純粋でない関数と指定すれば逐次実行される機能もある.CoaのインタープリタはGoで書かれており,Coaで書かれたソースコードは,goroutineを用いてインタープリタ内で並列実行される.現在,基本演算,繰返し,条件分岐,関数定義などの基本的な機能があり,FizzBuzz問題や情報オリンピックの問題等を解決できる程度の言語機能を実装している.比較実験として,13ファイルのダウンロードとマンデルブロ集合を表示するための計算を,逐次処理と並列処理で実行した.それぞれの実行時間とコード行数を比較し,Coaはコードの複雑さを増すことなく並列実行して処理速度が上がることを確認した.本発表では,Coaの仕組みと特徴,今後の課題を説明する.

著者

笹田 耕一 松本 行弘 前田 敦司 並木 美太郎

雑誌

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

巻号頁・発行日

vol.47, no.SIG2(PRO28), pp.57-73, 2006-02-15

---

本稿ではオブジェクト指向スクリプト言語Ruby を高速に実行するための処理系であるYARV: Yet Another RubyVM の実装と,これを評価した結果について述べる.Ruby はその利用のしやすさから世界的に広く利用されている.しかし,現在のRuby 処理系の実装は単純な構文木をたどるインタプリタであるため,その実行速度は遅い.これを解決するためにいくつかの命令実行型仮想マシンが提案・開発されているが,Ruby のサブセットしか実行できない,実行速度が十分ではないなどの問題があった.この問題を解決するため,筆者はRuby プログラムを高速に実行するための処理系であるYARV を開発している.YARV はスタックマシンとして実装し,効率良く実行させるための各種最適化手法を適用する.実装を効率的に行うため,比較的簡単なVM 生成系を作成した.本稿ではRuby の,処理系実装者から見た特徴を述べ,これを実装するための各種工夫,自動生成による実装方法について述べる.また,これらの高速化のための工夫がそれぞれどの程度性能向上に寄与したかについて評価する.

著者

齋地 崇大 前田 敦司

雑誌

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

巻号頁・発行日

vol.13, no.4, pp.1-20, 2020-10-23

---

リージョンによるメモリ管理は,メモリ空間をリージョンと呼ばれる単位で分割し,リージョン単位でLIFO順にメモリの割付けと解放を行う.プログラム中のメモリを必要とするオブジェクトは,それぞれの生存期間に対応したリージョンにメモリが割り付けられる.オブジェクトとリージョンの対応付けは,プログラムの構造を静的に解析することによって決定できる.実行の前にオブジェクトの生存期間を決定するため,ガベージコレクションによる実行時オーバヘッドの削減が期待できる.Ruby,Python,そしてJavaScriptといった動的言語は,実行時まで得られない動的な情報がプログラムに含まれるため,不要となったオブジェクトの割り付けられたリージョンを速やかに解放できる精度の高いオブジェクトとリージョンの対応付けを静的な解析で決定するのは困難である.本研究では,精度の高いリージョンによるメモリ管理を動的言語へ適用する手法として,実行時リージョン解析を提案する.実行時まで決定しない情報を用いてリージョンを解析するため,静的な解析と比較して精度の高いリージョン対応付けを決定できる.提案手法の性能を計測するため,プログラミング言語Rubyの処理系へ実行時リージョン解析機構を実装し評価を行った.いくつかのケースでは,ガベージコレクションの頻度や停止時間が削減され,実行時間の短縮が確認された.