[Prev][Next][Index][Thread]
[compeg:00109] PLDI report
ソニーの藤波です。PLDIの発表内容のまとめをお送りします。
藤波順久 fnami@psdc.sony.co.jp
ソニー(株) インフォメーション&ネットワーク研究所
---
ACM SIGPLAN 2000 Conference on Programming Language Design and
Implementation
http://suif.stanford.edu/~lam/pldi00/program.html
6/18 PLDI'00
--------
8:30 - 10:00 Session I: Runtime Techniques
Chair: Michael D. Smith
--------
Dynamo: A Transparent Runtime Optimization System
Vasanth Bala (Hewlett-Packard Laboratories), Evelyn Duesterwald
(Hewlett-Packard Laboratories) and Sanjeev Banerjia (InCert Software
Corp.)
Dynamoはnative code applicationを実行時に最適化するシステムである。最
初はインタプリタとして動き、hot traceを見つけるとそれをまっすぐなマシ
ンコード(fragmentと呼ばれる)に変換してfragment cacheに入れる。traceは
jump、call(virtualも含む)、returnも含むひと続きに実行されるコードで、
一つのtraceでは合流は考えない(合流してくるものは別のtraceとみなす)ので、
簡単に最適化ができる。traceの開始の候補につけられたカウンタが一定値を
超えたら、そこからtrace終了条件になるまでの命令がhot trace bufferには
いり、処理される。traceの開始の候補はbackwardジャンプとfragment cache
からの出口である。traceの終了はbackwardジャンプと他のfragmentの開始で
ある。traceの終了以外の出口も許され、すでにfragment cacheにあるコード
に分岐、あるいはcompensation codeを通ってインタプリタに戻る。hot trace
の検出率が突然上昇したら、working setが変化した可能性が高いので、
fragment cacheや他のワークエリアをすべてflushする。このため、fragment
のunlink処理は不要である。
http://www.hpl.hp.com/cambridge/projects/Dynamo/docs.htm
--------
Practicing JUDO: Java Under Dynamic Optimizations
Michal Cierniak (Intel Corp.) Guei-Yuan Lueh (Intel Corp.) and James
Stichnoth (Inktomi Corp.)
Java virtual machineのJITコンパイラの実装を効率化するため、次のような
処理を入れた。例外オブジェクトを必要なところでだけ生成、GCマップを必要
になったメソッドにだけ生成（高速低品質コンパイラの場合のみ）、dynamic
class loadingがないとしてインライン展開されたコードへのJMPを入れ、必要
になったら元のコードに書き戻す、ループ内での添字範囲チェック除去である。
それぞれ数%の性能向上があった。
--------
Split-Stream Dictionary Program Compression
Steven Lucco (Transmeta)
発表者は最近Microsoft Researchから移った。
PLDI'97で提案したBRISCを単純化、高圧縮率、高速、2段階アルゴリズムにし
たもので、基本ブロック単位でJIT展開できる。命令をオペコードとオペラン
ドに分け、それぞれでよく出現する列の辞書を作る。
Crusoeのtranslation bufferの実質的サイズを増やすのに使える。
translationをやり直すよりだいぶ速い。
--------
10:30 - 12:00 Session II: Pointer Analysis
Chair: Laurie Hendren
--------
Unification-based Pointer Analysis with Directional Assignments
Manuvir Das (Microsoft Research)
C言語でポインタがよく使われる場所は、複雑なオブジェクトの番地や、返り
値を得る変数の番地を手続きに渡すときなので、そのときに正確になる低コス
トの、context-insensitiveポインタ解析アルゴリズムを設計した。トップレ
ベルポインタはまじめに計算し、それより下はmergeしてしまう。Andersenの
flow insensitiveアルゴリズムに近い結果が得られる。
http://research.microsoft.com/spa/spa.html
--------
Off-line Variable Substitution for Scaling Points-to Analysis
Atanas Rountev (Rutgers University) and Satish Chandra (Bell Labs,
Lucent Technologies)
標準的なflow- and context-insensitive points-to analysisを行う前に、変
数のセットを単一の代表変数で置き換える処理を行う（線型時間でできる）
（解析結果を変えない）ことで、入力サイズを減らし、高速化する。
--------
Modular Interprocedural Pointer Analysis Using Access Paths: Design,
Implementation, and Evaluation
Ben-Chung Cheng and Wen-mei Hwu (University of Illinois, Urbana
Champaign)
flow-insensitiveだが、context-sensitive（手続き呼び出し元を考慮する）
なポインタ解析方法で、ポインタで指されるメモリ位置の名前を代入文の右辺
の形に正規化したaccess pathを使う。この解析法を使って、依存関係のない
load命令とstore命令を並べ替えて高速化する実験を行った。
--------
Lunch
--------
Programming Languages Achievement Award
Susan Graham
SIGPLAN創設者の一人。
授賞講演では、SIGPLANの歴史を述べ、ユーザインタフェースや、記述するべ
き計算のサイズや多様性、プラットホームの複雑さや多様性は増したが、
research agendaは当初と変わらず、計算を高いレベルで表現することだと話
していた。
--------
1:30 - 3:00 Session III: Program Correctness
Chair: Jens Knoop
--------
Safety Checking of Machine Code
Zhichen Xu, Barton Miller and Thomas Reps (University of Wisconsin)
マシンコード（生成方法は問わない）の安全性をチェックする。プログラムの
初期入力にtypestate情報linear constraintsの注釈を付けたものを必要とす
る。ホストで決められているメモリアクセスのpolicyを追加してチェックする
こともできる。現在のところ、配列の添字は線型のものしか使えず、動的なも
のは扱えない。
--------
Translation Validation for an Optimizing Compiler
George Necula (University of California, Berkeley)
最適化の各パスで意味が保存されていることを確認するインフラストラクチャ。
各パスの前後のプログラムの意味が同じかどうか、記号実行を使って検証する。
必要なら、パスから情報をもらう。GCCの最適化パスのうち13個以上検証でき
た。ただし、入力プログラムによってはfalse alarmが10%も出ることがある。
--------
A Certifying Compiler for Java
Christopher Colby, Peter Lee, George Necula and Fred Blau (Cedilla
Systems
Inc.)
certifying compiler（proof-carrying-codeを生成するコンパイラ）を実用的
な言語に対して作れることを示した。述べられているSpecial Jは、Javaのバ
イトコード（スレッドを除く）をx86命令にコンパイルする。
--------
3:30 - 5:30 Session IV: Compilation for Parallel Hardware
Chair: Linda Torczon
--------
Bitwidth Analysis with Application to Silicon Compilation
Mark Stephenson, Jonathan Babb and Saman Amarasinghe (MIT)
Bitwiseというコンパイラは、変数（整数とポインタ）のビット幅を可能なら
自動的に決める。プログラムは正しいものとして解析し、例えば、charにint
を代入していたら、そのintの変数は8ビットでよいとする。単純なループの上
限解析もする。
--------
Optimal Instruction Scheduling Using Integer Programming
Kent Wilken, Jack Liu and Mark Heffernan (University of California,
Davis)
基本ブロックのoptimalスケジューリングを整数線型計画法を使って行う。普
通の線型計画法で解けなかったものだけ整数線型計画法を使う。
--------
Improved Spill Code Generation for Software Pipelined Loops
Javier Zalamea, Josep Llosa, Eduard Ayguade and Mateo Valero
(Polytechnic University of Catalonia)
ソフトウェアパイプラインでレジスタが足りなくなったときは、展開数を減ら
すか、spillコードを入れるが、それをheuristicsを使って行う方法を提案す
る。どんなソフトウェアパイプラインテクニックにも適用できる。
--------
Exploiting Superword Level Parallelism with Multimedia Instruction
Sets
Samuel Larsen and Saman Amarasinghe (MIT)
MMXなどのSuperword Level Parallelismはベクトル化できるループ以外に、普
通の基本ブロックでも使えることがある。packing/unpackの問題を避けるため、
隣接するメモリアクセスに注目し、def-use chainをたどっていった。実装に
はSUIFを使っている。基本ブロックレベルではアセンブリ言語コーディングと
比べてまあまあの結果になった。packing/unpackingができないのと、アライ
ンメントが問題。
--------
6/19 PLDI'00
--------
8:30 - 10:00 Session V: High-Level Transforms
Chair: Saman Amarasinghe
--------
Compiler Analysis of Irregular Memory Accesses
Yuan Lin and David Padua (University of Illinois, Urbana Champaign)
普通は配列の添字の式がループ制御変数とループ不変式だけのものしか扱えな
いが、同じ変数を添字とするもの、別の配列の値を添字とするもの、も扱える
ようにする。
--------
Transforming Loops to Recursion for Multi-Level Memory Hierarchies
Qing Yi (Rice University), Vikram Adve (University of Illinois, Urbana
Champaign) and Ken Kennedy (Rice University)
ループで書かれたプログラムを、分割統治法の再帰的プログラムに変換し、局
所性を増すことで、メモリ階層が深かったり、キャッシュサイズ等が異なるシ
ステムに持って行ったりしてもだいじょうぶにする。
--------
Symbolic Analysis of Array Index Bounds and Memory Access Regions
Radu Rugina and Martin Rinard (MIT)
ポインタや配列の添字の解析を線型計画法で解く。制御フローグラフの各ノー
ドの前後で、添字の範囲を決める制約（線型不等式で表現）を作り、それを連
立させて解く。静的範囲チェックや並列化のテストに使える。実装にはSUIFを
使っている。
--------
10:30 - 12:00 Session VI: Analysis of Java Programs
Chair: Susan Eggers
--------
A Framework for Interprocedural Optimization in the Presence of
Dynamic Class Loading
Vugranam Sreedhar, Michael Burke and Jong Choi (IBM T. J. Watson
Research Lab)
Javaの参照を、A無条件に内部の型に決まっているもの、B外部からロードした
型を指すかもしれないもの、C外部からロードした型だけを指すものに分ける
解析方法を適用してみた。Aに関するメソッド呼び出しはインライン展開、Bは
型をテストして通ったものだけ、特殊化されたメソッドを呼ぶようにする最適
化に利用できる。
--------
Effective Synchronization Removal for Java
Erik Ruf (Microsoft Research)
Javaの静的コンパイラで、同期操作の除去を、escape analysis（オブジェク
トが外に出ていくか調べること）より改良された方法: 一つのスレッドしか使
わないオブジェクトの同期操作を見つけることで行う。
--------
Type-Based Race Detection for Java
Stephen Freund (Stanford University) and Cormac Flanagan (Compaq
Systems Research Center)
race condition（複数スレッドが同期なしで共有データを同時にいじる状況）
を静的な解析で見つける。/*# ... */の形のコメントで同期が必要な箇所に
annotationをつけ、それをチェックする。よくある同期パターンの多くをとら
えられる。
--------
1:30 - 3:00 Session VII: Foundations
Chair: Alex Aiken
--------
On Loops, Dominators, and Dominance Frontiers
G. Ramalingam (IBM T. J. Watson Research Center)
loop nesting forestとは、制御フローグラフのループを表すデータ構造と、
ループの包含関係である。loop nesting forestを使うと、支配辺境や支配木
を求める新しいアルゴリズムができる。reducibleグラフではループの概念は
広く受け入れられているものがあるが、ireducibleグラフでは違う。ここでは、
従来の三つの定義の欠点（求めるのに自乗時間、利用するのに自乗時間、求め
るのに支配木が必要）のない、新しい定義を与える。
--------
Functional Reactive Programming from First Principles
Zhanyong Wan and Paul Hudak (Yale University)
Functional Reactive Programmingとは、ハイブリッドシステムをプログラム
する高水準で宣言的なフレームワークである。連続時間の意味論を持つが、実
装は離散時間になる。実装が忠実であるとは、単位時間を0に近づけたときに
連続時間での値に収束することで、その条件は一様収束である。
--------
Scalable Context-Sensitive Flow Analysis using Instantiation
Constraints
Manuel Fahndrich, Jakob Rehof and Manuvir Das (Microsoft Research)
context-sensitiveだがflow-insensitiveなフロー解析をscalableにするため
に、各関数は1度だけ解析し、同値類ベースで行うような方法を提案する。
--------
3:30 - 4:30 Session VIII: Garbage Collection
Chair: Amer Diwan
--------
Contaminated Garbage Collection
Dante Cannarozzi, Michael Plezbert and Ron Cytron (Washington
University)
新しい、ごみ集め方法を述べる。オブジェクトをスタックフレームに動的に対
応づけ（深いオブジェクトから指されたら深くしていく）、そのスタックフレー
ムが取り除かれるときに、オブジェクトを消す。参照がなくなっても対応する
スタックを浅くはしないので、ごみになっても消されないことがある。
--------
A Generational On-the-fly Garbage Collector for Java
Tamar Domany (IBM Haifa Research Lab), Elliot Kolodner (IBM Haifa
Research Lab) and Erez Petrank (Technion - Israel Institute of
Technology)
on-the-fly garbage collectorに世代を入れた。オブジェクトの移動はできな
いので、世代境界は物理アドレスで分けずにオブジェクトに色を付ける。色を
変える操作が少なくてすむように、色を交互に使う。全実行時間が最大25%高
速化された。
--------
8:30 - 10:00 Session IX: Handling Real-Life Issues
Chair: Dawson Engler
--------
A Single Intermediate Language That Supports Multiple Implementations
of Exceptions
Norman Ramsey (Harvard University) and Simon Peyton Jones (Microsoft
Research)
C--は移植可能コンパイラを作るために、出力言語として作られたもので、メ
モリアクセスやジャンプ等を直接書ける。C--に例外処理を直接実装すると、
言語による意味の違いを吸収できないので、
continuation-passing style
constant-time stack-cutting
unwind stack in run-time system
custom code to unwind
の4つの方法をサポートした。
--------
Efficient Algorithms for Bidirectional Debugging
Bob Boothe (University of Southern Maine)
デバッガのステップ実行等で、双方向に動けるようにする。過去になるほど長
い間隔でチェックポイントを保存しておき、I/Oのログも取っておく（I/Oは
UNIX system callを仮定）。プログラムの各ステップに、カウンタをインクリ
メントしてある値になったらデバッガに飛ぶような、関数呼び出しを追加する。
呼び出される関数は適宜変更される。逆方向移動は、再実行によって行うが、
例えばある変数を前回変えた位置に移動する場合は2パスが必要になる。
--------
Caching Function Calls using Precise Dependencies
Allan Heydon, Roy Levin and Yuan Yu (Compaq Systems Research Center)
純粋な関数型言語での、ソフトウェアシステムの実装では、コンパイラやリン
カ等の外部ツールが関数で呼び出され、それらは時間がかかるるので、結果を
キャッシュする必要がある。それを最適にするために依存関係を詳細に、例え
ば使われていない関数入力値はキャッシュ検索キーとしては無視するようにし
て記録する。
http://www.research.compaq.com/SRC/vesta/
--------
10:30 - 12:00 Session X: Optimizations for Java
Chair: Thomas Gross
--------
ABCD: Eliminating Array Bounds Checks on Demand
Rastislav Bodik (University of Wisconsin), Rajiv Gupta (University of
Arizona) and Vivek Sarkar (IBM T. J. Watson Research Center)
配列の範囲チェックは例外を発生させるのでコード移動の最適化を妨げ、Java
のバイトコードレベルではそれの除去を表現できないので実行時（バイトコー
ドロード後）にやるしかない。普通のアルゴリズムでは実行時だと重いので、
ABCDを提案する。demand-drivenなのでhotな範囲チェックにだけ適用できて軽
い。
--------
Field Analysis: Getting Useful and Low-cost Interprocedural
Information
Sanjay Ghemawat (Compaq Systems Research Center), Keith Randall
(Compaq Systems Research Center) and Daniel Scales (Compaq Western
Research Laboratory)
field analysisは、フィールドのアクセス指定子を使って、必要な範囲
（privateならそのクラス、protectedならパッケージとサブクラス）だけ解析
を行い、nullテストや配列範囲テストの除去、コンパイル時メソッド呼び出し
解決、オブジェクトインライン、不要な同期の除去、スタック割り付け等がで
きる。
--------
An Automatic Object Inlining Optimization and its Evaluation
Julian Dolby and Andrew Chien (University of California, San Diego)
PLDI'97で発表した、オブジェクトをそのコンテナの中に展開する方法を、理
論化し、評価した。
--------
best presentation award: Manuvir Das (microsoft)
best paper award: Dynamo: A Transparent Runtime Optimization System