整数線形計画法を用いたDNAコンピュータ制御コードの生成

• Item type: Trans(1)
• 公開日: 2004-07-15
• タイトル: 整数線形計画法を用いたDNAコンピュータ制御コードの生成
• タイトル / 言語: en
• タイトル: Code Generation for a DNA Computer by Integer Linear Programming
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学情報理工学系研究科
• 著者所属: 東京大学情報理工学系研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者名: 阿部, 正佳; 萩谷, 昌己
• 著者名(英): Seika, Abe; Masami, Hagiya
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文ではANP-96というDNA計算の実験を自動的に行うロボットに対する，整数線形計画法を用いたコード生成について述べる．ANP-96はプレートを置く8個のテーブル，プレートにさまざまな処理を行うIMUと呼ばれる装置，プレートを移動するロボットアーム等から成り立ち，与えられたプログラムに従って複数の実験操作を並列に実行することができる．DNA計算の実験操作は種々の制約のもとで実行され時間もかかるので，複数の実験操作を自動的かつ効率的に実行することは重要である．一方で，現在のANP-96のプログラミング環境は，実験に本質的ではない低レベルな記述を必要とするため多くの手間を必要とし，誤ったプログラムにはロボットを破壊する危険もある．特に，プログラマは有限のテーブルを無駄なく割り当てるとともに，温度制御等の時間のかかる命令を効率良くスケジューリングしなければならない．我々は以上のようなプログラミングを自動化するために，テーブルのアロケーションと命令のスケジューリングを含む問題を，ANP-96に依存しない一般的な抽象度で記述する枠組みを開発するとともに，その枠組みに基づく制御コード生成系を実装した．特に，この枠組みでは，各操作におけるリソースの受け渡しに関する記述を簡潔に表現することができる．また，上述の問題に対する最適な解を与える手法として，コンパイラの分野で提案された整数線形計画法による手法を利用した．この手法は処理時間が長く，したがって小規模のプログラムにしか適用できないのが欠点であるが，ANP-96においては，一般にプログラムは比較的小規模であり，その実行回数とコストを考慮すると，時間をかけて最適化する価値がある．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we describe code generation using integer linear programming for a robot called ANP-96 which automatically executes DNA computing experiments. The robot consists of 8 tables for placing plates, a device called IMU to do various operations on a plate, a robot arm that moves plates, etc., and can execute many experimental operations in parallel according to a given program. Since operations for DNA computing are executed under various constraints and may take long time, executing many operations automatically and efficiently is essential. On the other hand, the current programming environment of ANP-96 is troublesome since it requires programmers to specify low level details which are not essential to experiments, and it is even dangerous since erroneous programs may destroy the robot. In particular, programmers have to appropriately allocate a finite number of tables, and also efficiently schedule operations that take long time, such as those for thermal control. To automate such programming activities, we first designed a framework for specifying such problems including table allocation and operation scheduling, at an abstract level independent from ANP-96, and then implemented a code generator based on the framework. In particular, under this framework one can succinctly describe resource transfers in each operation. In the code generator, we employed the integer linear programming method developed in the field of compilers, which gives the optimal solution for the problems mentioned above. Although the method can only be applied to small programs due to its long execution time, programs of ANP-96 are in general relatively small, and worth optimizing because of the number of times and the cost to execute them.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 45, 号 SIG09(PRO22), p. 1-13, 発行日 2004-07-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会