(57)【要約】【課題】分子演算の並列性を利用して従来の電子コンピュータよりも高速に計算を実行することが可能な技術を提供すること。【解決手段】電子計算部２１と分子計算部２２とを具備し、前記電子計算部は通常の計算処理に加えて、実質的に分子計算部の機能を制御し、その制御下で分子による演算が実施される分子計算装置において、前記電子計算部による前記分子計算部の制御は、所定の言語で作成された高級言語を前記分子計算機の制御命令に変換後に最適化したプログラムで実行される。【選択図】      図１
2005202785.tif 000002
【特許請求の範囲】
【請求項１】
電子計算部と並列反応実行部とを具備し、前記電子計算部は通常の計算処理に加えて、実質的に並列反応実行部の機能を制御し、その制御下で多数の反応を並列的に実行する並列反応実行装置において、
前記電子計算部による前記並列反応実行部の制御は、所定の言語で作成された高級言語を前記並列反応実行機の制御命令に変換後に最適化したプログラムで実行されることを特徴とする並列反応実行装置。
【請求項２】
分子の化学反応により並列反応実行を実行する並列反応実行装置であって、分子の化学反応の反応制御を行う反応制御部を備えた並列反応実行部と、分子を核酸配列に基づき符号化した符号分子に対応付けて定義された変数及び定数と、前記符号分子の演算反応に対応付けて定義された関数により記述されたプログラムを、前記符号分子の演算反応に対応する分子の化学反応の反応制御を行う前記反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成する制御命令生成部と、前記制御命令の手順を出力する出力部とを有する電子計算部を備え、
前記制御命令生成部は、所定の言語で作成された前記プログラムを前記制御命令に変換後に最適化することを特徴とする並列反応実行装置。
【請求項３】
請求項１又は請求項２に記載の並列反応実行装置において、前記最適化は、ＩＬＰ（整数線形計画法）に基づいて行うことを特徴とする並列反応実行装置。
【請求項４】
前記分子は核酸分子であることを特徴とする請求項２に記載の並列反応実行装置。
【請求項５】
多数の反応を並列的に実行する並列反応の計画を設計する並列反応実行計画設計装置において、並列反応の反応原理に対応付けて定義された関数により記述されたプログラムを前記並列反応の反応制御を行う反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成する制御命令生成部と、前記制御命令の手順を出力する出力部とを含み、前記制御命令生成部は、所定の言語で作成された前記プログラムを制御命令に変換後に最適化することを特徴とする並列反応実行計画設計装置。
【請求項６】
分子の化学反応により並列反応実行を実行する並列反応実行の計画を設定する並列反応実行計画設計装置において、分子を核酸配列に基づき符号化した符号分子に対応付けて定義された変数及び定数と、前記符号分子の演算反応に対応付けて定義された関数により記述されたプログラムを、前記符号分子の演算反応に対応する分子の化学反応の反応制御を行う反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成する制御命令生成部と、前記制御命令の手順を出力する出力部からなり、
前記制御命令生成部は、所定の言語で作成された前記プログラムを制御命令に変換後に最適化することを特徴とする並列反応実行計画設計装置。
【請求項７】
多数の反応を並列的に実行する並列反応実行方法であって、並行反応の原理に対応付けて定義された関数により記述されたプログラムを前記並列反応の反応制御を行う反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成し、前記制御命令の手順を前記反応制御部に出力し、前記制御命の手順に基づき並列反応の反応制御を行うことを特徴とする並列反応実行方法。
【請求項８】
分子の化学反応により並列反応実行を実行する並列反応実行方法であって、分子を核酸配列に基づき符号化した符号分子に対応付けて定義された変数及び定数と、前記符号分子の演算反応に対応付けて定義された関数により記述されたプログラムを、前記符号分子の演算反応に対応する分子の化学反応の反応制御を行う反応制御部を駆動させるための制御命令に変換後に最適化して前記制御命令の手順を生成し、前記制御命令の手順を前記反応制御部に出力し、前記制御命令の手順に基づき分子の化学反応の反応制御を行うことを特徴とする並列反応実行方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、核酸分子を使用する新規な並列反応実行装置、並列反応実行計画設計装置、及び並列反応実行方法に関する。
【背景技術】
【０００２】
１９９４年にエイデルマン（Ａｄｌｅｍａｎ）によって提案されたＤＮＡコンピュータが知られており、その研究も進められている。このＤＮＡコンピュータは、数学者の間でよく知られている「ハミルトン経路問題」と呼ばれるような問題に対して、従来のコンピュータを補完することが期待されている。
【０００３】
このようなＤＮＡコンピュータは、入出力をＤＮＡとして、反応を実行させて、結果のＤＮＡを取得・検出するＤＮＡの組み合わせ計算を実行する分子計算部と、処理プログラムの実行とその結果の出力、計算反応の計画及び結果の解釈を実行する電子計算部とを備えている。
【０００４】
このようなＤＮＡコンピュータにおいて、分子計算部は複数のＤＮＡ反応(以下、単に井「反応」とも称する)を並列に実行することができるが、これらのＤＮＡ反応は種々の制約のもとで実行され時間もかかるので、複数の反応を自動的かつ効率的に実行することは重要である。従って、分子計算部に設けられた有限のテーブルを無駄なく、割り当てるとともに、温度制御等の時間のかかる命令を効率よくスケジューリングしなければならない。
【０００５】
このスケジューリングについては、例えば、分析装置への入力操作が簡単に行えて汎用性に優れ、しかも、分析機器の取り替え使用を支障なく、行うことができる分析システムが提案されている(特許文献１参照)。この特許文献１では、分析装置に、データ処理装置からの高級言語表現よりなる実行文を動作実行のための指示データに翻訳可能なインタプリタを備えている。このため、データ処理装置側から自然言語に近いわかりやすい文字列等を入力することにより、分析装置のパラメータの設定やキー操作、あるいは、パラメータの値や実側値を呼び出して印字や計算などを自由に行えることになる。このことにより、ダイレクトオペレーション、例えば、オペレータが操作中に分析装置の値を確認したくなったような場合に、即時に、しかも、簡単に操作することができることが可能となり操作性が向上される。しかし、特許文献１には、分析を最適化する手法は開示されていない。
【０００６】
また、例えば自動着色装置又は組織処理装置における、被検物処理方法、とりわけ細胞学的又は組織学的標本の処理方法において、生物学的又は組織学的標本等の被検物の全体として可及的迅速に処理可能な方法も提案されている(特許文献２参照)。この方法では、グラフ理論的及び／又は線形計画法的解法によって、又は各処理プログラムを実行するために予設定された順序で到達されるべき処理ステーションの配置若しくは再配置によって、移送装置の走行路を最小化することにより処理量の最適化（ないし最適解の導出）を行う。これにより、各処理ステーションにおける処理時間内にできるだけ多くの細胞学的又は組織学的標本等の被検物の移送作業を行い、処理過程全体としての迅速化を図ることができるようにしている。しかし、特許文献２は、最大数の移送運動工程を実行することを主眼としているので、反応の時間や反応の順序を考慮した最適化は行われていない。
【特許文献１】特公平７−９２８７７号公報
【特許文献２】特開２００２−９０３７１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、分子演算の並列性を利用して従来の電子コンピュータよりも高速に計算を実行することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の第１局面に係る並列反応実行装置は、電子計算部と並列反応実行部とを具備し、前記電子計算部は通常の計算処理に加えて、実質的に並列反応実行部の機能を制御し、その制御下で多数の反応を並列的に実行する並列反応実行装置であって、前記電子計算部による前記並列反応実行部の制御は、所定の言語で作成された高級言語を前記並列反応実行機の制御命令に変換後に最適化したプログラムで実行されることを特徴とする。
【０００９】
本発明の第２局面に係る並列反応実行装置は、分子の化学反応により並列反応実行を実行する並列反応実行装置であって、分子の化学反応の反応制御を行う反応制御部を備えた並列反応実行部と、分子を核酸配列に基づき符号化した符号分子に対応付けて定義された変数及び定数と、前記符号分子の演算反応に対応付けて定義された関数により記述されたプログラムを、前記符号分子の演算反応に対応する分子の化学反応の反応制御を行う前記反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成する制御命令生成部と、前記制御命令の手順を出力する出力部とを有する電子計算部を備え、前記制御命令生成部は、所定の言語で作成された前記プログラムを前記制御命令に変換後に最適化することを特徴とする。
【００１０】
本発明の第３局面に係る並列反応実行装置は、多数の反応を並列的に実行する並列反応の計画を設計する並列反応実行計画設計装置であって、並列反応の反応原理に対応付けて定義された関数により記述されたプログラムを前記並列反応の反応制御を行う反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成する制御命令生成部と、前記制御命令の手順を出力する出力部とを含み、前記制御命令生成部は、所定の言語で作成された前記プログラムを制御命令に変換後に最適化することを特徴とする。
【００１１】
本発明の第４局面に係る並列反応実行装置は、分子の化学反応により並列反応実行を実行する並列反応実行の計画を設定する並列反応実行計画設計装置において、分子を核酸配列に基づき符号化した符号分子に対応付けて定義された変数及び定数と、前記符号分子の演算反応に対応付けて定義された関数により記述されたプログラムを、前記符号分子の演算反応に対応する分子の化学反応の反応制御を行う反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成する制御命令生成部と、前記制御命令の手順を出力する出力部からなり、前記制御命令生成部は、所定の言語で作成された前記プログラムを制御命令に変換後に最適化することを特徴とする。
【００１２】
本発明の第５局面に係る並列反応実行方法は、多数の反応を並列的に実行する並列反応実行方法であって、並行反応の原理に対応付けて定義された関数により記述されたプログラムを前記並列反応の反応制御を行う反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成し、前記制御命令の手順を前記反応制御部に出力し、前記制御命の手順に基づき並列反応の反応制御を行うことを特徴とする。
【００１３】
本発明の第６局面に係る並列反応実行方法は、分子の化学反応により並列反応実行を実行する並列反応実行方法であって、分子を核酸配列に基づき符号化した符号分子に対応付けて定義された変数及び定数と、前記符号分子の演算反応に対応付けて定義された関数により記述されたプログラムを、前記符号分子の演算反応に対応する分子の化学反応の反応制御を行う反応制御部を駆動させるための制御命令に変換後に最適化して前記制御命令の手順を生成し、前記制御命令の手順を前記反応制御部に出力し、前記制御命令の手順に基づき分子の化学反応の反応制御を行うことを特徴とする。
【発明の効果】
【００１４】
本発明によれば、分子計算部の動作を最適化できる。
【発明を実施するための最良の形態】
【００１５】
図面を参照して本発明の実施の形態を説明する。なお、本発明で用いる「並列反応」とは、同種及び／又は異種の２つの反応結果に夫々対応する２以上の反応を同時又は重複して実行することをいう。従って、並列反応を構成する２以上の反応は、各反応を実行するために設計された１以上の自動化装置によって実行される。２以上の反応を同時に実行する場合には、同一の反応容器で混合する場合と、別々の容器でほぼ同時に混合する場合とがある。２以上の反応を重複して行う場合には、通常別々の反応容器で計画された順番で混合するが、同じ容器で異なる反応条件（例えば、温度、反応開始用試薬）を適用しても良い。また、本発明における「反応」とは、任意の物質に関する所望の応答特性を、適宜の反応性物質を用いてその応答特性を発揮させるか調べることにあることをいう。典型的な反応は化学反応であり、好ましくは、核酸を使用する分子反応において、特に、分子計算処理を含むＤＮＡコンピュータへの適用が可能である。なお、化学反応は、精製、検査、廃棄、修理、組み立て等の種々の目的のために適用できる。並列反応を実行する装置としては、公知のロボット手段を本発明のために利用しても良い。しかし、本発明の利点を享受すれば、ロボット手段は、非常に単純かつ小型な構成になりうるし、並列反応を完了するのに必要な生物学的資源又は環境資源も最小限にすることができる。
【００１６】
図１は、本発明の一実施の形態に係る分子計算装置(以下、単に「計算装置」と称することもある)の概略構成を示すブロック図である。本発明の一実施の形態に係る計算装置は、大きく分けて、電子計算部２１と分子計算部２２とを具備し、電子計算部２１が、実質的に分子計算部２２の機能を制御し、その制御下で分子計算部２２による演算を実施する。なお、分子計算部２２は、分子の化学反応を実行することにより実質的に計算を実行する。
【００１７】
このように、本発明の一実施の形態に係る計算装置では、分子演算の並列性を利用して分子計算部２２が演算を行い、その結果得られたデータを基に、電子計算部２１が演算結果を表示する。本発明の一実施の形態では、核酸分子を用いて計算を実施することによって、データの並列処理や遺伝子解析を効率的に実行する計算装置を開示する。また、核酸分子によりデータやプログラムを表現し、そのプログラムで定義された演算を分子反応に置き換えて反応を実行することにより、従来の電子コンピュータに比べて桁違いに大きなメモリ容量と高い並列処理能力を実現する。
【００１８】
本発明の一実施の形態に係る分子計算装置は、分子計算部２２と電子計算部２１とが互いに補完的に機能を分担する計算装置であって、電子計算部２１には、データを入力する入力部１１及びデータを出力する出力部２０が接続されている。また、分子計算部２２には、データを入力する入力部１８及び出力部１９が接続されている。
【００１９】
電子計算部２１は、一般的な電子コンピュータにより実現される。具体的には、演算部１４、記憶部１３、入出力制御部１２及び通信部２３を具備する。演算部１４に記憶部１３、入出力制御部１２及び通信部２３が接続されている。また、入出力制御部１２は入力部１１及び出力部２０に接続されている。更に、その他の一般的な電子コンピュータの構成要素を具備してもよい。演算部１４は、例えばＣＰＵなどにより実現される。記憶部１３は半導体メモリなどにより実現される。
【００２０】
分子計算部２２は、演算部１５、記憶部１６、入出力制御部１７及び通信部２４を具備する。演算部１５と記憶部１６、入出力制御部１７、入力部１８及び出力部１９は分子や容器、ピペッタなどの反応機器により実現される。すなわち、分子計算部２２は、分子の化学反応を実行するための装置により実現されるものであり、演算部１５、記憶部１６、入出力制御部１７などに装置構成が１：１に対応するものではない。演算部１５、記憶部１６、入出力制御部１７などの構成は、分子計算部２２の分子や容器、ピペッタなどの反応機器を電子計算部２１と同じ概念として捉えた場合の構成の一例を示している。演算部１５、記憶部１６及び入出力制御部１７は通信部２４に接続されている。また、入出力制御部１７は入力部１８及び出力部１９に接続される。これら分子や反応機器により、演算とデータの記憶と分子データの入出力制御とを同時に実現している。
【００２１】
本発明の計算装置では、電子計算部２１が分子計算部２２を制御する。電子計算部２１に所望するプログラムが入力されると、入力された情報を基に、分子計算部２２において実行する分子計算の計画が生成される。また、目的とする分子計算に必要な分子の設計が行われ、それにより得られた情報を分子計算部２２に伝える。分子計算部２２は、得られた情報に基づき分子計算を行う。例えば、当該分子計算の計画は、記憶部１３に記憶された入力情報と設計される分子計算が対応づけられたテーブルを演算部１４が検索し、対応する計算を選択することによりなされてもよい。また、分子の設計は、記憶部１３に記憶された入力情報と設計される分子が対応づけられたテーブルを演算部１４が検索し、対応する分子を選択することによりなさてもよい。
【００２２】
電子計算部２１側の入力部１１は、例えば、キーボードおよびマウス等の一般的に人が情報を入力することが可能な入力手段の何れかを使用することが可能である。また、電子計算部２１側の出力部２０は、ディスプレイおよびプリンタ等の一般的に情報を出力することが可能な出力手段の何れかを使用することが可能である。
【００２３】
これら計算装置の動作を実現するため、演算部１４は、例えば翻訳・計算計画立案・実行部１４ａ、核酸配列計算部１４ｂ、結果解析部１４ｃなどとして機能する。これら各手段１４ａ〜１４ｃは、例えば記憶部１３から翻訳・計算計画立案・実行プログラム、核酸配列計算プログラム、検出結果解析プログラムが読み出されることにより実行される。また、演算部１４で各種機能を実行させるためのプログラムは、記録媒体に記録されたプログラムプロダクトとして存在し、図示しない記録媒体読取装置により読み取られ、記憶部１３に格納された上で演算部１４で実行されてもよい。また、演算部１４は、これら各手段１４ａ〜１４ｃとして機能する以外にも、通常の電子計算機が実行する手段としても機能する。
【００２４】
更に、分子計算部２２において得られた計算結果の出力は、通信部２４、２３を介して電子計算部２１に送信され、演算部１４などにより所望のデータ処理が施されてもよい。例えば、それらの計算結果は、予め記憶部１３に記憶しておいた処理形式に応じた形式で集計および演算処理される。その演算処理結果は、最終的には出力部１９または出力部２０に所望する形態で出力される。これらの処理の間、分子計算部２２の演算部１５や記憶部１６の状態は、電子計算部２１において通信部２３、２４を介して受信される情報として間接的に把握されている。
【００２５】
一方、分子計算部２２は、実験的に核酸分子を合成したり、合成済みの核酸分子を用いて所望する演算反応を行うことにより分子計算を実行する部分である。
【００２６】
電子計算部２１の演算部１４は、通常の電子計算機の演算部が行う処理に加えて、入力部１１から入力された初期値を符号分子表現に変換すること、計算プログラムの手続または関数を対応する符号分子の演算反応に変換すること、および記憶された計算プログラムから演算反応の実行手順を作成すること等を行う。また、電子計算部２１にて行われることは、例えば、分子の変数への割り当て、試薬などの反応用溶液収容容器の割り当て、分子計算中の反応機器（例えば、ピペットチップなど）や反応用溶液の配置の割り当て、コンテナやピペッタなどの反応機器の移動や操作の割り当て、サーマルサイクラの温度制御の設定、並びに計算の実行シーケンスの決定などである。
【００２７】
以下に更に詳細に本発明を説明する。本発明の計算装置の具体例を図２に示す。図２に示した計算装置は、電子計算部２１と分子計算部２２と核酸合成装置３０からなる。電子計算部２１は通信部２３を、分子計算部２２は通信部２４を備える。これら通信部２３及び通信部２４の間でデータの送受信を行うことにより、電子計算部２１と分子計算部２２との間の情報通信が可能となる。図１の例では、核酸合成装置は分子計算部２２内に組み込まれる場合を示したが、図２では、分子計算部２２とは別個に設けられている。
【００２８】
電子計算部２１の通信部２３は核酸合成装置３０に電気的に接続され、通信部２３から送信された核酸合成命令に基づき核酸合成装置３０が核酸合成を実行できるように構成されている。核酸合成装置３０は例えば通信部２３からの命令に基づき核酸容器や核酸分子を制御する制御部を備える。そして、制御部の制御に基づき合成された核酸は、核酸容器に収容されたまま容器ごと分子計算部２２に搬送される。なお、核酸合成装置３０を分子計算部２２に設けることもできる。この場合、核酸合成装置３０から分子計算部２２に搬送させる搬送系を分子計算部２２とは別個に設ける必要が無い。核酸容器の搬送は搬送機構で行ってもよいし、マニュアルで行ってもよい。
【００２９】
なお、核酸合成装置３０は電子計算部２１と接続しなくてもよい。この場合、電子計算部２１で核酸合成に必要なデータを出力し、その出力結果に基づきマニュアルで核酸合成を行えばよい。
【００３０】
電子計算部２１は、図１の演算部１４に相当する構成として翻訳・計算計画立案・実行部１４ａ、核酸配列計算部１４ｂ、検出結果解析部１４ｃを備える。記憶部１３から所定のプログラムが読み出されることにより演算部１４がこれら各部分１４ａ〜１４ｃとして機能する。また、これら各部分１４ａ〜１４ｃなどと入出力制御部１２を介して入力部１１、図１の出力部２０としての表示部２０ａ及びプリンタ２０ｂが接続される。
【００３１】
分子計算部２２は、図１の演算部１５、記憶部１６、入出力制御部１７、入力部１８、出力部１９として機能する自動制御部１５１、ＸＹＺ制御ピペッタ１５２、サーマルサイクラ反応容器１５３、ビーズ容器１５４、酵素容器１５５、緩衝液容器１５６、核酸容器１５７、検出部１５８、温度制御手段１５９、搬送機構１６０を有する。
【００３２】
分子計算部２２は、通信部２４に接続された自動制御部１５１を備える。この自動制御部１５１は、ＸＹＺ制御ピペッタ１５２と、核酸の反応を実行するサーマルサイクラ反応容器１５３と、ビーズを保持するビーズ容器１５４と、酵素を保持する酵素容器１５５と、緩衝液を保持する緩衝液容器１５６と、核酸を保持する核酸容器１５７、温度制御手段１５９、搬送機構１６０を自動制御するため、これら各構成（１５２〜１５７、１５９、１６０）に駆動信号を出力する。これら各構成（１５２〜１５７、１５９、１６０）は、この駆動信号を受けて駆動することにより、分子の反応や反応条件を制御する。従って、これら各構成（１５２〜１５７、１５９、１６０）は、全体として反応制御部として機能し、それぞれは反応制御要素として機能する。
【００３３】
自動制御部１５１による制御は、通信部２４を介して電子計算部２１から送信された制御命令に基づき実行される。反応容器１５３〜１５７は、ビーカー、試験管若しくはマイクロチューブ等、核酸などを含む溶液を収容する容器であれば何でもよい。
【００３４】
サーマルサイクラ反応容器１５３は、温度調節の可能な反応容器でよい。例えば、一般的に使用されているサーマルサイクラと組み合わせることにより実現可能である。また、この例では、担体としてビーズを用いた場合の例を示したが、他の担体を用いることも可能である。その場合、ビーズ容器１５４に代えてまたはビーズ容器に加えて、適切な構成要素を具備することが可能である。酵素容器１５５は、酵素を失活から守るためにクーラー等の温度制御手段１５９と共に具備されてもよい。必要であれば、他の保持手段にもクーラーまたはヒーター等の温度制御手段１５９を配置してもよい。
【００３５】
サーマルサイクラ反応容器１５３における反応は、制御命令に沿って実行される。例えば、各種容器１５４〜１５７などから所望する容量の内容物をＸＹＺ制御ピペッタ１５２により分取した後、所望する温度等の条件に従って反応が実施される。各部分における動きは、分子計算部内の自動制御部１５１により制御される。ＸＹＺ制御ピペッタ１５２は、自動制御部１５１により制御されて、所望に応じてＸＹＺ方向および／または上下に移動するピペッタである。
【００３６】
搬送機構１６０は、自動制御部１５１からの制御命令に基づき、例えば各容器１５３〜１５７を他の図示しない容器収容手段との間で、あるいは検出部１５８との間で搬送する。
【００３７】
反応終了後、検出部１５８において反応産物の検出および同定が実施される。検出部１５８は、電気泳動装置、シークエンサー、化学発光測光器および蛍光光度計等の一般的に核酸分子を検出および解析するために使用される何れの検出手段または解析手段により実現されてもよい。
【００３８】
電子計算部２１で生成された制御命令は通信部２３に出力される。通信部２３は、これら制御命令を通信部２４を介して分子計算部２２に送信する。分子計算部２２は、受信した制御命令に基づき各構成を制御することにより、分子計算を実行させる。計算結果は通信部２４により、通信部２３を介して電子計算部２１に送信される。
【００３９】
通信部２３、２４は、ケーブル等の有線の通信手段により実現されるものでも、また、電波等の無線の通信手段によって実現されるものでもよい。
【００４０】
電子計算部２１で生成された核酸合成命令は通信部２３に出力される。通信部２３は、これら核酸合成命令を核酸合成装置３０に出力する。核酸合成装置３０は、受信した核酸合成命令に基づき各構成を制御することにより、核酸合成を実行させる。合成の結果物としての核酸分子を収容した核酸容器は分子計算部２２に搬送される。もちろん、核酸容器中の核酸分子のみを分子計算部２２の核酸容器中に運ぶようにしてもよい。
【００４１】
図３は分子計算部２２の配置例を示す図であり、図示しない核酸抽出装置が分子計算部２２に隣接配置され、核酸抽出装置の一部に図示しない搬送装置が設けられている。本発明の一実施の形態では、上記のような構成の分子計算部で行わせる反応の制御を自動的に最適化することを主眼とする。まず、簡単に、図３に示す分子計算部２２について説明する。
【００４２】
分子計算部２２は、大まかに言えば、「入力」である複数の与えられた溶液から始まり、以下のような操作を繰り返し適用することで、「出力」となる新たな溶液（これも複数）を作り出す。これを演算と考えれば、この「出力」である溶液を調べることにより、演算が終了する。この場合、例えば、以下のような操作が行われる。  
（１）特定の溶液を混合して、新しい溶液を作る（Ｍｉｘｉｎｇ、懸濁）。  
（２）溶液から磁気ビーズという仕掛けにより、ある物質（溶液と考えて良い）を取り出す（Ｍａｇｎｅｔｉｃ  ｓｅｐａｒａｔｉｏｎ、磁性粒子分離）。  
（３）溶液を特定の温度にまで暖める（Ｗａｒｍｉｎｇ、温度制御）。  
（４）溶液を特定の温度で一定時間維持する（Ｗａｉｔ、維持）。
【００４３】
ここで、通常の電子計算機との対応を考えると、溶液は通常のプログラミング言語における「値」と考えることが出来る。また、プレートとチップは、この「値」を保持する「変数」に相当するものと考えることができる。プレートは溶液を入れる器である。またチップとはガラス製の先細りの管であり、溶液を保持することが出来る。実際にはチップは複数の管からなり、チップラックというチップを納める複数の穴をもつ容器に置かれており、チップに対する操作はこのチップの１セットに対して同時に行われる。プレートも同様に、複数の管に対応する複数の穴からなり、この穴の各々に溶液が入れられる。
【００４４】
プレートとチップの個数は、基本的に制限はないが、図３に示す分子計算部２２では、８つのテーブルで上記の４つの操作をで行うようになっている。また、上記の（３）の温度制御が可能なテーブルは２つであり、さらに（１）の懸濁や（２）の磁性粒子分離を行うためのＩＭＵという装置は１つしかない。なお、図３における分子計算部２２の主要モジュールは以下の通りである。  
（１）  ＩＭＵ（Ｉｎｔｅｇｒａｔｅｄ  Ｍａｇｎｅｔｉｃ  ｓｅｐａｒａｔｉｏｎ  Ｕｎｉｔ）  
（２）  ストッカ  
（３）  ディスペンサ  
（４）  ターンテーブル  
（５）  ロボットアーム
上記の構成において、ターンテーブルは８個のテーブル（うち２つは温度制御可能）を備えた回転式の装置であり、８個のテーブルのうち１つのテーブルがＩＭＵの直下に来るように配置されている。ＩＭＵはチップを装着し、チップの先細りの下部から溶液を排出し、あるいは吸入することが出来る。また、ＩＭＵは、ターンテーブルの下方にオンオフ可能な電磁石を配置し、プレートの各穴の底部に磁性粒子を選択的に付着させることができる。例えば懸濁という操作は次のように行われる。ＩＭＵがチップを装着して、その下のテーブルに置かれたプレートにチップと別の溶液が入っている状態で、チップ内の溶液の吸入と、排出を繰り返す。磁性粒子分離も同様であるが、溶液にビーズが入っており、ＩＭＵが磁気をかけてビーズをプレートの各穴底部に付着させるという処理を行う。ストッカはプレートやチップラックを提供する装置であり、ディスペンサは溶液を提供(分注)する装置である。またロボットアームはテーブルに置かれたプレートやチップを別のテーブルに移動する装置である。ここで、ＩＭＵは、磁気的な分離を行う他の技術でも良く、例えば、上記のピペット用チップに懸濁液を吸引した後にチップの壁面に磁性粒子を磁気的に付着させて溶液を排出することによっても磁性粒子分離を達成できる。
【００４５】
このような構成において、この８個のテーブルはＣＰＵの「レジスタ」に相当する。溶液である「値」は「変数」であるプレートやチップに保持されるが、それらが処理「演算」対象となるためには８個のテーブルのどれかに割り当てられる必要がある。あるテーブルはその仕事が終わったら、保持している「変数」を破棄し、別の変数を保持することが出来る。また、温度制御は時間のかかる命令であるが、ＩＭＵを必要としないので、その間にＩＭＵは別の仕事を行うことが出来る。
【００４６】
これらを考慮したプログラムの最適化は、いわゆるレジスタアロケーションと命令スケジューリングに他ならない。しかしながら、分子計算部２２に対して、このような最適化を行った例はなく、プログラミングは上述の主要モジュールに対する直接的な命令からなる。このため、分子計算部２２で、反応(演算)を行うためには、ユーザが計画を立てて、個々の反応や各部の動作を記述しなくてかならなので、多くの手間を必要とし、例えば、誤ったプログラムをした場合には、分子計算部２２を破壊する危険もある。そこで、必要な反応のみを記述して、動作を自動化するためには、以下のような事項が要求される。  
（１）  具体的なテーブル番号を意識したくない。  
（２）  必要なくなったプレートやチップは自動的に破棄してほしい。  
（３）  温度制御などに関して、時間的な制約を意識したくない。  
（４）  出来る限りモジュールの並列性を活かしたい。  
（５）  禁止された動作（禁止事項）の検出と排除。
【００４７】
上記の要求を満足するために、本実施の形態では、翻訳・計算計画立案・実行部１４ａが次のような機能を備えている。  
（１）  パーサ  
ユーザは、所定の抽象度で記述出来る高級言語でのプログラミングを行い、パーサは、その意味的な正しさを検証し，禁止事項の検出を行う。そして正しいが最適化されていない分子計算部２２用のコードを出力する。このコードは、レジスタ（テーブル）アロケーションと最適な命令スケジューリングがまだ適用されていないものである。
【００４８】
（２）コード生成系  
パーサが出力したコードを入力とし、最適なレジスタ（テーブル）アロケーションと命令スケジューリングを行い、最終的な分子計算部２２用の命令を生成する。
【００４９】
上記の構成において、まずテーブルのアロケーションと命令のスケジューリングを含む問題を、分子計算部２２に依存しない一般的な抽象度で記述する高級言語（以下、混乱を避けるため、「アセンブラ言語」と称する）を定義するとともに、そのコード生成系を実装することによって、自動的にスケジューリングの最適化を行うことができる。なお、アロケーションとスケジューリングを同時に最適化する手法として、本実施の形態においては、詳細は後述する整数線形計画法（ＩＬＰ）に基づく手法を用いた。このＩＬＰに基づくこのような手法として、ＧｅｂｏｔｙｓたちのＯＡＳＩＳ、ＺｈａｎｇたちのＳＩＬＰがある。これら既存の定式化と実装は通常の計算機を対象としたものであり、命令体系はＲＴＬに摂似の固定されたセットを対象としている。一方本実施の形態においては、アロケーションとスケジューリングが可能な抽象度のアセンブラ言語を対象としている。このため本発明の応用範囲は広いと言える。
【００５０】
本実施の形態に係るアセンブラ言語においては、命令は引数レジスタヘの複数の同時代入の形をしている。既存の手法では命令が定義するレジスタは高々ひとつという条件が必要であったため、本実施の形態では、ＳＳＡ変換を利用して、複数代入も扱えるようにした。また、このことにより全てのリソースをレジスタとして統一約に表現することが可能になった。
【００５１】
（アセンブラ言語の定義）  
まず、テーブルのみをレジスタと考え、基本的な命令について、アセンブラ言語を定めてみる。
【００５２】
（１）  ｎｅｗｐａｌｔｅ（ｔ）、ｎｅｗｒａｃｋ（ｔ）  
テーブルｔに新たなプレート、チップラックを置く。
【００５３】
（２）  ａｔｔａｃｈ（ｔ）、ｄｅｔａｃｈ（ｔ）  
ＩＭＵヘテーブルｔのチップを着、脱。
【００５４】
（３）  ｗａｒｍ（ｔ）、ｗａｉｔ（ｔ）  
テーブルｔの温度制御。
【００５５】
（４）  ｍｉｘ（ｔ）、ｍａｇ（ｔ）  
テーブルｔの溶液でＩＭＵのチップを懸濁、磁性粒子分離。
【００５６】
（５）  ｍｏｖｅ（ｔ１、ｔ２）  
テーブルｔ１上の溶液をテーブルセ２へ移動。
【００５７】
このアセンブラ言語は説明の都合上簡略化されている。例えば、（３）の温度制御の命令では温度を指定する必要があるが、以下の議論で本質的ではないので簡略化している。例えば、３０度まで暖めるのであれば、３０という値を指定する必要があるが、これは命令のパラメータとはせず、命令コードでｗａｒｍ３０（ｔ）のように区別するものとする。すなわち、引数は実レジスタを表す変数（以下、「仮想レジスタ」と称する）に限定する。また、命令の実行時間についての情報は明記されていないが、何らかの方法でコード生成系に提供されているものとする。
【００５８】
上記のように定義されたアセンブラ言語によるプログラム例を以下に示す。ここで、テーブルｔ０にはある溶液の入った（分注済み）プレートが置かれているとする。  
ｗａｒｍ（ｔ１）          ｔ１を暖める（時間かかる）  
ｍｏｖｅ（ｔ０、ｔ１）    ｔ０上の分注済みプレートをｔ１へ  
Ｗａｉｔ（ｔ１）          ｔ１を特綻温度で維持（時間かかる）  
ｍｏｖｅ（ｔ１、ｔ２）    ｔ１上の成果物をｔ２へ  
ｍａｇ（ｔ３）            ｔ３を磁性粒子分離（時間かかる）  
ｍｉｘ（ｔ２）            ｔ２を懸濁（時間かかる）
上記のように記述した命令に対して、コード生成系は実レジスタ（テ−ブル）を割り当て、かつ可能な限り並列実行（例えば、下記のｗａｒｍ（Ｔ３）とｍａｇ（Ｔ２））するように命令をスケジューリングして、例えば、以下のようなアセンブラコ−ドを出力する。なお、以下のアセンブラコードにおいて、横に並べられた命令は並列実行される。ここにおいて、仮想レジスタｔ０、ｔ２には実レジスタＴ１が、ｔ１にはＴ３が、ｔ３にはＴ２が割り当てられている。ｗａｒｍ、ｗａｉｔの引数は温度制御可能なＴ３、Ｔ７から選ばれている。  
ｗａｒｍ（Ｔ３）          ｍａｇ（Ｔ２）  
ｍｏｖｅ（Ｔ１、Ｔ３）  
ｗａｉｔ（Ｔ３）  
ｍｏｖｅ（Ｔ３、Ｔ１）  
ｍｉｘ（Ｔ１）
このアセンブラ言語は直感約で分かりやすいが、コード生成系が実レジスタを割り当てる場合には、レジスタの生存区間解析が必要であるが、上記のような表現では各命令についての知識が必要である。この知識とは、例えば、温度制御に使われるレジスタ（テーブル）は８個あるテーブル中の３、７番のみが割り当て可能であること、ｍｉｘとｍａｇは共にＩＭＵを必要とし、ＩＭＵはひとつしかないので、これらの命令は並列には実行できないということ、等の知識である。また、このアセンブラ言語は、コード生成系の構造が特定の構成（例えば、オリンパス製ＡＰ＿９６）に依存したものになってしまい、汎用性、拡張性に欠ける。
【００５９】
通常のコンパイラにおいては、命令の種類は一定で、その意味は厳密に定義されており、最適化フェーズからコード生成系に至るまで、その知識をもとに処理を行う。対象が通常のコンピュータであるから、あらかじめ定義された命令の組み合わせにより、広範囲の命令を表現することができるので、命令についての知識を処理系が知っている、というアプローチは適切である。しかし、本実施の形態の対象となる分子計算部２２では四則演算のような基本的な操作をあらかじめ想定することは不可能である。このような状況でコード生成を行うための、アセンブラ言語への要求事項として以下が考えられる。  
（１）あらかじめ意味の定まっている命令はない。  
（２）各命令の引数間のデータ依存関係が表現出来る。  
（３）各命令の引数に割り当て可能なレジスタ集合が指定出来る。  
（４）各命令の実行時間が表現出来る。  
（５）各命令の並列実行可能性の表現が出来る。
【００６０】
（汎用的アセンブラ言語）  
上記の要求を満足するような汎用的なアセンブラ言語を導く。まず、Ｃ言語で記述される以下のような命令ｆｏｏを考える。引数の型は割り当て可能なレジスタ集合を表すと考える。例えばｉｎｔ＝｛ｉ１、ｉ２｝等で記述される。  
命令ｆｏｏ（ｌｏｎｇ  Ｘ、ｉｎｔ  ｙ、ｉｎｔ  ｚ）  
意味Ｘ＋＝ｙ＊ｚ＋＋；  
これを純粋な（副作用の無い）関数ｆｏｏ＿１、ｆｏｏ＿２のｘ、ｚへの同時代入の形で表すと、以下のようになる。
【数１】
2005202785.tif 000003
【００６１】
本実施の形態に係るコード生成系から見ると、引数のレジスタ集合、及び引数のデータ依存関係のみあればよい。ここで、ｆｏｏ＿１、ｆｏｏ＿２は副作用のない関数であるから、その詳細がなくても引数のデータ俵存関係は決定できる。よって、それら関数の定義を落した情報をｆｏｏの「型」と考え、以下のように記述する。  
foo : (x:long、y:int、z:int), x=(x,y,z), z=(z)  
この記述のみから、ｆｏｏのデータ依存関係は決定する。
【００６２】
一般的に書けば、オペコードｏｐの型宣言は以下の形となる。
【数２】
2005202785.tif 000004
【００６３】
ここにυｉ：Ｔｉは仮想レジスタυｉに実レジスタの集合Ｔｉのある要素が割り当てられるということを意味する。またυｉ＝（υｊ、‥）はυｉが（υｊ、‥・）に依存することを意味する．先の議論によれば、このυｉ＝（υｊ、…）はυｉ＝ｏｐ＿ｉ（υｊ、…）から関数ｏｐ＿ｉを省略したものである。ここでｏｐ＿ｉの定義が与えられていれば、υｉが単に（υｊ、‥）に依存する、というだけでなく、命令の実行により、引数レジスタの値がどのように変換するのかが決定できる．すなわち、仮想レジスタυｉ、υｊ、υｋの値がそれぞれυｉ０、υｊ０、υｋ０であり、ｏｐの型においてυｉ＝（υｊ，υｋ）があるとき、命令  
ｏｐ（υ１，・・・，υｉ，・・・，υｎ）  
の実行により、仮想レジスタυｉの値はｏｐ＿ｉ（υｉ０、υｊ０）となる。ここで、関数ｏｐ＿ｉの定義が与えられていなくても、それを単なるコンストラクタと見なして命令を実行し、特定の点での特定の仮想レジスタの値をコンストラクタの合成の形で表すことは可能である。
【００６４】
このことを利用して本実施の形態に係るアセンブラプログラムの意味を定義する。アセンブラプログラムの意味とは、プログラム開始時点での各仮想レジスタυの値がυ０であるとし、上記の意味でプログラムを実行し、最後の命令の実行後に、その引数にある仮想レジスタの値のリストがそのプログラムの意味である。
【００６５】
例えば上のｆｏｏの例で、以下のプログラム  
ｆｏｏ（ｘ、ｙ、ｚ）  
ｆｏｏ（ｘ、ｙ、ｚ）  
を実行した後のｘ、ｙ、ｚの値のリストは以下のようになる。
【数３】
2005202785.tif 000005
【００６６】
ここまでで、アセンブラ言語への上記の要求事項の（１）から（３）が満たされることになる。また要求事項の（４）については各命令の実行時間を指定すればよい。各命令の並列実行可能性の表現〈５〉については、有限個（本実施の形態では８個）の実行ユニットをレジスタとして表すことで可能であることを以下に示す。
【００６７】
（レジスタによる装置と制約の表現）
例えば演算装置ＡＬＵが２つあるような場合は、各演算命令の最初にＡＬＵを使うことを以下のように明示すればよい。
【数４】
2005202785.tif 000006
【００６８】
これにより、高々２つの演算命令が並列に実行されることになる。ここでｏｐの型のａ＝（）は、ａに他の引数に依存しない特定の値が代入されることを意味する。実際にＡＬＵに何かが代入されるわけではないが、この型付けにより「この命令はＡＬＵを−瞬だけ使い、ＡＬＵには何も残さない」ということを表現することになる。
【００６９】
例えば以下の例において、ＯＰ１、ＯＰ２の間に誤ったデータ依存関係は生じない。
【数５】
2005202785.tif 000007
【００７０】
すなわちａ＝（）により、各命令のａの生存区間はその命令の実行中のみになる。従って、ＯＰ１、ＯＰ２中のふたつのａは異なる仮想レジスタとみなせるので、同一のレジスタを割り当てることも可能であるし、またそれぞれにＡ１、Ａ２を割り当てて並列に実行させることも可能である。すなわち高々２つの並列実行がなされる。ここでもちろん「可能である」というのは、コード生成系がアロケーションとスケジューリングの双方を考慮しつつ最適化をする際、そのような選択肢が可能である、という意味である。
【００７１】
ここで特にＡＬＵがシングルトン｛Ａ１｝であった場合に生じる制約を考えると、ＯＰ１、ＯＰ２は以前と同様にデータ依存関係を生じないが、同時には実行出来ない、という制約を表現することになる。ある命令とある命令の組み合わせに限り同時実行出来ない、という変則的な制約を、このような方法で記述することが出来る。
【００７２】
またもし上記の型においてａ＝（）がａ＝（ａ）であった場合、ＯＰ２の実行後のａの値はｏｐ２＿１（ＯＰ１＿１（ａ０））なので、ＯＰ１、ＯＰ２の順序は入れ替えられないことになる。これを利用して、２つの命令間の実行順序の制約も型付けにより表現出来る。実行順序の制約は通常データの依存関係により自然に表現されているが、自然に表現出来ない場合でも、仮想的なレジスタ集合を導入することで表現可能となる。
【００７３】
次に入出力装置の型について考える。以下のｏｕｔ（ｏ、ｘ）は何らかの出力装置ｏに、データｘを出力する命令を表現している。
【数６】
2005202785.tif 000008
【００７４】
出力を単なる代入と考えるとｏｕｔの型は  
ｏｕｔ：（ｏ：ＯＵＴ、ｘ：ＤＡＴÅ），ｏ＝（ｘ）  
でも良さそうであるが、そうすると最後の命令でのｏの値はｏｕｔ＿１（ｃ０）となる。すなわちそれ以前のｏｕｔ命令の実行順序の制約がなくなり、コード生成系は誤ったコードを生成してしまう。出力操作により、出力装置の次の状態は出力操作以前の状態と、出力されるデータに依存して決まると考えれば、上の型付けは自然である、
一方、入力操作により、入力装置の次の状態は、入力装置の以前の状態「のみ」で決起するものであるから、入力命令については以下のような型付けになる。  
／＊レジスタ集合＊／  
ＩＮ＝｛Ｉ１｝  
／＊型宣言＊／  
ｉｎ：（ｉ：ＩＮ，ｘ：ＤＡＴＡ）．Ｘ＝（ｉ），ｉ＝（ｉ）
（ÅＮＰ−９６のアセンブラ言語表現）  
以上の議論に基づいて、ＩＭＵを明示し、温度制御可能なテーブルの集合もレジスタ集合として明示して、前述したＡＮＰ−９６アセンブラ言語の例を書き換えると、以下のようになる。なお、型の後ろの数字は実行時間（自然数）の指定である。
【数７】
2005202785.tif 000009
【００７５】
レジスタ集合ＴＢＬとＴ３７は共通の実レジスタが入っている。このようにレジスタ集合同士はｄｉｓｊｏｉｎｔである必要はない．ｎｅｗｐｌａｔｅ（ｎｅｗｒａｃｋ）では新たなプレート（チップラック）がテ−ブルｔに置かれる。命令実行後のｔの値はそれぞれｎｅｗｐｌａｔｅ＿１（）、ｎｅｗｒａｃｋ＿１（）となる。ａｔｔａｃｈ命令ではテーブルｔ上のチップラックに収納されているチップがＩＭＵｉに装着される。この命令の型については、ｔはチップが抜き取られるという変化が起るのでｔ＝（ｔ）であり、ＩＭＵｉには以前のＩＭＵの状態とは無関係にｔ上のチップが装着されるのでｉ＝（ｔ）となる。装着されているチップをテーブルｔに戻すのがｄｅｔａｃｈである。その型については、まずチップがｔに戻されることでｔは変化するが、その結果は、ＩＭＵｉの状態、正確にはそれに取りつけられているチップの状態にも依存するのでｔ＝（ｔ、ｉ）であり、またＩＭＵはチップがはずされて空の状態になるのでｉ＝（）となっている。ｗａｒｍ、ｗａｉｔのテーブルｔはＴ３７でなければならず、ｔの以前の状態に依存した変化が起るのでｔ＝〈ｔ〉となる。ｍｉｘ、ｍａｇはテーブルとＩＭＵの相互的な入出力といった型になる。
【００７６】
上記のようなアセンブラ言語を受取り、コ−ドを生成するコード生成系は以下のような処理系を備えている。  
（１）  入力  
各命令の型と実行時間  
各命令の引数が仮想レジスタであり、並列化されていないアセンブラ命令列
（２）  出力  
開始時刻が付加され、仮想レジスタが実レジスタに置き換えられたアセンブラ命令の集合。
【００７７】
（３）  目的  
プログラムの実行時間の最小化。
【００７８】
（４）  前提  
生存区間の重なる仮想レジスタには同一の実レジスタは割り当てられない。  
先行命令に依存する命令は、全先行命令が終了してから実行される。
【００７９】
仕意個数の命令が同時に実行出来ると仮定（必要な並列性制約の明示的な表現が必要）。
【００８０】
上記の処理系を有するコード生成系の実装について述べる。以後、単にレジスタと言えば実レジスタを表すものとする。
【００８１】
レジスタアロケーションと命令スケジューリングの最適化は互いに排他的であることが知られている。例えば以下の式を考える。  
ｄ＝ａ＊ｂ＋ｃ  
これをロード待ちが１クロックかかるレジスタマシンのアセンブラに変換すると、以下のようになる。  
【数８】
2005202785.tif 000010
【００８２】
ここでまず仮想レジスタυｉにレジスタＲＩを割り当てた後に、命令スケジューリングを行うと以下のようになる。
【数９】
2005202785.tif 000011
【００８３】
一方命令スケジューリングの後にレジスタアロケーションを行うとが以下のようになる。
【数１０】
2005202785.tif 000012
【００８４】
上記のようにふたつの最適化は適用順序により異なる結果となる。一般にｎｏｐを埋めるための命令移動によりレジスタの生存区間は長くなり、結果として多くのレジスタを消費し、レジスタ溢れの可能性が増大する。一方前者の適用順序ではレジスタアロケータがなるべく少ないレジスタで済むように努力する結果、多くのデータ依存関係を作ってしまい、スケジューラが命令を移動出来る余地が少なくなる。
【００８５】
これら両者を同時に考慮した最適化問題はＮＰ＿ＨＡＲＤであることが知られており、効率的なアルゴリズムは存在しない。しかし、整数線形計画法（ＩＬＰ）に基づくものや制約論理型プログラミングによる方法などが提案されており、成功した実装例もある。以下に述べる実装はＳＩＬＰを基に、本発明の実施の形態に沿うよう拡張したものである。
【００８６】
ＩＬＰ〈ＩｎｔｅｇｅｒＩ  Ｌｉｎｅａｒ  Ｐｒｏｇｒａｍｍｉｎｇ〉とは以下のような最適化問題である。ここにＶは整数変数の集合で、以下、ＩＬＰ変数と呼ぶ。υ∈Ｖは目的変数。Ｃは線形制約式の集合である。線形制約式とは整数係数のＶの一時結合を＝または≦で比較した式である。
【数１１】
2005202785.tif 000013
【００８７】
ｓｏｌｖｅｒは与えられたＩＬＰからその最適解を求めるプログラムである。最適解とはＣの全ての制約を満たすような割り当ての中で、目的変数υを最小とするようなものである。
【００８８】
以下、コード生成系をＩＬＰで表現する方法を述べる。まず入力プログラムは、必要な変換や前処理により、以下の形で与えられるものとする。  
【数１２】
2005202785.tif 000014
【００８９】
以後命令ｉ∈ＩｎｓｔとはＰｒｅｇ中のｉ番目にある命令を意味する。Ｖｒｅｇはプログラム中に現れる仮想レジスタの集合であり、前術のＡＮＰ＿９６の例ではＶｒｅｇ＝｛ｔ０、ｔ１、ｔ２、ｔ３、ｉ｝である。Ｒｓｅｔはレジスタ集合の集合であり、先の例ではＲｓｅｔ＝｛｛ＩＭＵ１｝、｛Ｔ１、Ｔ２、・・・、Ｔ８｝、｛Ｔ３、Ｔ７｝｝である。Ｒｓｅｔは仮想レジスタに割り当て可能なレジスタ集合を対応させる関数であり、命令の型宣言から決定する。ｄｕｒａは命令の実行時間である。ｄｅｐは命令ｉが書き込んだ仮想レジスタを命令ｊが参照している場合に生ずる（真の）依存関係であり、型宣言とプログラムの解析から求められる。
【００９０】
また、入力プログラムはＳＳＡ形式で与えられると仮定する。この理由はふたつある。ひとつは逆依存や出力依存のような擬似均依存関係が無くなり、最適化の余地が増えることである。この仮定から、ｄｅｐは真の依存関係のみを考慮する。より大きな理由は、本実施の形態のレジスタアロケーションは仮想レジスタ単位であり、後に説明するＩＬＰへの変換においては、ＳＳＡであるという仮定が必要となるからである。実際の実装では、与えられたプログラムヘの前処理としてＳＳＡに変換している。この仮定より、仮想レジスタυを定義する命令ｄｅｆ（υ）は一意的に定まる。ｒｅｆｓ（υ）はυを参照する複数の命令である。
【００９１】
以上の入力に対して、各命令の開始時点を表すＩＬＰ変数の集合Ｖｂを導入すると、ＩＬＰは実行ステップ数ｓｔｅｐを最小とする以下のような問題となる。
【数１３】
2005202785.tif 000015
【００９２】
ここでＣｓｃｈは命令スケジューリングの制約、Ｃｒｅｇはレジスタアロケーションの制約である。これらの制約の下で、ＩＬＰソルバによりｓｔｅｐが最小となるような解が求められる。Ｖｂ以外のＩＬＰ変数は後述する。以下、ＩＬＰ変数はこのようにタイブライタフォントで表す。またＶ＿ｘのような表現は、イタリック体の変数部分ｘを適当な方法により変換して作ったＩＬＰ変数を表す。
【００９３】
命令スケジューリングの制約Ｃｓｃｈは、下記のようにＩＬＰで自然に表現出来る。  
【数１４】
2005202785.tif 000016
【００９４】
次に、レジスタアロケーションの制約について説明する。本実施の形態に係るアセンブラ言語では、各仮想レジスタυには、ただひとつのレジスタ集合が割り当てられ、レジスタ集合同士はｄｉｓｊｏｉｎｔである必要はない。しかし、後述するようにレジスタアロケーションの制約をＩＬＰで表現するには、レジスタ集合同士はｄｉｓｊｏｉｎｔであり、代わりに各仮想レジスタυには複数の可能なレジスタ集合が対応するとした方が扱いやすい。よって、レジスタ集合の集合Ｒｓｅｔと、仮想レジスタから実レジスタヘの対応関数ｒｓｅｔから作られる、以下の条件を満たす集合Ｒｓｅｔｓ及び関数ｒｓｅｔｓを導入する。
【数１５】
2005202785.tif 000017
【００９５】
この条件を満たすＲｓｅｔｓ、ｒｓｅｔｓは一意的ではない。例えばＲｓｅｔｓ＝｛｛ｒ｝ｌｒ∈Ｒｓｅｔ〉とシングルトンにまで分判してもよいが、ＩＬＰの求解の効率化のためには最小限の分割であることが望ましい。このようなＲｓｅｔｓは以下のアルゴリズムにより求められる。
【数１６】
2005202785.tif 000018
【００９６】
すなわち、最も大きな分剤から始めて、必要となる分割のみを繰り返すのである。Ｒｓｅｔｓが求まれば、関数ｒｓｅｔｓは以下のように定義される。  
【数１７】
2005202785.tif 000019
【００９７】
以後、レジスタ集合といえばＲｓｅｔｓの要素を指す。また、仮想レジスタυのレジスタ集合といえばｒｓｅｔｓ（υ）のある要素を指す。
【００９８】
ここで、レジスタアロケーションの制約Ｃｒｅｇが表現すべきものは、  
（１）各レジスタ集合υ∈Ｒｓｅｔｓの要素数＃ｒを越えた割り当ては出来ない。  
（２）  各仮想レジスタ即は、そのレジスタ集合の要素がひとつだけ割り当てられる。  
（３）  生存区間が重なっている２つの仮想レジスタには異なるレジスタを割り当てる。  
ことである。グラフカラーリング等の手法では、生存区間解析の結果に基づいてアロケーションを行うが、ここではスケジューリング最適化を同時に行うので、そのような解析をあらかじめ行うことは出来ない。そこでまず、項目（３）を除いた制約を表現することを考える。すると項目（１）、（２）のみの制約はＩＩＰの典型的な応用例であるグラフの経路問題として、以下のように表現出来る。
【数１８】
2005202785.tif 000020
【００９９】
ここにυｉはυをレジスタ集合とする仮想レジスタであり、エッジはレジスタの受け渡しを表す。例えばｒ→υというエッジはレジスタ集合ｒからひとつレジスタを取り出し、それをυｉに割り当てる、ということを意味し、υ１→υ２はυ１が使用したそのレジスタを、次にυ２に割り当てる、ということを意味している。また、υ２→ｒは、そのレジスタをｒへ返却するという意味である。以下のようなプール値（０か１）を取るＩＬＰ変数を用意する。  
【数１９】
2005202785.tif 000021
【０１００】
その値が１のときにｘからｙへのエッジが存在するとしてグラフを表現すると、上述の項目（１）はｒから出ていくエッジを表すＩＬＰ変数の総和が＃ｒ以下という線形制約で記述出来、項目（２）は各仮想レジスタｖｉに入ってくるエッジの総和と出て行くエッジの総和が共に１という線形制約で記述出来る。
【０１０１】
以下、項目（３）の表現を含めた詳細を説明する。まず新たに以下のＩＬＰ変数を導入する。
【数２０】
2005202785.tif 000022
【０１０２】
ここにＶ１は各仮想レジスタの生存区間長を表すＩＬＰ変数の集合である。Ｖｒは前述のグラフのエッジを表現するものであり、便宜上、仮想レジスタ間のエッジ（Ｖｒｖｖ）、レジスタ集合から出ていくエッジ（Ｖｒｒｖ）、及びレジスタ集合に入るエッジ（Ｖｒｖｒ）の和集合として定義している。レジスタアロケーション制約Ｇｒｅｇは便宜上Ｃｒｅｇ１からＣｒｅｇ６に分けて記述する。
【数２１】
2005202785.tif 000023
【０１０３】
ここにＣｒｅｇ１はＶｒの値をプール値に制限するものである。Ｃｒｅｇ２は生存区間Ｖ１に関する制約である。ここで以下の補助関数を定義する。
【数２２】
2005202785.tif 000024
【０１０４】
ここにｏｕｔｒ（ｒ）はレジスタ集合υから出ていくエッジ、ｏｕｔυ（υ）は仮想レジスタから出ていく全てのエッジ、ｏｕｔυｒ（υ、ｒ）は仮想レジスタυから出ていくエッジでレジスタ集合ｒのもの、ｉｎυｒ（υ、ｒ）は仮想レジスタυに入ってくるエッジでレジスタ集合ｒのものを、それぞれ表すＩＬＰ変数の集合である。以下がＣｒｅｇの残りである。
【数２３】
2005202785.tif 000025
【０１０５】
ここにＧｒｅｇ３はレジスタ集合υの要素数を越えない、という制約である。またＧｒｅｇ４とＧｒｅｇ５は、各仮想レジスタにただひとつのレジスタが割り当てられるという制約である。Ｃｒｅｇ４において、ｒ∈ｒｓｅｔｓ（υ）はυの本来のレジスタ集合（＝∪ｒｅｓｅｔｓ（υ））の一部なので、その制約式により等しい両辺の値は０または１であり、Ｃｒｅｇ６によりそのυ∈ｒｅｓｅｔｓ（υ）のどれかひとつが割り当てられることになる。最後のＣｒｅｇ６は、もしｘ＿ｒ＿υ１＿υ２＝１すなわち、υ１からυ２ヘレジスタが渡されるのであれば、υ２の定義はυ１の定義後、υ１の生存区間長以上、後でなければならない、という制約である。ここでもし（ｉ、ｊ）∈ｄｅｐであれば、もとものその制約はデータ依存として記述されているはずだから不要である。ここでもしｘ＿ｒ＿υ１＿υ２＝０ならばそのような制約は必要なく、υ１とυ２は生存区間が重なっていてもかまわない。すなわちどうしてもＩＬＰ変数ｘ＿ｒ＿υ１＿υ２の値により制約を「動的に」制御する必要がある。
【０１０６】
次に、ＩＬＰによる条件式の表現方法を説明する。  
ｅをプール値のＩＬＰ変数とし、線形制約式ｅ＝１が満たされた場合のみ、制約式ｅ≧０を有効とするｗｈｅｎ（ｅ＝１）ｅ≧０といった表現は本来ＩＬＰでは記述出来ないが、ＳＩＬＰでは以下のような方法により、この「コーディング」を行っている。  
ｅ≧Ｍ（ｅ−１）
ここにＭは非常に大きな正の定数であり、この式自体は線形制約式である。ここでもしｅ＝１であれば、ｅ≧０であるから、制約が有効となる。またもしｅ＝０ならばｃ≧−Ｍとなる。ここでもしｅの取り得る範囲を見積もることが出来、その最小値よりも−Ｍが小さいなら、事実上この制約はないことになる。Ｃｒｅｇ６の場合であれば、それは最適化されていないプログラムのサイズと各命令の実行時開から見積もることが可能である。
【０１０７】
この手法の拡張として、ｅがプール値で無い場合を考える。まず値が負かどうかをＩＬＰで動的に調べるコード、Ｃで書けば以下のｎｅｇｐ  
＃ｄｅｆｉｎｅ  ｎｅｇｐ（ｘ、ｙ）  ｙ＝＝（Ｘ＜０  ？  １：０）  
は次のように記述できる。  
ｘ≧−ｙＭ  
０≦ｙ≦１
ｘ＜（１一ｙ）Ｍ
同様に以下のｚｅｒｏｐ
＃ｄｅｆｉｎｅ  ｚｅｒｏｐ（ｘ、ｙ）  ｙ＝＝（ｘ＝＝０）  
は次のように記述できる。  
ｎｅｇ（ｘ，ｔ１）  
ｎｅｇ（−ｘ，ｔ２）  
ｙ＝１−ｔ１−ｔ２
０≦ｙ≦１
このような方法は、基本的な枠組みに収まらないような、特殊な制約条件を記述するのに役立つ。
【０１０８】
以上の方法で生成されたＩＬＰをソルバに与えて求解を行う。本実施の形態では商用のＩＬＰソルバであるＮＵＯＰＴを使用した。本実施の形態で導入したＩＬＰ変数で、整数変数でなければならないのはＶｒのみであり、実行時間や実行開始時点は実数でもよく、むしろ機械装置の制御では自然である。ＮＵＯＰＴでは線形制約式に整数変数と実数変数を混在させることが出来る。
【０１０９】
表１はＵｌｔｒａ  Ｓｐａｒｃ１における求解時間である。
【数２４】
2005202785.tif 000026
【０１１０】
各プログラムは図４と同一の命令定義において、表左の式に差し換えて実行した結果である（２番目の式が図４に示したもの）。表の「命令」は式を素朴にコンパイルした結果の命令数、「変数」はＳＳＡ変換後の仮想レジスタ数、「制約」は生成されたＩＬＰ制約式の数、時間は求解時間である。命令や変数のわずかな増加により、実行時間は著しく増大している。本手法の適用範囲を広げるためにも、処理速度の向上が必要である。なお、図４に示すプログラムは分かりやすさのため、簡単な算術式に対するＲＩＳＣ風のアセンブラ命令を例としているが、処理系は宣言で与えられたもの以外、各命令についての知識はない。また、命令実行時問はｌｏａｄとｄｉｖが２単位、他は１単位である。なお、レジスタ集合Ｇは４つの汎用レジスタ、Ｄは２つの処理装置を表す。各命令の引数は、その命令が実行される処理装置を表す仮想レジスタｄｅｖ及び、演算を行う汎用レジスタからなる。
【０１１１】
上記のように、本発明の実施の形態では、分子計算部２２のコード生成系に向けて、従来のコンパイラ技術の枠組みを応用するための抽象的なアセンブラ言語を定義し、そのコード生成系を実装した。そして、コード生成系の実装においては、レジスタアロケーションと命令スケジューリングを同時に最適化するために、ＩＬＰに基づく手法を用いた。
【０１１２】
複数の最適化問題をＩＬＰへ変換して同時に解くことにより、最適化コード生成を行うという既存研究として、アロケーションとスピル処理を同時に解く手法、アロケーションとスケジューリングを同時に解く手法ＯＡＳＩＣ、ＳＩＬＰ、命令選汎アロケーション、スケジューリングを同時に解く手法などがあるが、扱える問題の範囲が広ければ、定式化も複雑になり。処理時間も増大する。
【０１１３】
本実施の形態のコード生成系においては、命令選択やスピル処理は無関係であり、定式化の簡激さからＳＩＬＰをベースとして実装を行ったが、その定式化及び実装と比較して以下の点が異なっている。  
（１）抽象化されたアセンブラ言語を対象とする。  
（２）アセンブラ命令は複数の同時代入からなる。  
（３）全てのリソースは仮想レジスタとして明示的に表現される。  
（４）レジスタ集合間に共通のレジスタがあってもよい。  
（５）仮想レジスタ単位でのレジスタ割り当て。  
（６）ＳＳＡ変換の利用。
【０１１４】
既存の定式化と実装は通常の計算機を対象としたものであり、命令体系はＢＴ１に類似の固定されたセットを対象としている。一方本発明の実施の形態では、アロケーションとスケジューリングが可能な抽象度の言語を対象としているため、応用範囲は広い。また、既存の定式化では演算装置やメモリなどは、通常の計算機を対象としているので、命令中に明示はされない。よってそれらのリソースの割り当ては、レジスタ割り当て同様の処理であるにも関わらず、個別に定式化されている。またその定式化において、命令が定義（代入）する引数レジスタは高々ひとつという前提があり、レジスタアロケーションはレジスタを定義している命令に対してなされている。本実施の形態の場合には、前述のＡＮＰ＿９６の例からも明らかなように、命令が複数の同時代入を表現できる。また、このことから全てのリソースをレジスタとして命令中に明示的に表現し、レジスタ割り当ては命令単位ではなく仮想レジスタ単位で行う。これをＩＬＰで表現するには、仮想レジスタを定義している命令はただひとつという仮定が必要になるが、それはＳＳＡ変換により可能である。また、ＳＳＡ変換をすることにより、従来手法では個別に対応していた逆依存や出力依存といった擬似的なデータ依存を考慮しなくてもよい。
【０１１５】
以上の構成において、分子計算部２２の主要モジュールは種々の変化が可能であり、分子計算を行う装置以外にも、同種及び／又は異種の化学反応を多数並列して実行するような１以上の反応実行装置又は反応計画装置に幅広く適用可能である。また、本発明を化学反応以外の各種応答反応を並列的に扱う装置であっても、応答反応における変数、定数、及び関数等を上述した実施の形態の主旨に応じて適宜対応付けることによって適用が可能となりうる。
【０１１６】
上記の実施形態から下記の発明が抽出できる。なお、下記の各発明は単独で適用しても良いし、適宜組み合わせて適用しても良い。
【０１１７】
本発明の第１局面に係る並列反応実行装置は、電子計算部と並列反応実行部とを具備し、前記電子計算部は通常の計算処理に加えて、実質的に並列反応実行部の機能を制御し、その制御下で多数の反応を並列的に実行する並列反応実行装置であって、前記電子計算部による前記並列反応実行部の制御は、所定の言語で作成された高級言語を前記並列反応実行機の制御命令に変換後に最適化したプログラムで実行されることを特徴とする。
【０１１８】
本発明の第２局面に係る並列反応実行装置は、分子の化学反応により並列反応実行を実行する並列反応実行装置であって、分子の化学反応の反応制御を行う反応制御部を備えた並列反応実行部と、分子を核酸配列に基づき符号化した符号分子に対応付けて定義された変数及び定数と、前記符号分子の演算反応に対応付けて定義された関数により記述されたプログラムを、前記符号分子の演算反応に対応する分子の化学反応の反応制御を行う前記反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成する制御命令生成部と、前記制御命令の手順を出力する出力部とを有する電子計算部を備え、前記制御命令生成部は、所定の言語で作成された前記プログラムを前記制御命令に変換後に最適化することを特徴とする。
【０１１９】
上記の第１及び第２局面において、前記最適化は、ＩＬＰ（整数線形計画法）に基づいて行うことや、上記の第２局面において、前記分子は核酸分子であることが好ましい。
【０１２０】
本発明の第３局面に係る並列反応実行装置は、多数の反応を並列的に実行する並列反応の計画を設計する並列反応実行計画設計装置であって、並列反応の反応原理に対応付けて定義された関数により記述されたプログラムを前記並列反応の反応制御を行う反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成する制御命令生成部と、前記制御命令の手順を出力する出力部とを含み、前記制御命令生成部は、所定の言語で作成された前記プログラムを制御命令に変換後に最適化することを特徴とする。
【０１２１】
本発明の第４局面に係る並列反応実行装置は、分子の化学反応により並列反応実行を実行する並列反応実行の計画を設定する並列反応実行計画設計装置において、分子を核酸配列に基づき符号化した符号分子に対応付けて定義された変数及び定数と、前記符号分子の演算反応に対応付けて定義された関数により記述されたプログラムを、前記符号分子の演算反応に対応する分子の化学反応の反応制御を行う反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成する制御命令生成部と、前記制御命令の手順を出力する出力部からなり、前記制御命令生成部は、所定の言語で作成された前記プログラムを制御命令に変換後に最適化することを特徴とする。
【０１２２】
本発明の第５局面に係る並列反応実行方法は、多数の反応を並列的に実行する並列反応実行方法であって、並行反応の原理に対応付けて定義された関数により記述されたプログラムを前記並列反応の反応制御を行う反応制御部を駆動させるための制御命令に変換して前記制御命令の手順を生成し、前記制御命令の手順を前記反応制御部に出力し、前記制御命の手順に基づき並列反応の反応制御を行うことを特徴とする。
【０１２３】
本発明の第６局面に係る並列反応実行方法は、分子の化学反応により並列反応実行を実行する並列反応実行方法であって、分子を核酸配列に基づき符号化した符号分子に対応付けて定義された変数及び定数と、前記符号分子の演算反応に対応付けて定義された関数により記述されたプログラムを、前記符号分子の演算反応に対応する分子の化学反応の反応制御を行う反応制御部を駆動させるための制御命令に変換後に最適化して前記制御命令の手順を生成し、前記制御命令の手順を前記反応制御部に出力し、前記制御命令の手順に基づき分子の化学反応の反応制御を行うことを特徴とする。
【０１２４】
本発明は、上記各実施の形態に限ることなく、その他、実施段階ではその要旨を逸脱しない範囲で種々の変形を実施し得ることが可能である。さらに、上記各実施形態には、種々の段階の発明が含まれており、開示される複数の構成要件における適宜な組合せにより種々の発明が抽出され得る。
【０１２５】
また、例えば各実施形態に示される全構成要件から幾つかの構成要件が削除されても、発明が解決しようとする課題の欄で述べた課題が解決でき、発明の効果で述べられている効果が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。
【図面の簡単な説明】
【０１２６】
【図１】本発明の一実施の形態に係る分子計算装置の概略構成を示すブロック図。
【図２】本発明の計算装置の具体例を示す図。
【図３】分子計算部２２の配置例を示す図。
【図４】本実施の形態に基づくプログラム例を示す図。
【符号の説明】
【０１２７】
１１…入力部
１２…入出力制御部
１３…記憶部
１４…演算部
１４ａ…翻訳・計算計画立案・実行部
１４ｂ…核酸配列計算部
１４ｃ…検出結果解析部
１５…演算部
１６…記憶部
１７…入出力制御部
１８…入力部
１９…出力部
２０…出力部
２０ａ…表示部
２０ｂ…プリンタ
２１…電子計算部
２２…分子計算部
２３、２４…通信部
３０…核酸合成装置
１５１…自動制御部
１５２…ＸＹＺ制御ピペッタ
１５３…サーマルサイクラ反応容器
１５４…ビーズ容器
１５５…酵素容器
１５６…緩衝液容器
１５７…核酸容器
１５８…検出部
１５９…温度制御手段
１６０…搬送機構
【図１】
2005202785.tif 000027
【図２】
2005202785.tif 000028
【図３】
2005202785.tif 000029
【図４】
2005202785.tif 000030