論理計算システム、生成装置、生成方法及びプログラム
【課題】 多くの論理変数や論理演算を含む複雑な論理計算を高速かつ大量に処理可能な論理計算システム等を提案する。
【解決手段】 ネットリスト記憶部１１１が記憶するネットリストについて、タスクグラフ生成手段１１３は、一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係からタスクグラフを生成する。プログラム生成部１１５は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を追加して、実行プログラム１０５を生成する。情報処理部１０７は、実行プログラム１０５を並列分散処理する。事前に静的にネットリストを処理するため、純計算時では信号線を追跡する必要がなくなる。さらに、SIMD並列化の効率を高めることができる。また、データ転送命令により、タスク間のデータ転送を予め決まったとおりに効率的に行うことができる。
【解決手段】 ネットリスト記憶部１１１が記憶するネットリストについて、タスクグラフ生成手段１１３は、一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係からタスクグラフを生成する。プログラム生成部１１５は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を追加して、実行プログラム１０５を生成する。情報処理部１０７は、実行プログラム１０５を並列分散処理する。事前に静的にネットリストを処理するため、純計算時では信号線を追跡する必要がなくなる。さらに、SIMD並列化の効率を高めることができる。また、データ転送命令により、タスク間のデータ転送を予め決まったとおりに効率的に行うことができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、論理計算システム、生成装置、生成方法及びプログラムに関し、特に、ネットリストなどに基づいて実行プログラムを生成する生成部と、実行プログラムにより論理計算を実行する情報処理部を備える論理計算システム等に関する。
【背景技術】
【０００２】
新たな大規模集積回路（Large Scale Integration，LSI）を開発するにあたっては、そのLSIの設計段階において、ある入力に対するLSIの出力が、開発者の意図するものであることを確かめる必要がある。このテスト作業は、計算機を用いて行われることが多く、LSIの論理シミュレーションと呼ばれる。
【０００３】
テストの対象となる回路は、例えばネットリストのように、それぞれの信号線と素子の関係を表すリストによって表現される。LSIの論理シミュレーションは、内部状態を持ち、過去の状態に依存して出力が変化する順序回路と、そうでない組み合わせ回路とに切り分けて行われる。このうち、組み合わせ回路のテスト計算は、論理積（AND）、否定論理積（NAND）、論理和（OR）、否定論理和（NOR）、否定（NOT）等の論理素子で構成されたループのない回路に、ネットリストによって表現される信号線と論理回路素子との関係を参照しながら、テストデータ（テストデータは、検証対象の論理回路に対して、外部から入力する信号列のシミュレーションパターン集合である。）を入力したときの回路の出力値と、開発者の期待する出力値とを比較することにより行われる。
【０００４】
具体的には、(1)組み合わせ回路のネットリストを参照する、(2)入力信号のテストパターンを読み込む、(3)論理演算によって出力信号を求める、(4)求まった出力と期待する出力とを比較する、という処理を逐次的に繰り返すことによって、論理シミュレーションを行っている。（以下、「従来の並列化手法」という。）
【０００５】
ネットリストは、外部入力信号、外部出力信号、各論理ゲートの種類、各論理ゲートの結線などを表にしたものである。ネットリストを表すデータ構造は、複雑であり、並列化による処理の高速化を行うことは難しい。このため、従来の論理シミュレーションの並列化手法として、まったく同じ論理シミュレーションを行える計算機を複数台用意し、入力信号のテストパターンをいくつかに分割して、それぞれの分割部分を異なる計算機に割り当てるというものがある（非特許文献１など参照）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】X．Wen、外６名著，“Low-Capture-Switching-Activity Test Generation for Reducing IR-Drop in At-Speed Scan Testing”，Journal of Electronic Testing：Theory and Applications，Volume 24，Issue 4，pp.379-391，Aug 2008．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
LSIの論理シミュレーション、不良診断、テスト計算、エキスパートシステムに代表されるアプリケーションでは、このような大量の論理計算を行う必要がある。これらのアプリケーションで扱う論理計算は、論理式が少し複雑になるだけで、急激に計算に時間を要するようになるという特徴を持っている。例えば、論理変数がひとつ増えたとき、その値が真偽の両方の場合についてシミュレーションする必要があるとすると、基本的には計算時間が倍となる。
【０００８】
さらに、昨今のLSIに集約される論理回路素子の数は、集積技術の進歩によって増加の一途をたどっている。一般に、ネットリストは、LSIが大規模になるほど、信号線の追跡に多くの計算を必要とする。集積回路は、計算機の高性能化を追い越す形で、大規模化かつ複雑化している。
【０００９】
しかしながら、従来の並列化手法は、単純に、入力テストデータでの分割による並列化のみ行うものである。そのため、例えば、純計算時（実行インスタンス）における入力テストデータ数が少なければ、多くの計算時間を要してしまうことになる。例えば、入力信号が１ビット増えると、検証すべきテストパターンの数は２倍となるため、計算時間を据え置きたい場合には、同じ性能の計算機が２倍の数必要になる。そのため、従来の並列化手法は、昨今のLSIの論理シミュレーションにおいては、追跡する信号線とテストデータがどちらも増加しているという問題に効果的に対処できない。
【００１０】
そこで、本願発明は、多くの論理変数や論理演算を含む複雑な論理計算を高速かつ大量に処理可能な論理計算システム等を提案することを目的とする。
【課題を解決するための手段】
【００１１】
請求項１に係る発明は、信号線と素子の関係を表すリストに基づいて実行プログラムを生成する生成部と、前記実行プログラムにより論理計算を実行する情報処理部を備える論理計算システムであって、前記情報処理部は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備えるものであり、前記生成部は、前記リストを記憶する記憶手段と、前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成手段を備えるものである。
【００１２】
請求項２に係る発明は、請求項１記載の論理計算システムであって、前記情報処理部は、分散並列処理が可能なものであり、前記プログラム生成手段は、前記同じ処理を行う並列処理可能な前記タスクのうち、前記データ転送命令が追加されなかったものをまとめて実行単位タスク集合とするものであり、前記情報処理部は、前記実行単位タスク集合に含まれる複数の前記タスクをまとめてタスクスケジューリングし、前記データ転送命令に基づくタスク間通信を行って実行するものである。
【００１３】
請求項３に係る発明は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備える情報処理部に、信号線と素子の関係を表すリストに基づく論理計算を実行させるための実行プログラムを生成する生成装置であって、前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成手段を備えるものである。
【００１４】
請求項４に係る発明は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備える情報処理部に、信号線と素子の関係を表すリストに基づく論理計算を実行させるための実行プログラムを生成する生成方法であって、タスクグラフ生成手段が、前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成ステップと、プログラム生成手段が、前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成ステップを含むものである。
【００１５】
請求項５に係る発明は、コンピュータを、信号線と素子の関係を表すリストにおいて、一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、前記タスクグラフにおいてデータ依存関係のある前記タスクの間に複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加しないことにより、前記データ転送命令を備える情報処理部に前記リストに基づく論理計算を実行させるための実行プログラムを生成するプログラム生成手段として機能させるためのプログラムである。
【００１６】
なお、本願発明における情報処理部は、入力信号のテストパターンを与えて計算させることができる複数の実行部を備え、これらに対して、範囲を分けたテストパターンを割りつけることによる並列分散化も併せて用いるものであってもよい。これにより、本願発明に加えて、従来の並列化手法も適用することが可能となる。
【発明の効果】
【００１７】
本願の各請求項に係る発明（以下、「本願発明」という。）によれば、多くの論理変数や論理演算を含む複雑な論理演算を並列分散プログラムとみなすことにより、並列分散処理技術を応用して高速かつ大量に処理することが可能になる。そのため、複雑な論理演算を、例えばGPGPUを搭載したPCクラスタやCell Broadband Engine（Cell/B.E.）を搭載したゲーム機のクラスタのような安価なハードウェアを用いて、高速かつ大量に処理することが可能になる。
【００１８】
すなわち、本願発明によれば、事前のSIMD（Single Instruction Multiple Data）並列化などによって、静的にネットリストを処理するため、純計算時（実行時インスタンス）では信号線を追跡する必要がなくなる。さらに、静的にネットリストを処理する際、同時に処理することができる演算をまとめておくことによって、SIMD並列化の効率を高めることができる。また、データ転送命令により、タスク間のデータ転送を予め決まったとおりに効率的に行うことができる。現在では、論理シミュレーションや不良診断にも多くの計算時間を要するようになっている。そのため、通常単一の高性能計算機における、いままでの論理計算をより高速化したいという需要も高まっている。本願発明は、これに応えることもできる。
【００１９】
さらに、請求項２に係る発明によれば、SIMD並列化に加えて、タスクスケジューリング手法を含む、ワークフロー型並列分散アプリケーションの並列化に関する既存の効率化手法を適用することにより、論理計算を高速化することが可能になる。タスクスケジューリングの手法は、一般に、互いに依存関係があるようなタスクグラフによって表現できる並列分散アプリケーションにおいて、その計算時間の短縮を目的に利用されるものである。本願発明では、ネットリストなどによって表現されるLSIの組み合わせ回路を、並列分散プログラムとみなす。すなわち、組み合わせ回路内で行われる論理演算のそれぞれをタスクとみなし、論理回路素子間の信号線接続をタスク間の依存関係とみなすことで、タスクスケジューリングの手法を用いて高速化することが可能になる。
【００２０】
テスト計算のような計算負荷の高いアプリケーションは、他にも数多く存在する。タスクスケジューリングやタスクのSIMD並列化、スクラッチパッドメモリの記憶領域管理などのキーテクノロジーの研究開発から得られた知見は、他のアプリケーションにも応用できる可能性が高い。そのため、例えば、本願発明を次のように捉えてもよい。すなわち、ノードとノード間のデータ送受信関係を表すリストに基づいて実行プログラムを生成する生成部と、前記実行プログラムにより情報処理を行う情報処理部を備える情報処理システムであって、前記情報処理部は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備えるものであり、前記生成部は、前記リストを記憶する記憶手段と、前記リストにおける一つ又は複数のノードをタスクに置き換えて、各ノードのデータ送受信関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、前記タスクグラフにおいてデータ送受信関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成手段を備えるものである。
【図面の簡単な説明】
【００２１】
【図１】本願発明の実施例における論理計算システムの構成及び動作を説明するための概念ブロック図である。
【図２】図１の論理計算システム１０１の動作の一例を示すフロー図である。
【図３】テスト対象となる組み合わせ回路の一例を示す図である。
【図４】図３の回路に対する図２のステップＳＴ１の処理後のタスクグラフの一例を示す図である。
【図５】図３の回路に対する図２のステップＳＴ２の処理後のプログラムの構造の一例を示す図である。
【発明を実施するための形態】
【００２２】
以下では、図面を参照して、本願発明の実施例について説明する。なお、本願発明は、この実施例に限定されるものではない。
【実施例】
【００２３】
図１は、本願発明の実施例における論理計算システムの構成及び動作を説明するための概念ブロック図である。論理計算システム１０１（本願請求項の「論理計算システム」の一例）は、実行プログラム１０５を生成する生成装置１０３（本願請求項の「生成部」、「生成装置」の一例）と、実行プログラム１０５を実行して情報処理を行う情報処理部１０７（本願請求項の「情報処理部」の一例）を備える。
【００２４】
情報処理部１０７は、複数のタスクの並列分散処理が可能な複数の実行装置１２３1，…，１２３n（以下、添え字は、複数を示す場合には省略する。）と、タスクスケジューリング等により情報処理部１０７の動作を制御する制御装置１２１を備える。情報処理部１０７では、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令によりタスク間通信を行うものである。情報処理部１０７は、制御装置１２１の制御の下で、実行プログラム１０５の並列分散処理を行う。この並列分散処理では、タスクスケジューリングの手法を用いることで、複数の計算機を活用し、計算の効率化を図ることができる。
【００２５】
生成装置１０３は、ネットリスト（本願請求項の「リスト」の一例）を記憶するネットリスト記憶部１１１（本願請求項の「記憶手段」の一例）と、ネットリストに基づいてタスクグラフを生成するタスクグラフ生成部（本願請求項の「タスクグラフ生成手段」の一例）と、タスクの間にデータ転送命令を追加して実行プログラム１０５を生成するプログラム生成部１１５（本願請求項の「プログラム生成手段」の一例）を備える。生成装置１０３は、事前にネットリストを静的に処理し、SIMD並列化することによって、LSIの大規模化に伴う信号線追跡の繰り返しをなくすことができる。
【００２６】
まず、情報処理部１０７の一例について、具体的に説明する。情報処理部１０７は、一つのプロセッサのようなものでもよく、複数の独立した装置が処理を行うものであってもよい。例えば、昨今のマイクロプロセッサは、回路の複雑化、高密度高集積化、高クロック化のために、消費電力と発熱量の増大が問題視されており、単一のプロセッサコアの性能向上はすでに頭打ちの状況にある。このため、現在では、一つのプロセッサに複数個のコアを搭載し、並列処理を行うことによって全体としての処理能力向上を狙う、マルチコア構成のプロセッサが主流となっている。
【００２７】
特に、ヘテロジニアスマルチコアと呼ばれる新しいプロセッサの構成は、単体で高性能化された制御用のプロセッサコアを１個から数個、SIMD演算などの特定の処理を高性能化した多数の演算用のコアを同時に含むことによって、多様なタイプのプロセッサコアを、スケジューラにより適材適所で有効利用することができる。また、複雑化し過ぎたプロセッサコアの構造を単純化することによって、高クロック化、パイプライン化と、省電力と発熱量の低減の両立を実現している。ヘテロジニアスマルチコアプロセッサは、異なるアーキテクチャのプロセッサコアを組み合わせて一つのプロセッサを構成することにより、アーキテクチャ毎の弱点を補い合って、アプリケーション全体の処理効率を高めることができる。
【００２８】
例えば、GPGPU（General-Purpose computing on Graphics Processing Units（グラフィックス・プロセッシング・ユニットによる汎目的計算））は、本来は画像処理を行うための補助演算装置であるGPUの演算能力を、画像処理以外の汎用な目的に利用できるようにするための技術である。最近のデスクトップアプリケーションでリアルタイムに行われる画像処理は、３次元描画を含むレンダリングアルゴリズムの高度化と、画面の高精細化・高解像度化、高フレームレート化によって、非常に負荷が高くなっている。これらのアプリケーションの要求に応えるために、GPUには高性能なメモリと強力な演算器を集積されている。また、デスクトップアプリケーションで行われる３次元グラフィックスの描画には、行列演算を中心としたSIMD演算や、浮動小数点の演算が非常に多く含まれ、描画性能の向上のために、GPUはSIMD演算と浮動小数点演算の性能が特に高められている。また、GPUベンダーからGPGPUのための技術情報、プログラミング環境、フレームワーク等が公開され、計算負荷の高いさまざまな実用アプリケーションにも応用され始めている。特に、ハイパフォーマンスコンピューティングの分野で注目され、科学技術計算を行うPCクラスタに搭載される機会が多くなっており、最近はスーパーコンピュータにおいても計算ノードの構成に含まれることが多い。
【００２９】
また、例えば、ソニー・コンピュータエンタテインメント社が開発したヘテロジニアスマルチコアプロセッサであるCell/B.E.は，PowerPCアーキテクチャのプロセッサコア（PowerPC Processor Element（PPE））１個と、SIMD演算の性能に優れた演算用のコア（Synergistic Processor Element（SPE））８個を有している。各プロセッサはメインメモリや入出力デバイス、グラフィックデバイスと、Element Interconnect Bus（EIB）と呼ばれる高速なバスで接続されており、各プロセッサはEIBを経由してデータアクセスを行う。これにより、消費電力や発熱量を抑えながらも、従来のプロセッサに比べて高速に加減算や論理演算のような基本演算処理を、複数同時に行うことが可能である。
【００３０】
PPEは、64ビットPowerアーキテクチャの汎用的なプロセッサである。従来のプロセッサと同様にOSの駆動等を行うことが可能だが、特にCell/B.E.においては演算を行うSPEを制御する役割を担っている。後述する実験では、Powerアーキテクチャ上のTime Base Register（TBR）を用いて計算時間の計測を行った。
【００３１】
SPEは、SIMD型アーキテクチャを採用しており、SIMD演算に特化している。SPEは演算装置であるSynergistic Processor Unit（SPU）とMemory Flow Controller（MFC）から構成されている。SPEは、メインメモリに直接アクセスできないが、それぞれのSPEがSPU内に256KiBのLocal Store（LS）と呼ばれる専用のメモリを持つ。そのため、SPEがメインメモリを参照するときは、Direct Memory Access（DMA）を用いてメインメモリとLSとの間でデータ転送を行う。この転送処理は、MFCが行う。（この転送処理が、本願請求項の「データ転送命令」に基づく処理の一例である。）SPUには、プロファイリングのために利用できる、SPU Decrementerというレジスタがある。後述の実験では、このレジスタを用いて計算時間の計測を行った。例えば、OpenCLは、GPGPUやIAサーバを含む異機種並列分散環境で並列分散アプリケーションを実行するためのフレームワークである。OpenCLは、互いに依存関係を持つタスクをタスクスケジューリングする機構を持たない。そのため、単体では、図１の情報処理部１０７を構成することはできない。しかし、図１の実行装置１２３として、OpenCLを含む既存の異機種並列分散環境を用いて実装することは可能である。
【００３２】
Cell/B.E.上のプログラミングで特に有効な技法として、ループ展開、ダブルバッファリングについて説明する。ループ展開とは、繰り返しの処理を展開してループ回数を減らすことで、ループ制御によるオーバーヘッドを減らし、プログラムの実行を高速化する手法である。SPEはSIMD演算に特化しているため、プログラムの制御を得意としていない。ループ展開を行うことで、その制御を減らすことができ、SIMD演算を効率よく行うことができる。そのため、SPE上の計算で特に有効な技法である。ダブルバッファリングとは、データを格納するバッファを２個用意し、バッファを入れ替えながら処理とデータ転送を並列に行うことで、入出力の待ち時間を削減し、実行を高速化する手法である。PPEとSPEとの間のDMA転送は、SPE内のMFCが処理を行うため、データ転送中にSPUは他の処理を行うことが可能である。ダブルバッファリングを用いて、DMA転送と演算を並列に行うことで、SPEの通信待ち時間を削減することができる。
【００３３】
続いて、SIMD並列化について説明する。SIMD演算は、一つの命令でいくつかの数のデータに対して一度に処理を行う演算の一方式である。（SIMD命令でない）汎用な命令は、汎用のソースレジスタと汎用のデスティネーションレジスタにそれぞれ与えられる単一のデータに対して、定められた処理を行った後、デスティネーションレジスタに結果を格納するという処理を行う。それに対して、SIMD命令では、ソースレジスタとデスティネーションレジスタとして専用のSIMDレジスタを持ち、レジスタに格納された連なる複数のベクトルデータに対して、定められた処理を一度に行う。旧来の汎用な命令による演算を、SIMD演算に置き換えることをSIMD並列化という。SIMD演算に適した処理をSIMD並列化することによって、効率化を図ることができる。
【００３４】
SIMD演算の特色は、長いベクトル長を持つSIMDレジスタに格納されたデータを、一命令で一度に、画一的に処理できるということにある。演算するデータの長さがSIMDレジスタ長に満たない場合は、その分だけ演算時間にロスが生じてしまう。このため、演算するデータは、出来るだけまとめてSIMD演算するというのが普通である。特に条件分岐や繰り返しは、その条件の判定に逐次的な処理を含み、SIMD演算の効率を下げてしまうため、これらを取り除く（可能な限り必要のない形にする）ことによって、さらに効率化を図ることができる。
【００３５】
続いて、図２を参照して、図１の論理計算システム１０１の動作の概要について説明する。図１の論理計算システム１０１は、ネットリストで表現される回路を並列分散プログラムと考え、準備段階（コンパイルおよび最適化と同時に行うことが可能）として、事前にSIMD並列化を行う。すなわち、生成装置１０３において、タスクグラフ生成部１１３がタスクグラフ生成処理を静的に行い（図２のステップＳＴ１）、プログラム生成部１１５がSIMD並列化、最適化等を静的に行う（図２のステップＳＴ２）。そのため、静的にネットリストを処理することから、純計算時には信号線の追跡を行う必要がない。さらに、同時に処理できる演算を静的にまとめることにより、SIMD演算の効率を良くすることができる。その後、情報処理部１０７が、並列分散処理（図２のステップＳＴ３）を行う。そのため、タスクスケジューリング手法を含む既存のワークフロー型並列分散プログラムの効率化のさまざまな手法を応用することができる。
【００３６】
続いて、図３及び図４を参照して、図２のステップＳＴ１の処理の一例について具体的に説明する。図３は、テスト対象となる組み合わせ回路例（以下、「テスト対象回路」という。）を示す図である。図１のネットリスト記憶部１１１は、図３の検査対象の論理回路の設計データ（ネットリスト）を記憶している。図３のテスト対象回路は、信号線１、２、３、４、２８、２９及び３０を入力信号とし、素子１０、１５、１６及び１８の出力信号を出力信号とする。素子９は否定であり、信号線１の信号を反転する。素子１１は、素子９の出力信号と信号線２９の論理積を演算する。素子１７は、信号線２と信号線３０の否定論理和を演算する。素子１８は、信号線３の信号と素子１７の出力信号の否定論理和を演算する。素子１２は、素子１７と素子１１の出力信号の論理和を演算する。素子１３は、素子１１の出力信号と信号線４の信号の論理和を演算する。素子１４は、素子１２と素子１３の否定論理積を演算する。素子１６は、素子１４の出力信号と信号線２８の信号の否定論理積を演算する。素子１０は否定であり、素子１６の出力信号を反転する。素子１５は、素子９と素子１６の出力信号の否定論理和を演算する。
【００３７】
図４は、図２のステップＳＴ１の処理において、図３のテスト対象回路から作成されたタスクグラフの一例を示す図である。タスクとは、プログラム内のループやサブルーチン等のまとまった処理単位のことである。プログラムのそれぞれのタスクの間には、データ依存等の実行順序に関する制約がある。プログラムは、この依存関係を用いてタスク間を繋いだグラフとして表すことができる。これをタスクグラフと呼ぶ。プログラムをタスク単位に分割し、ネットワークで接続された計算機資源にタスクを割り当てることで、並列分散計算を行うことができる。
【００３８】
図４では、各素子をタスク（本願請求項の「タスク」の一例）に割り当てている（すなわち、一つの素子をタスクに置き換える。）。そのため、各タスクの依存関係は、図３と同様である。なお、計算に必須ではないが、タスクグラフは実行する際に計算時間が短くなるように最適化することが可能である。例えば、同一の論理演算タスクをまとめることができることができるならば、ひとつにまとめて、より長いベクトル長のSIMD演算タスクにする（すなわち、複数の素子を一つのタスクに置き換える。）。また、可能ならば、クリティカルパス長を短く、並列度を増すようにグラフを変換する。こうして生成されたタスクグラフは、互いに制御依存およびデータ依存関係を含むタスクから構成される並列分散プログラムとみなすことができる。
【００３９】
本願発明は、組み合わせ回路を、その論理演算をタスクとし、論理回路素子間の信号線を依存関係としたタスクグラフとみなす。タスクグラフは、重み付き有向非循環グラフ（Directed Acyclic Graph）G=(V,E)で表わすことができる。Vはノードの集合を表し、SIMD演算器を用いた論理演算を行うタスクに射影される。Eはタスクから別のタスクの有向辺の集合を表し、タスク間のデータ通信に射影される。ただし、有向辺は、循環を作らないものとする。従来は、シミュレーション時にすべての計算機が信号線の追跡を行っていた。それに対し、本願発明では、タスクグラフの生成処理は、ネットリストに変更がない限り最初の実行前に一度だけ行えば良く、テストデータに依存しない。そのため、信号線の追跡は、タスク割り当てを行うより以前の一回のみでよい。事前にネットリストを静的に処理し、タスクグラフを生成することで、シミュレーション時の信号線の追跡処理を削減することができる。また、回路をタスクグラフとして扱うことで、タスクスケジューリングの手法を用いて並列分散計算を効率よく行うことができる。
【００４０】
続いて、図５を参照して、図３のテスト対象回路に対する図２のステップＳＴ２の処理の一例について具体的に説明する。同じ論理演算を行うタスクは、互いに依存関係が無ければ、それらをまとめて処理することで、タスク割り当ての時間を削減できる。また、まとめたタスクは、SIMD演算によって、多くのテストパターンを効率よく計算することができる。
【００４１】
図４では、論理素子による処理の種類は、論理積（AND）が素子１１、否定論理積（NAND）が素子１４及び１６、論理和（OR）が素子１２及び１３、否定論理和（NOR）が素子１５、１７及び１８、否定（NOT）が９及び１０である。このうち、素子１４と１６の間には依存関係がある。素子１７と１５・１８との間にも依存関係がある。素子９と１０の間にも依存関係がある。素子１２及び１３は、同じ処理（論理和）であり、依存関係がない。そのため、これらは、SIMD演算によって処理が可能である。また、素子１５と１８も、同じ処理（否定論理和）であり、依存関係がない。そのため、これらも、SIMD演算によって処理が可能である。図５では、データ転送命令を追加している（データ転送命令１５１、１５３、１５５、１５７及び１５９は、データ依存関係のあるタスクの間に追加されたものであり、本願請求項のタスクグラフにおいてデータ依存関係のあるタスクの間に追加された「データ転送命令」の一例である。）。データ転送命令は、例えば、SPE_shuffle命令である。データ転送命令は、例えば、論理演算をSIMD並列化するため、後続タスクが異なる同種の演算を行うタスクをひとつにまとめたとき、行き先に応じて出力データを分配する。また、出力データのコピーや移動ができる。さらに、データ並列により多くのテストデータを同時に計算することにより、高速化するだけではなく、１回あたりに要する計算時間を短くすることもできる。このデータ転送命令により、タスク間のデータ転送は、タスク間通信を用いて、予め決まったとおりに効率よく行うことができる。図５では、素子１２及び１３に対応するタスクをタスク集合（本願請求項の「実行単位タスク集合」の一例）とし、SIMD演算によってまとめて処理することで、タスク割り当ての時間を削減することができる。素子１５及び１８に対応するタスクについても同様である。
【００４２】
なお、図５では、素子１２及び１３に対応するタスクは、素子１４に対応するタスクの前提として処理するものであり、異なるタイミングで処理すると、クリティカルパスが長くなり、トータルの計算量が増加する可能性が高い。そのため、同時に処理することが望ましいと考えられる。他方、素子１５及び１８に対応するタスクは、別のタイミングで行っても、クリティカルパスの増加は認められない。そのため、図５にあるように、素子１５及び１８に対応するタスクは、同じタイミングで処理する（これらのタスクの間にもデータ転送命令を追加しない）ようにしてもよく、また、異なるタイミングで処理する（一部のタスクの間にはデータ転送命令を追加する）ようにしてもよい。このように、同じ処理を行い、並列に処理可能な場合であっても、全部にデータ転送命令を追加しないようにしてもよく、一部にのみ追加しないようにして残りにはデータ転送命令を追加するようにしてもよい。このようにして、図１のプログラム生成部１１５は、実行プログラム１０５を生成することができる。
【００４３】
本願発明の高速化の手法に加えて、計算機に合わせてSIMD最適化や並列化コンパイラによる最適化等、様々な最適化を行うことができ、タスクの処理を高速化することができる。例えば、SIMD最適化とは、計算時に積極的にSIMD命令を用いる、メモリのアラインメントを調整する等、SIMD演算を効率よく行えるようにすることである。プログラムのソースコード自体に変更を加える手法、また、コンパイラが自動的に行うものがある。並列化コンパイラとは、複数のプロセッサを持つ計算機等、同時に複数の演算処理を行える環境で、並列に処理を行うように、自動的にコードを変換するコンパイラである。並列に処理を行うプログラムでは、複数の処理が同じデータ領域を用いる等、排他制御が必要となる。このようなプログラムのコードを書くことは非常に手間がかかり、並列処理を最適に行うことは難しい。並列化コンパイラを用いて自動的にコードを変換することで、この手間を無くし、最適に並列処理を行うことができる。
【００４４】
続いて、図１の情報処理部１０７の動作について説明する。制御部１２１は、実行装置１２３に、動的スケジューリングを用いてタスクを割り当てる。実行装置１２３は、SIMD演算等を用いてタスクを実行する。そして、求まった出力は、期待する出力と比較される。
【００４５】
実行プログラム１０５は、高速化や大容量のメモリを使いたいなどの目的のために、ループやサブルーチン、ブロックなどのまとまった処理単位（タスク）に分割されている。並列分散環境は、ネットワークで接続された異機種の並列計算機群である。並列分散環境では、計算機資源（ネットワーク、主記憶、プロセッサ）をタスクに割り付けて利用することにより、タスクを実行する。タスク同士は、データ依存や処理依存等の依存関係を持つ。例えば、あるタスクを並列分散環境における適当な計算機資源を用いて実行するためには、実行に必要となるパラメータを先行するタスクで計算し、ネットワークを使って結果を計算機資源に転送する必要がある。並列分散計算を構成するタスクは、これらの依存関係を満たしながら、計算機資源に割り付けられて実行される。計算時間は、この割り付け方により大きく変化する。この計算時間を短くするため、タスクをどの計算機に割り当てるか、スケジューラが適切に選択する必要がある。このようなタスクの割り当てをタスクスケジューリングと呼ぶ。計算時間の短縮化等のため、様々なスケジューリング手法に関する研究が行われている。しかし、一般的な並列分散計算におけるタスクの割け方の最適解を求める問題は典型的なNP困難の計算クラスに属するため、解を求めることは不可能である。このため、タスクスケジューラ（タスクに依存関係を満たしながら，プロセッサや記憶領域等の計算機資源に割り付ける実行時ミドルウェア）は、ヒューリスティックな手法により得た準最適解を利用している。
【００４６】
図１の情報処理部１０７は、動的にスケジューリングを行い、タスクグラフにおけるタスクを実行する。図１の実行装置１２３は、例えば、PC、Cell/B.E.、GPGPU搭載PCを含むローカルエリアネットワークで接続された異機種構成のPCクラスタをハードウェア・プラットホームであってもよい。図１の情報処理部１０７は、ハードウェア・プラットホーム上のSIMD型演算器にタスクを割り付け、論理演算を効率的に行う仕組みを分散ミドルウェアとして実装する。分散ミドルウェアの役割は、後述するタスクスケジューラからの指令に基づき、指定されたタスクを指定されたSIMD型演算器に割り付ける。具体的には、タスクスケジューラから指定されたプログラムを二次記憶装置からロードして実行する。タスクの実行に必要なデータは、他のタスクまたは外部初期入力データとして与えられる。タスクスケジューラは、演算器間の通信時間や演算器における計算時間も考慮しながら、全体の計算時間が小さくなるように、タスクをヘテロジニアスマルチコアプロセッサやGPGPUにおけるSIMD型演算器に割り付ける。この種のタスクスケジューリングの最適化問題は一般に解くことができない（NP困難問題）ため、クリティカルパス上のタスクを最優先する方法をベースにするヒューリスティックな方法を用いる。
【００４７】
タスクスケジューラは、制御依存およびデータ依存関係が満足され実行可能となったタスクのうち、出口ノードまでの距離が最短となるタスクを高い優先順位で実行するクリティカルパス法を基本とする動的タスクスケジューリング手法でスケジューリングを行い、ネットリストを並列分散プログラムとしてハードウェア・プラットホーム上で並列分散実行する。
【００４８】
本願発明では、タスク割り当てを動的にスケジューリングすることで、論理シミュレーションの計算時間を短縮する。動的スケジューリングとは、実行時に行うタスク割り当ての際に，手法ごとに決めたポリシーに従い、特定の目的関数（例えば計算時間や計算コスト）を最小化するようにタスクを割り当てる計算機を決定するスケジューリング手法である。動的スケジューリングでは、タスクを割り当てる計算機を決定する際に計算時間が必要になるが、１スケジューリングタイムインスタンスあたりに必要な時間は、経験的に１ミリ秒程度であり、SIMD演算とのオーバーラップも可能である。動的スケジューリングには、例えば、クリティカルパス(CP)法がある。クリティカルパス(CP)法とは、クリティカルパス上のタスクを優先的に割り当てるスケジューリング手法である。このスケジューリング手法では、タスクを割り当て時に、その時点でのクリティカルパス長を計算し、タスク割り当てを動的に行う。
【００４９】
続いて、本願発明の評価のため行った、２つの実験について説明する。まず、従来の手法による論理シミュレーションに要する計算時間を計測した（以下、「従来手法の評価実験」という。）。続いて、本願発明による論理演算の計算時間を計測した（以下、「本願発明の評価実験」という。）。前者は、信号線追跡の時間に関する評価を目的とするものである。後者は、SIMD演算の高速化の評価を目的とするものである。
【００５０】
従来手法の評価実験では、従来の手法における計算に必要な時間を計測した。従来手法は、計算を行う際に毎回信号線の追跡を行っており、何度も同じ処理を繰り返すという無駄がある。この実験では、従来手法の処理全体に要する時間と論理演算に要する時間を計測し、信号線追跡が処理時間に占める割合を調べた。
【００５１】
この実験では、ネットリストを読み込み、表として管理し、この表を参照することで信号線の追跡を行った。プログラム実行後、gprofを用いてプロファイリングを行い、処理全体に要した時間、論理演算部分に要した時間をそれぞれ計測した。この実験の結果を表１に示す。従来の手法においては、論理演算は実験全体のうち約35％を占めていることが確認できた。論理演算部分以外に要した時間1.28秒のうち、I/O関係の処理（ネットリストやテストパターンの読み込み、結果の出力）を除いた時間は、主に信号線の追跡に要した時間である。この時間は、提案手法を用いることで削減できる。また、本実験で論理演算に要した時間0.69秒について、本願発明ではSIMD並列化して論理演算を行うため、この時間を短縮することができる。よって、本願発明により、例えば論理演算をCell/B.E.上のSPEを用いてSIMD並列化した場合、同じ計算をPPE上で行った場合に比べて２倍から３倍高速化可能である。さらに、論理演算がシミュレーション全体のおよそ４割を占めるものの、本願発明では信号線追跡にも多くの時間が割かれており、信号線追跡を削減する提案手法によって高速化することができる。
【００５２】
【表１】
【００５３】
本願発明の評価実験では、全体の処理のうち、論理演算の部分をSIMD並列化し、さらにSIMD演算に特化したプロセッサを用いて、SIMD演算を高速に行うことで全体の計算時間を短縮した。この実験では、SIMD演算に特化したプロセッサであるSPEを搭載したCell/B.E.を用いて、本願発明の計算時間を計測した。実験では、PPEとSPEのそれぞれでSIMD命令セットを用いたAND演算を行うため、32MiBのテスト用ベクトルデータ２つを用意する。この２つのテスト用ベクトルデータのANDをとる演算を行い、その計算時間を計測した。SPEの計算では、ダブルバッファリングを用いたため、処理全体の計算時間と計算部分のみの両者を計測し、比較することで、ダブルバッファリングの効果を調べた。同様に、ループ展開に関して、展開を行う場合と行わない場合とを比較し、ループ展開による計算時間の減少を調べた。それぞれ計算時間の計測には、PPEではTBR，SPEではSPU Decrementerをそれぞれ用いた。
【００５４】
この実験の結果を表２に示す。SPEの処理全体の時間と計算部のみの時間とを比較すると、その差は1ミリ秒以下であり、ダブルバッファリングを用いることで、PPEとSPEとの間のDMA転送に要する時間は、計算時間でオーバーラップが可能であることが確認できた。また、PPEとSPEの計算の速さを比較すると、ループ展開を行う場合ではSPEはPPEの約3.1倍、ループ展開を行わない場合は約2.6倍の速さとなっている。このことから、SPEのようなSIMD演算を高速に行うことができるプロセッサを用いることで、論理演算を高速に行え、本願発明のSIMD並列化が有効であることが確認できた。SIMD演算では、ループ展開によりSIMD演算器を有効に利用すると効果的であるから、本実験で実際にループ展開を行う場合と行わない場合を計測し、比較したところ、PPE，SPEはどちらも計算時間が短くなり、ループ展開がSIMD演算の高速化に効果的であることが確認できた。
【００５５】
【表２】
【産業上の利用可能性】
【００５６】
本願発明は、LSIの論理シミュレーション、不良診断、テスト計算、エキスパートシステムをはじめとする論理演算を高速かつ大量に行う論理計算に利用可能である。
【符号の説明】
【００５７】
１０１ 論理計算システム、１０３ 生成装置、１０５ 実行プログラム、１０７ 情報処理部、１１１ ネットリスト記憶部、１１３ タスクグラフ生成部、１１５ プログラム生成部、１２１ 制御装置、１２３1，…，１２３n 実行装置、１５１，１５３，１５５，１５７，１５９ データ転送命令
【技術分野】
【０００１】
本発明は、論理計算システム、生成装置、生成方法及びプログラムに関し、特に、ネットリストなどに基づいて実行プログラムを生成する生成部と、実行プログラムにより論理計算を実行する情報処理部を備える論理計算システム等に関する。
【背景技術】
【０００２】
新たな大規模集積回路（Large Scale Integration，LSI）を開発するにあたっては、そのLSIの設計段階において、ある入力に対するLSIの出力が、開発者の意図するものであることを確かめる必要がある。このテスト作業は、計算機を用いて行われることが多く、LSIの論理シミュレーションと呼ばれる。
【０００３】
テストの対象となる回路は、例えばネットリストのように、それぞれの信号線と素子の関係を表すリストによって表現される。LSIの論理シミュレーションは、内部状態を持ち、過去の状態に依存して出力が変化する順序回路と、そうでない組み合わせ回路とに切り分けて行われる。このうち、組み合わせ回路のテスト計算は、論理積（AND）、否定論理積（NAND）、論理和（OR）、否定論理和（NOR）、否定（NOT）等の論理素子で構成されたループのない回路に、ネットリストによって表現される信号線と論理回路素子との関係を参照しながら、テストデータ（テストデータは、検証対象の論理回路に対して、外部から入力する信号列のシミュレーションパターン集合である。）を入力したときの回路の出力値と、開発者の期待する出力値とを比較することにより行われる。
【０００４】
具体的には、(1)組み合わせ回路のネットリストを参照する、(2)入力信号のテストパターンを読み込む、(3)論理演算によって出力信号を求める、(4)求まった出力と期待する出力とを比較する、という処理を逐次的に繰り返すことによって、論理シミュレーションを行っている。（以下、「従来の並列化手法」という。）
【０００５】
ネットリストは、外部入力信号、外部出力信号、各論理ゲートの種類、各論理ゲートの結線などを表にしたものである。ネットリストを表すデータ構造は、複雑であり、並列化による処理の高速化を行うことは難しい。このため、従来の論理シミュレーションの並列化手法として、まったく同じ論理シミュレーションを行える計算機を複数台用意し、入力信号のテストパターンをいくつかに分割して、それぞれの分割部分を異なる計算機に割り当てるというものがある（非特許文献１など参照）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】X．Wen、外６名著，“Low-Capture-Switching-Activity Test Generation for Reducing IR-Drop in At-Speed Scan Testing”，Journal of Electronic Testing：Theory and Applications，Volume 24，Issue 4，pp.379-391，Aug 2008．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
LSIの論理シミュレーション、不良診断、テスト計算、エキスパートシステムに代表されるアプリケーションでは、このような大量の論理計算を行う必要がある。これらのアプリケーションで扱う論理計算は、論理式が少し複雑になるだけで、急激に計算に時間を要するようになるという特徴を持っている。例えば、論理変数がひとつ増えたとき、その値が真偽の両方の場合についてシミュレーションする必要があるとすると、基本的には計算時間が倍となる。
【０００８】
さらに、昨今のLSIに集約される論理回路素子の数は、集積技術の進歩によって増加の一途をたどっている。一般に、ネットリストは、LSIが大規模になるほど、信号線の追跡に多くの計算を必要とする。集積回路は、計算機の高性能化を追い越す形で、大規模化かつ複雑化している。
【０００９】
しかしながら、従来の並列化手法は、単純に、入力テストデータでの分割による並列化のみ行うものである。そのため、例えば、純計算時（実行インスタンス）における入力テストデータ数が少なければ、多くの計算時間を要してしまうことになる。例えば、入力信号が１ビット増えると、検証すべきテストパターンの数は２倍となるため、計算時間を据え置きたい場合には、同じ性能の計算機が２倍の数必要になる。そのため、従来の並列化手法は、昨今のLSIの論理シミュレーションにおいては、追跡する信号線とテストデータがどちらも増加しているという問題に効果的に対処できない。
【００１０】
そこで、本願発明は、多くの論理変数や論理演算を含む複雑な論理計算を高速かつ大量に処理可能な論理計算システム等を提案することを目的とする。
【課題を解決するための手段】
【００１１】
請求項１に係る発明は、信号線と素子の関係を表すリストに基づいて実行プログラムを生成する生成部と、前記実行プログラムにより論理計算を実行する情報処理部を備える論理計算システムであって、前記情報処理部は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備えるものであり、前記生成部は、前記リストを記憶する記憶手段と、前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成手段を備えるものである。
【００１２】
請求項２に係る発明は、請求項１記載の論理計算システムであって、前記情報処理部は、分散並列処理が可能なものであり、前記プログラム生成手段は、前記同じ処理を行う並列処理可能な前記タスクのうち、前記データ転送命令が追加されなかったものをまとめて実行単位タスク集合とするものであり、前記情報処理部は、前記実行単位タスク集合に含まれる複数の前記タスクをまとめてタスクスケジューリングし、前記データ転送命令に基づくタスク間通信を行って実行するものである。
【００１３】
請求項３に係る発明は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備える情報処理部に、信号線と素子の関係を表すリストに基づく論理計算を実行させるための実行プログラムを生成する生成装置であって、前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成手段を備えるものである。
【００１４】
請求項４に係る発明は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備える情報処理部に、信号線と素子の関係を表すリストに基づく論理計算を実行させるための実行プログラムを生成する生成方法であって、タスクグラフ生成手段が、前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成ステップと、プログラム生成手段が、前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成ステップを含むものである。
【００１５】
請求項５に係る発明は、コンピュータを、信号線と素子の関係を表すリストにおいて、一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、前記タスクグラフにおいてデータ依存関係のある前記タスクの間に複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加しないことにより、前記データ転送命令を備える情報処理部に前記リストに基づく論理計算を実行させるための実行プログラムを生成するプログラム生成手段として機能させるためのプログラムである。
【００１６】
なお、本願発明における情報処理部は、入力信号のテストパターンを与えて計算させることができる複数の実行部を備え、これらに対して、範囲を分けたテストパターンを割りつけることによる並列分散化も併せて用いるものであってもよい。これにより、本願発明に加えて、従来の並列化手法も適用することが可能となる。
【発明の効果】
【００１７】
本願の各請求項に係る発明（以下、「本願発明」という。）によれば、多くの論理変数や論理演算を含む複雑な論理演算を並列分散プログラムとみなすことにより、並列分散処理技術を応用して高速かつ大量に処理することが可能になる。そのため、複雑な論理演算を、例えばGPGPUを搭載したPCクラスタやCell Broadband Engine（Cell/B.E.）を搭載したゲーム機のクラスタのような安価なハードウェアを用いて、高速かつ大量に処理することが可能になる。
【００１８】
すなわち、本願発明によれば、事前のSIMD（Single Instruction Multiple Data）並列化などによって、静的にネットリストを処理するため、純計算時（実行時インスタンス）では信号線を追跡する必要がなくなる。さらに、静的にネットリストを処理する際、同時に処理することができる演算をまとめておくことによって、SIMD並列化の効率を高めることができる。また、データ転送命令により、タスク間のデータ転送を予め決まったとおりに効率的に行うことができる。現在では、論理シミュレーションや不良診断にも多くの計算時間を要するようになっている。そのため、通常単一の高性能計算機における、いままでの論理計算をより高速化したいという需要も高まっている。本願発明は、これに応えることもできる。
【００１９】
さらに、請求項２に係る発明によれば、SIMD並列化に加えて、タスクスケジューリング手法を含む、ワークフロー型並列分散アプリケーションの並列化に関する既存の効率化手法を適用することにより、論理計算を高速化することが可能になる。タスクスケジューリングの手法は、一般に、互いに依存関係があるようなタスクグラフによって表現できる並列分散アプリケーションにおいて、その計算時間の短縮を目的に利用されるものである。本願発明では、ネットリストなどによって表現されるLSIの組み合わせ回路を、並列分散プログラムとみなす。すなわち、組み合わせ回路内で行われる論理演算のそれぞれをタスクとみなし、論理回路素子間の信号線接続をタスク間の依存関係とみなすことで、タスクスケジューリングの手法を用いて高速化することが可能になる。
【００２０】
テスト計算のような計算負荷の高いアプリケーションは、他にも数多く存在する。タスクスケジューリングやタスクのSIMD並列化、スクラッチパッドメモリの記憶領域管理などのキーテクノロジーの研究開発から得られた知見は、他のアプリケーションにも応用できる可能性が高い。そのため、例えば、本願発明を次のように捉えてもよい。すなわち、ノードとノード間のデータ送受信関係を表すリストに基づいて実行プログラムを生成する生成部と、前記実行プログラムにより情報処理を行う情報処理部を備える情報処理システムであって、前記情報処理部は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備えるものであり、前記生成部は、前記リストを記憶する記憶手段と、前記リストにおける一つ又は複数のノードをタスクに置き換えて、各ノードのデータ送受信関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、前記タスクグラフにおいてデータ送受信関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成手段を備えるものである。
【図面の簡単な説明】
【００２１】
【図１】本願発明の実施例における論理計算システムの構成及び動作を説明するための概念ブロック図である。
【図２】図１の論理計算システム１０１の動作の一例を示すフロー図である。
【図３】テスト対象となる組み合わせ回路の一例を示す図である。
【図４】図３の回路に対する図２のステップＳＴ１の処理後のタスクグラフの一例を示す図である。
【図５】図３の回路に対する図２のステップＳＴ２の処理後のプログラムの構造の一例を示す図である。
【発明を実施するための形態】
【００２２】
以下では、図面を参照して、本願発明の実施例について説明する。なお、本願発明は、この実施例に限定されるものではない。
【実施例】
【００２３】
図１は、本願発明の実施例における論理計算システムの構成及び動作を説明するための概念ブロック図である。論理計算システム１０１（本願請求項の「論理計算システム」の一例）は、実行プログラム１０５を生成する生成装置１０３（本願請求項の「生成部」、「生成装置」の一例）と、実行プログラム１０５を実行して情報処理を行う情報処理部１０７（本願請求項の「情報処理部」の一例）を備える。
【００２４】
情報処理部１０７は、複数のタスクの並列分散処理が可能な複数の実行装置１２３1，…，１２３n（以下、添え字は、複数を示す場合には省略する。）と、タスクスケジューリング等により情報処理部１０７の動作を制御する制御装置１２１を備える。情報処理部１０７では、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令によりタスク間通信を行うものである。情報処理部１０７は、制御装置１２１の制御の下で、実行プログラム１０５の並列分散処理を行う。この並列分散処理では、タスクスケジューリングの手法を用いることで、複数の計算機を活用し、計算の効率化を図ることができる。
【００２５】
生成装置１０３は、ネットリスト（本願請求項の「リスト」の一例）を記憶するネットリスト記憶部１１１（本願請求項の「記憶手段」の一例）と、ネットリストに基づいてタスクグラフを生成するタスクグラフ生成部（本願請求項の「タスクグラフ生成手段」の一例）と、タスクの間にデータ転送命令を追加して実行プログラム１０５を生成するプログラム生成部１１５（本願請求項の「プログラム生成手段」の一例）を備える。生成装置１０３は、事前にネットリストを静的に処理し、SIMD並列化することによって、LSIの大規模化に伴う信号線追跡の繰り返しをなくすことができる。
【００２６】
まず、情報処理部１０７の一例について、具体的に説明する。情報処理部１０７は、一つのプロセッサのようなものでもよく、複数の独立した装置が処理を行うものであってもよい。例えば、昨今のマイクロプロセッサは、回路の複雑化、高密度高集積化、高クロック化のために、消費電力と発熱量の増大が問題視されており、単一のプロセッサコアの性能向上はすでに頭打ちの状況にある。このため、現在では、一つのプロセッサに複数個のコアを搭載し、並列処理を行うことによって全体としての処理能力向上を狙う、マルチコア構成のプロセッサが主流となっている。
【００２７】
特に、ヘテロジニアスマルチコアと呼ばれる新しいプロセッサの構成は、単体で高性能化された制御用のプロセッサコアを１個から数個、SIMD演算などの特定の処理を高性能化した多数の演算用のコアを同時に含むことによって、多様なタイプのプロセッサコアを、スケジューラにより適材適所で有効利用することができる。また、複雑化し過ぎたプロセッサコアの構造を単純化することによって、高クロック化、パイプライン化と、省電力と発熱量の低減の両立を実現している。ヘテロジニアスマルチコアプロセッサは、異なるアーキテクチャのプロセッサコアを組み合わせて一つのプロセッサを構成することにより、アーキテクチャ毎の弱点を補い合って、アプリケーション全体の処理効率を高めることができる。
【００２８】
例えば、GPGPU（General-Purpose computing on Graphics Processing Units（グラフィックス・プロセッシング・ユニットによる汎目的計算））は、本来は画像処理を行うための補助演算装置であるGPUの演算能力を、画像処理以外の汎用な目的に利用できるようにするための技術である。最近のデスクトップアプリケーションでリアルタイムに行われる画像処理は、３次元描画を含むレンダリングアルゴリズムの高度化と、画面の高精細化・高解像度化、高フレームレート化によって、非常に負荷が高くなっている。これらのアプリケーションの要求に応えるために、GPUには高性能なメモリと強力な演算器を集積されている。また、デスクトップアプリケーションで行われる３次元グラフィックスの描画には、行列演算を中心としたSIMD演算や、浮動小数点の演算が非常に多く含まれ、描画性能の向上のために、GPUはSIMD演算と浮動小数点演算の性能が特に高められている。また、GPUベンダーからGPGPUのための技術情報、プログラミング環境、フレームワーク等が公開され、計算負荷の高いさまざまな実用アプリケーションにも応用され始めている。特に、ハイパフォーマンスコンピューティングの分野で注目され、科学技術計算を行うPCクラスタに搭載される機会が多くなっており、最近はスーパーコンピュータにおいても計算ノードの構成に含まれることが多い。
【００２９】
また、例えば、ソニー・コンピュータエンタテインメント社が開発したヘテロジニアスマルチコアプロセッサであるCell/B.E.は，PowerPCアーキテクチャのプロセッサコア（PowerPC Processor Element（PPE））１個と、SIMD演算の性能に優れた演算用のコア（Synergistic Processor Element（SPE））８個を有している。各プロセッサはメインメモリや入出力デバイス、グラフィックデバイスと、Element Interconnect Bus（EIB）と呼ばれる高速なバスで接続されており、各プロセッサはEIBを経由してデータアクセスを行う。これにより、消費電力や発熱量を抑えながらも、従来のプロセッサに比べて高速に加減算や論理演算のような基本演算処理を、複数同時に行うことが可能である。
【００３０】
PPEは、64ビットPowerアーキテクチャの汎用的なプロセッサである。従来のプロセッサと同様にOSの駆動等を行うことが可能だが、特にCell/B.E.においては演算を行うSPEを制御する役割を担っている。後述する実験では、Powerアーキテクチャ上のTime Base Register（TBR）を用いて計算時間の計測を行った。
【００３１】
SPEは、SIMD型アーキテクチャを採用しており、SIMD演算に特化している。SPEは演算装置であるSynergistic Processor Unit（SPU）とMemory Flow Controller（MFC）から構成されている。SPEは、メインメモリに直接アクセスできないが、それぞれのSPEがSPU内に256KiBのLocal Store（LS）と呼ばれる専用のメモリを持つ。そのため、SPEがメインメモリを参照するときは、Direct Memory Access（DMA）を用いてメインメモリとLSとの間でデータ転送を行う。この転送処理は、MFCが行う。（この転送処理が、本願請求項の「データ転送命令」に基づく処理の一例である。）SPUには、プロファイリングのために利用できる、SPU Decrementerというレジスタがある。後述の実験では、このレジスタを用いて計算時間の計測を行った。例えば、OpenCLは、GPGPUやIAサーバを含む異機種並列分散環境で並列分散アプリケーションを実行するためのフレームワークである。OpenCLは、互いに依存関係を持つタスクをタスクスケジューリングする機構を持たない。そのため、単体では、図１の情報処理部１０７を構成することはできない。しかし、図１の実行装置１２３として、OpenCLを含む既存の異機種並列分散環境を用いて実装することは可能である。
【００３２】
Cell/B.E.上のプログラミングで特に有効な技法として、ループ展開、ダブルバッファリングについて説明する。ループ展開とは、繰り返しの処理を展開してループ回数を減らすことで、ループ制御によるオーバーヘッドを減らし、プログラムの実行を高速化する手法である。SPEはSIMD演算に特化しているため、プログラムの制御を得意としていない。ループ展開を行うことで、その制御を減らすことができ、SIMD演算を効率よく行うことができる。そのため、SPE上の計算で特に有効な技法である。ダブルバッファリングとは、データを格納するバッファを２個用意し、バッファを入れ替えながら処理とデータ転送を並列に行うことで、入出力の待ち時間を削減し、実行を高速化する手法である。PPEとSPEとの間のDMA転送は、SPE内のMFCが処理を行うため、データ転送中にSPUは他の処理を行うことが可能である。ダブルバッファリングを用いて、DMA転送と演算を並列に行うことで、SPEの通信待ち時間を削減することができる。
【００３３】
続いて、SIMD並列化について説明する。SIMD演算は、一つの命令でいくつかの数のデータに対して一度に処理を行う演算の一方式である。（SIMD命令でない）汎用な命令は、汎用のソースレジスタと汎用のデスティネーションレジスタにそれぞれ与えられる単一のデータに対して、定められた処理を行った後、デスティネーションレジスタに結果を格納するという処理を行う。それに対して、SIMD命令では、ソースレジスタとデスティネーションレジスタとして専用のSIMDレジスタを持ち、レジスタに格納された連なる複数のベクトルデータに対して、定められた処理を一度に行う。旧来の汎用な命令による演算を、SIMD演算に置き換えることをSIMD並列化という。SIMD演算に適した処理をSIMD並列化することによって、効率化を図ることができる。
【００３４】
SIMD演算の特色は、長いベクトル長を持つSIMDレジスタに格納されたデータを、一命令で一度に、画一的に処理できるということにある。演算するデータの長さがSIMDレジスタ長に満たない場合は、その分だけ演算時間にロスが生じてしまう。このため、演算するデータは、出来るだけまとめてSIMD演算するというのが普通である。特に条件分岐や繰り返しは、その条件の判定に逐次的な処理を含み、SIMD演算の効率を下げてしまうため、これらを取り除く（可能な限り必要のない形にする）ことによって、さらに効率化を図ることができる。
【００３５】
続いて、図２を参照して、図１の論理計算システム１０１の動作の概要について説明する。図１の論理計算システム１０１は、ネットリストで表現される回路を並列分散プログラムと考え、準備段階（コンパイルおよび最適化と同時に行うことが可能）として、事前にSIMD並列化を行う。すなわち、生成装置１０３において、タスクグラフ生成部１１３がタスクグラフ生成処理を静的に行い（図２のステップＳＴ１）、プログラム生成部１１５がSIMD並列化、最適化等を静的に行う（図２のステップＳＴ２）。そのため、静的にネットリストを処理することから、純計算時には信号線の追跡を行う必要がない。さらに、同時に処理できる演算を静的にまとめることにより、SIMD演算の効率を良くすることができる。その後、情報処理部１０７が、並列分散処理（図２のステップＳＴ３）を行う。そのため、タスクスケジューリング手法を含む既存のワークフロー型並列分散プログラムの効率化のさまざまな手法を応用することができる。
【００３６】
続いて、図３及び図４を参照して、図２のステップＳＴ１の処理の一例について具体的に説明する。図３は、テスト対象となる組み合わせ回路例（以下、「テスト対象回路」という。）を示す図である。図１のネットリスト記憶部１１１は、図３の検査対象の論理回路の設計データ（ネットリスト）を記憶している。図３のテスト対象回路は、信号線１、２、３、４、２８、２９及び３０を入力信号とし、素子１０、１５、１６及び１８の出力信号を出力信号とする。素子９は否定であり、信号線１の信号を反転する。素子１１は、素子９の出力信号と信号線２９の論理積を演算する。素子１７は、信号線２と信号線３０の否定論理和を演算する。素子１８は、信号線３の信号と素子１７の出力信号の否定論理和を演算する。素子１２は、素子１７と素子１１の出力信号の論理和を演算する。素子１３は、素子１１の出力信号と信号線４の信号の論理和を演算する。素子１４は、素子１２と素子１３の否定論理積を演算する。素子１６は、素子１４の出力信号と信号線２８の信号の否定論理積を演算する。素子１０は否定であり、素子１６の出力信号を反転する。素子１５は、素子９と素子１６の出力信号の否定論理和を演算する。
【００３７】
図４は、図２のステップＳＴ１の処理において、図３のテスト対象回路から作成されたタスクグラフの一例を示す図である。タスクとは、プログラム内のループやサブルーチン等のまとまった処理単位のことである。プログラムのそれぞれのタスクの間には、データ依存等の実行順序に関する制約がある。プログラムは、この依存関係を用いてタスク間を繋いだグラフとして表すことができる。これをタスクグラフと呼ぶ。プログラムをタスク単位に分割し、ネットワークで接続された計算機資源にタスクを割り当てることで、並列分散計算を行うことができる。
【００３８】
図４では、各素子をタスク（本願請求項の「タスク」の一例）に割り当てている（すなわち、一つの素子をタスクに置き換える。）。そのため、各タスクの依存関係は、図３と同様である。なお、計算に必須ではないが、タスクグラフは実行する際に計算時間が短くなるように最適化することが可能である。例えば、同一の論理演算タスクをまとめることができることができるならば、ひとつにまとめて、より長いベクトル長のSIMD演算タスクにする（すなわち、複数の素子を一つのタスクに置き換える。）。また、可能ならば、クリティカルパス長を短く、並列度を増すようにグラフを変換する。こうして生成されたタスクグラフは、互いに制御依存およびデータ依存関係を含むタスクから構成される並列分散プログラムとみなすことができる。
【００３９】
本願発明は、組み合わせ回路を、その論理演算をタスクとし、論理回路素子間の信号線を依存関係としたタスクグラフとみなす。タスクグラフは、重み付き有向非循環グラフ（Directed Acyclic Graph）G=(V,E)で表わすことができる。Vはノードの集合を表し、SIMD演算器を用いた論理演算を行うタスクに射影される。Eはタスクから別のタスクの有向辺の集合を表し、タスク間のデータ通信に射影される。ただし、有向辺は、循環を作らないものとする。従来は、シミュレーション時にすべての計算機が信号線の追跡を行っていた。それに対し、本願発明では、タスクグラフの生成処理は、ネットリストに変更がない限り最初の実行前に一度だけ行えば良く、テストデータに依存しない。そのため、信号線の追跡は、タスク割り当てを行うより以前の一回のみでよい。事前にネットリストを静的に処理し、タスクグラフを生成することで、シミュレーション時の信号線の追跡処理を削減することができる。また、回路をタスクグラフとして扱うことで、タスクスケジューリングの手法を用いて並列分散計算を効率よく行うことができる。
【００４０】
続いて、図５を参照して、図３のテスト対象回路に対する図２のステップＳＴ２の処理の一例について具体的に説明する。同じ論理演算を行うタスクは、互いに依存関係が無ければ、それらをまとめて処理することで、タスク割り当ての時間を削減できる。また、まとめたタスクは、SIMD演算によって、多くのテストパターンを効率よく計算することができる。
【００４１】
図４では、論理素子による処理の種類は、論理積（AND）が素子１１、否定論理積（NAND）が素子１４及び１６、論理和（OR）が素子１２及び１３、否定論理和（NOR）が素子１５、１７及び１８、否定（NOT）が９及び１０である。このうち、素子１４と１６の間には依存関係がある。素子１７と１５・１８との間にも依存関係がある。素子９と１０の間にも依存関係がある。素子１２及び１３は、同じ処理（論理和）であり、依存関係がない。そのため、これらは、SIMD演算によって処理が可能である。また、素子１５と１８も、同じ処理（否定論理和）であり、依存関係がない。そのため、これらも、SIMD演算によって処理が可能である。図５では、データ転送命令を追加している（データ転送命令１５１、１５３、１５５、１５７及び１５９は、データ依存関係のあるタスクの間に追加されたものであり、本願請求項のタスクグラフにおいてデータ依存関係のあるタスクの間に追加された「データ転送命令」の一例である。）。データ転送命令は、例えば、SPE_shuffle命令である。データ転送命令は、例えば、論理演算をSIMD並列化するため、後続タスクが異なる同種の演算を行うタスクをひとつにまとめたとき、行き先に応じて出力データを分配する。また、出力データのコピーや移動ができる。さらに、データ並列により多くのテストデータを同時に計算することにより、高速化するだけではなく、１回あたりに要する計算時間を短くすることもできる。このデータ転送命令により、タスク間のデータ転送は、タスク間通信を用いて、予め決まったとおりに効率よく行うことができる。図５では、素子１２及び１３に対応するタスクをタスク集合（本願請求項の「実行単位タスク集合」の一例）とし、SIMD演算によってまとめて処理することで、タスク割り当ての時間を削減することができる。素子１５及び１８に対応するタスクについても同様である。
【００４２】
なお、図５では、素子１２及び１３に対応するタスクは、素子１４に対応するタスクの前提として処理するものであり、異なるタイミングで処理すると、クリティカルパスが長くなり、トータルの計算量が増加する可能性が高い。そのため、同時に処理することが望ましいと考えられる。他方、素子１５及び１８に対応するタスクは、別のタイミングで行っても、クリティカルパスの増加は認められない。そのため、図５にあるように、素子１５及び１８に対応するタスクは、同じタイミングで処理する（これらのタスクの間にもデータ転送命令を追加しない）ようにしてもよく、また、異なるタイミングで処理する（一部のタスクの間にはデータ転送命令を追加する）ようにしてもよい。このように、同じ処理を行い、並列に処理可能な場合であっても、全部にデータ転送命令を追加しないようにしてもよく、一部にのみ追加しないようにして残りにはデータ転送命令を追加するようにしてもよい。このようにして、図１のプログラム生成部１１５は、実行プログラム１０５を生成することができる。
【００４３】
本願発明の高速化の手法に加えて、計算機に合わせてSIMD最適化や並列化コンパイラによる最適化等、様々な最適化を行うことができ、タスクの処理を高速化することができる。例えば、SIMD最適化とは、計算時に積極的にSIMD命令を用いる、メモリのアラインメントを調整する等、SIMD演算を効率よく行えるようにすることである。プログラムのソースコード自体に変更を加える手法、また、コンパイラが自動的に行うものがある。並列化コンパイラとは、複数のプロセッサを持つ計算機等、同時に複数の演算処理を行える環境で、並列に処理を行うように、自動的にコードを変換するコンパイラである。並列に処理を行うプログラムでは、複数の処理が同じデータ領域を用いる等、排他制御が必要となる。このようなプログラムのコードを書くことは非常に手間がかかり、並列処理を最適に行うことは難しい。並列化コンパイラを用いて自動的にコードを変換することで、この手間を無くし、最適に並列処理を行うことができる。
【００４４】
続いて、図１の情報処理部１０７の動作について説明する。制御部１２１は、実行装置１２３に、動的スケジューリングを用いてタスクを割り当てる。実行装置１２３は、SIMD演算等を用いてタスクを実行する。そして、求まった出力は、期待する出力と比較される。
【００４５】
実行プログラム１０５は、高速化や大容量のメモリを使いたいなどの目的のために、ループやサブルーチン、ブロックなどのまとまった処理単位（タスク）に分割されている。並列分散環境は、ネットワークで接続された異機種の並列計算機群である。並列分散環境では、計算機資源（ネットワーク、主記憶、プロセッサ）をタスクに割り付けて利用することにより、タスクを実行する。タスク同士は、データ依存や処理依存等の依存関係を持つ。例えば、あるタスクを並列分散環境における適当な計算機資源を用いて実行するためには、実行に必要となるパラメータを先行するタスクで計算し、ネットワークを使って結果を計算機資源に転送する必要がある。並列分散計算を構成するタスクは、これらの依存関係を満たしながら、計算機資源に割り付けられて実行される。計算時間は、この割り付け方により大きく変化する。この計算時間を短くするため、タスクをどの計算機に割り当てるか、スケジューラが適切に選択する必要がある。このようなタスクの割り当てをタスクスケジューリングと呼ぶ。計算時間の短縮化等のため、様々なスケジューリング手法に関する研究が行われている。しかし、一般的な並列分散計算におけるタスクの割け方の最適解を求める問題は典型的なNP困難の計算クラスに属するため、解を求めることは不可能である。このため、タスクスケジューラ（タスクに依存関係を満たしながら，プロセッサや記憶領域等の計算機資源に割り付ける実行時ミドルウェア）は、ヒューリスティックな手法により得た準最適解を利用している。
【００４６】
図１の情報処理部１０７は、動的にスケジューリングを行い、タスクグラフにおけるタスクを実行する。図１の実行装置１２３は、例えば、PC、Cell/B.E.、GPGPU搭載PCを含むローカルエリアネットワークで接続された異機種構成のPCクラスタをハードウェア・プラットホームであってもよい。図１の情報処理部１０７は、ハードウェア・プラットホーム上のSIMD型演算器にタスクを割り付け、論理演算を効率的に行う仕組みを分散ミドルウェアとして実装する。分散ミドルウェアの役割は、後述するタスクスケジューラからの指令に基づき、指定されたタスクを指定されたSIMD型演算器に割り付ける。具体的には、タスクスケジューラから指定されたプログラムを二次記憶装置からロードして実行する。タスクの実行に必要なデータは、他のタスクまたは外部初期入力データとして与えられる。タスクスケジューラは、演算器間の通信時間や演算器における計算時間も考慮しながら、全体の計算時間が小さくなるように、タスクをヘテロジニアスマルチコアプロセッサやGPGPUにおけるSIMD型演算器に割り付ける。この種のタスクスケジューリングの最適化問題は一般に解くことができない（NP困難問題）ため、クリティカルパス上のタスクを最優先する方法をベースにするヒューリスティックな方法を用いる。
【００４７】
タスクスケジューラは、制御依存およびデータ依存関係が満足され実行可能となったタスクのうち、出口ノードまでの距離が最短となるタスクを高い優先順位で実行するクリティカルパス法を基本とする動的タスクスケジューリング手法でスケジューリングを行い、ネットリストを並列分散プログラムとしてハードウェア・プラットホーム上で並列分散実行する。
【００４８】
本願発明では、タスク割り当てを動的にスケジューリングすることで、論理シミュレーションの計算時間を短縮する。動的スケジューリングとは、実行時に行うタスク割り当ての際に，手法ごとに決めたポリシーに従い、特定の目的関数（例えば計算時間や計算コスト）を最小化するようにタスクを割り当てる計算機を決定するスケジューリング手法である。動的スケジューリングでは、タスクを割り当てる計算機を決定する際に計算時間が必要になるが、１スケジューリングタイムインスタンスあたりに必要な時間は、経験的に１ミリ秒程度であり、SIMD演算とのオーバーラップも可能である。動的スケジューリングには、例えば、クリティカルパス(CP)法がある。クリティカルパス(CP)法とは、クリティカルパス上のタスクを優先的に割り当てるスケジューリング手法である。このスケジューリング手法では、タスクを割り当て時に、その時点でのクリティカルパス長を計算し、タスク割り当てを動的に行う。
【００４９】
続いて、本願発明の評価のため行った、２つの実験について説明する。まず、従来の手法による論理シミュレーションに要する計算時間を計測した（以下、「従来手法の評価実験」という。）。続いて、本願発明による論理演算の計算時間を計測した（以下、「本願発明の評価実験」という。）。前者は、信号線追跡の時間に関する評価を目的とするものである。後者は、SIMD演算の高速化の評価を目的とするものである。
【００５０】
従来手法の評価実験では、従来の手法における計算に必要な時間を計測した。従来手法は、計算を行う際に毎回信号線の追跡を行っており、何度も同じ処理を繰り返すという無駄がある。この実験では、従来手法の処理全体に要する時間と論理演算に要する時間を計測し、信号線追跡が処理時間に占める割合を調べた。
【００５１】
この実験では、ネットリストを読み込み、表として管理し、この表を参照することで信号線の追跡を行った。プログラム実行後、gprofを用いてプロファイリングを行い、処理全体に要した時間、論理演算部分に要した時間をそれぞれ計測した。この実験の結果を表１に示す。従来の手法においては、論理演算は実験全体のうち約35％を占めていることが確認できた。論理演算部分以外に要した時間1.28秒のうち、I/O関係の処理（ネットリストやテストパターンの読み込み、結果の出力）を除いた時間は、主に信号線の追跡に要した時間である。この時間は、提案手法を用いることで削減できる。また、本実験で論理演算に要した時間0.69秒について、本願発明ではSIMD並列化して論理演算を行うため、この時間を短縮することができる。よって、本願発明により、例えば論理演算をCell/B.E.上のSPEを用いてSIMD並列化した場合、同じ計算をPPE上で行った場合に比べて２倍から３倍高速化可能である。さらに、論理演算がシミュレーション全体のおよそ４割を占めるものの、本願発明では信号線追跡にも多くの時間が割かれており、信号線追跡を削減する提案手法によって高速化することができる。
【００５２】
【表１】
【００５３】
本願発明の評価実験では、全体の処理のうち、論理演算の部分をSIMD並列化し、さらにSIMD演算に特化したプロセッサを用いて、SIMD演算を高速に行うことで全体の計算時間を短縮した。この実験では、SIMD演算に特化したプロセッサであるSPEを搭載したCell/B.E.を用いて、本願発明の計算時間を計測した。実験では、PPEとSPEのそれぞれでSIMD命令セットを用いたAND演算を行うため、32MiBのテスト用ベクトルデータ２つを用意する。この２つのテスト用ベクトルデータのANDをとる演算を行い、その計算時間を計測した。SPEの計算では、ダブルバッファリングを用いたため、処理全体の計算時間と計算部分のみの両者を計測し、比較することで、ダブルバッファリングの効果を調べた。同様に、ループ展開に関して、展開を行う場合と行わない場合とを比較し、ループ展開による計算時間の減少を調べた。それぞれ計算時間の計測には、PPEではTBR，SPEではSPU Decrementerをそれぞれ用いた。
【００５４】
この実験の結果を表２に示す。SPEの処理全体の時間と計算部のみの時間とを比較すると、その差は1ミリ秒以下であり、ダブルバッファリングを用いることで、PPEとSPEとの間のDMA転送に要する時間は、計算時間でオーバーラップが可能であることが確認できた。また、PPEとSPEの計算の速さを比較すると、ループ展開を行う場合ではSPEはPPEの約3.1倍、ループ展開を行わない場合は約2.6倍の速さとなっている。このことから、SPEのようなSIMD演算を高速に行うことができるプロセッサを用いることで、論理演算を高速に行え、本願発明のSIMD並列化が有効であることが確認できた。SIMD演算では、ループ展開によりSIMD演算器を有効に利用すると効果的であるから、本実験で実際にループ展開を行う場合と行わない場合を計測し、比較したところ、PPE，SPEはどちらも計算時間が短くなり、ループ展開がSIMD演算の高速化に効果的であることが確認できた。
【００５５】
【表２】
【産業上の利用可能性】
【００５６】
本願発明は、LSIの論理シミュレーション、不良診断、テスト計算、エキスパートシステムをはじめとする論理演算を高速かつ大量に行う論理計算に利用可能である。
【符号の説明】
【００５７】
１０１ 論理計算システム、１０３ 生成装置、１０５ 実行プログラム、１０７ 情報処理部、１１１ ネットリスト記憶部、１１３ タスクグラフ生成部、１１５ プログラム生成部、１２１ 制御装置、１２３1，…，１２３n 実行装置、１５１，１５３，１５５，１５７，１５９ データ転送命令
【特許請求の範囲】
【請求項１】
信号線と素子の関係を表すリストに基づいて実行プログラムを生成する生成部と、前記実行プログラムにより論理計算を実行する情報処理部を備える論理計算システムであって、
前記情報処理部は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備えるものであり、
前記生成部は、
前記リストを記憶する記憶手段と、
前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、
前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成手段を備える、論理計算システム。
【請求項２】
前記情報処理部は、分散並列処理が可能なものであり、
前記プログラム生成手段は、前記同じ処理を行う並列処理可能な前記タスクのうち、前記データ転送命令が追加されなかったものをまとめて実行単位タスク集合とするものであり、
前記情報処理部は、前記実行単位タスク集合に含まれる複数の前記タスクをまとめてタスクスケジューリングし、前記データ転送命令に基づくタスク間通信を行って実行するものである、請求項１記載の論理計算システム。
【請求項３】
複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備える情報処理部に、信号線と素子の関係を表すリストに基づく論理計算を実行させるための実行プログラムを生成する生成装置であって、
前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、
前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成手段を備える生成装置。
【請求項４】
複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備える情報処理部に、信号線と素子の関係を表すリストに基づく論理計算を実行させるための実行プログラムを生成する生成方法であって、
タスクグラフ生成手段が、前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成ステップと、
プログラム生成手段が、前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成ステップを含む生成方法。
【請求項５】
コンピュータを、
信号線と素子の関係を表すリストにおいて、一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、
前記タスクグラフにおいてデータ依存関係のある前記タスクの間に複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加しないことにより、前記データ転送命令を備える情報処理部に前記リストに基づく論理計算を実行させるための実行プログラムを生成するプログラム生成手段として機能させるためのプログラム。
【請求項１】
信号線と素子の関係を表すリストに基づいて実行プログラムを生成する生成部と、前記実行プログラムにより論理計算を実行する情報処理部を備える論理計算システムであって、
前記情報処理部は、複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備えるものであり、
前記生成部は、
前記リストを記憶する記憶手段と、
前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、
前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成手段を備える、論理計算システム。
【請求項２】
前記情報処理部は、分散並列処理が可能なものであり、
前記プログラム生成手段は、前記同じ処理を行う並列処理可能な前記タスクのうち、前記データ転送命令が追加されなかったものをまとめて実行単位タスク集合とするものであり、
前記情報処理部は、前記実行単位タスク集合に含まれる複数の前記タスクをまとめてタスクスケジューリングし、前記データ転送命令に基づくタスク間通信を行って実行するものである、請求項１記載の論理計算システム。
【請求項３】
複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備える情報処理部に、信号線と素子の関係を表すリストに基づく論理計算を実行させるための実行プログラムを生成する生成装置であって、
前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、
前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成手段を備える生成装置。
【請求項４】
複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を備える情報処理部に、信号線と素子の関係を表すリストに基づく論理計算を実行させるための実行プログラムを生成する生成方法であって、
タスクグラフ生成手段が、前記リストにおける一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成ステップと、
プログラム生成手段が、前記タスクグラフにおいてデータ依存関係のある前記タスクの間に前記データ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加せずに前記実行プログラムを生成するプログラム生成ステップを含む生成方法。
【請求項５】
コンピュータを、
信号線と素子の関係を表すリストにおいて、一つ又は複数の素子をタスクに置き換えて、各素子のデータの依存関係から前記タスクのタスクグラフを生成するタスクグラフ生成手段と、
前記タスクグラフにおいてデータ依存関係のある前記タスクの間に複数のデータのそれぞれの移動後の位置を定義するデータ転送命令を追加し、同じ処理を行う並列処理可能な前記タスクの間には、一部又は全部に前記データ転送命令を追加しないことにより、前記データ転送命令を備える情報処理部に前記リストに基づく論理計算を実行させるための実行プログラムを生成するプログラム生成手段として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１２−１４１８５２（Ｐ２０１２−１４１８５２Ａ）
【公開日】平成２４年７月２６日（２０１２．７．２６）
【国際特許分類】
【出願番号】特願２０１１−２４３（Ｐ２０１１−２４３）
【出願日】平成２３年１月４日（２０１１．１．４）
【出願人】（５０４１７４１３５）国立大学法人九州工業大学 (489)
【Ｆターム（参考）】
【公開日】平成２４年７月２６日（２０１２．７．２６）
【国際特許分類】
【出願日】平成２３年１月４日（２０１１．１．４）
【出願人】（５０４１７４１３５）国立大学法人九州工業大学 (489)
【Ｆターム（参考）】
[ Back to top ]