Lift中間言語における動的長配列の追加

IPSJ

Bibliographic Information

Other Title
  • Extending Lift Intermediate Language with Dynamic Length Arrays

Search this article

Abstract

LIFT ILはGPGPUプログラムのための配列指向の中間言語である．LIFT コンパイラは高級言語プログラムをOpenCLプログラムに変換する際に，中間言語であるLIFT IL上でハードウェア依存の最適化を行う．一方，LIFT ILには動的に長さが決まる配列を表現できないという問題がある．なぜならばLIFT ILは静的に型付けされる関数型言語で，配列の長さをシンボルとして推論する依存型システムを備えており，静的にすべての配列長のシンボルが決定しているからである．本論文では，LIFT ILを存在型で拡張することで動的長配列を扱う方法を提案する．その際，型から配列長を隠蔽・展開する操作を適切な場所に挿入する必要があるが，それらの自動挿入方法を提案する．この提案に基づいて，LIFT ILのコンパイラを作成し，そのうえでフィルター関数を実装した．さらに，Project Euler問題集を用いて，拡張したLIFT ILコンパイラで動的長配列を扱うプログラムが記述・コンパイル・実行できることを確かめた．

LIFT IL is an array-oriented intermediate language (IL) for GPGPU programming. The LIFT compiler translates a high-level language program into LIFT IL, applies hardware-specific optimizations, and then generates an OpenCL program. The IL has a dependent type system that infers the length of arrays as a symbol. This forces every array to have a length that can be statically determined, preventing one from expressing arrays having a dynamic length. In this paper, we extend LIFT IL to support arrays having a dynamic length by using existential types. We also propose an algorithm that automatically inserts pack and unpack operations, which are necessary for existential types. Based on the proposal, we implemented a LIFT IL compiler and added a filter function. In order to assess the usefulness to real world problems, we confirmed the problems that require the dynamic length array in a subset of Project Euler can successfully be written, compiled and executed in the extended LIFT IL compiler.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top