JPH05216848A - 方程式セットを解くための多重プロセッサコンピュータ - Google Patents
方程式セットを解くための多重プロセッサコンピュータInfo
- Publication number
- JPH05216848A JPH05216848A JP4270671A JP27067192A JPH05216848A JP H05216848 A JPH05216848 A JP H05216848A JP 4270671 A JP4270671 A JP 4270671A JP 27067192 A JP27067192 A JP 27067192A JP H05216848 A JPH05216848 A JP H05216848A
- Authority
- JP
- Japan
- Prior art keywords
- task
- tasks
- matrix
- processor
- processing elements
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/11—Complex mathematical operations for solving equations, e.g. nonlinear equations, general mathematical optimization problems
- G06F17/12—Simultaneous equations, e.g. systems of linear equations
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/16—Matrix or vector computation, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/36—Circuit design at the analogue level
- G06F30/367—Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Analysis (AREA)
- Pure & Applied Mathematics (AREA)
- Computational Mathematics (AREA)
- Mathematical Optimization (AREA)
- Computer Hardware Design (AREA)
- Data Mining & Analysis (AREA)
- General Engineering & Computer Science (AREA)
- Algebra (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- Computing Systems (AREA)
- Geometry (AREA)
- Evolutionary Computation (AREA)
- Microelectronics & Electronic Packaging (AREA)
- Operations Research (AREA)
- Multi Processors (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Complex Calculations (AREA)
- Computer And Data Communications (AREA)
Abstract
(57)【要約】
【目的】 マトリックスで表わされる方程式のセットを
解く多重インストラクションのストリーム多重データス
トリームコンピュータシステムと方法を提供する。 【構成】 マトリックスとして表わされる方程式セット
を解く新規の方法とその方法でつくられた並列性を利用
することのできる新規なマルチプロセッサコンピュータ
構成とが組合される。マトリックスを解くタスクを準個
別化タスクに区分することで準個別化タスクの数だけ並
列に実行され得る。マルチプロセッサ構成は、特殊目的
ネットワークプロセッサで制御されている相互プロセッ
サ通信ネットワークを介して相互結合された多数のフォ
ンノイマンコンピュータからなる。ネットワークプロセ
ッサは、各フォンノイマンコンピュータが準個別化タス
クを効率的に実行するようにし、そして夫々のコンピュ
ータ間で通信されるべき情報をルーティングする。
解く多重インストラクションのストリーム多重データス
トリームコンピュータシステムと方法を提供する。 【構成】 マトリックスとして表わされる方程式セット
を解く新規の方法とその方法でつくられた並列性を利用
することのできる新規なマルチプロセッサコンピュータ
構成とが組合される。マトリックスを解くタスクを準個
別化タスクに区分することで準個別化タスクの数だけ並
列に実行され得る。マルチプロセッサ構成は、特殊目的
ネットワークプロセッサで制御されている相互プロセッ
サ通信ネットワークを介して相互結合された多数のフォ
ンノイマンコンピュータからなる。ネットワークプロセ
ッサは、各フォンノイマンコンピュータが準個別化タス
クを効率的に実行するようにし、そして夫々のコンピュ
ータ間で通信されるべき情報をルーティングする。
Description
【産業上の利用分野】本発明は、一般的には、コンピュ
ータシステム、より詳細には、マトリックス形式にて表
わすことができるセットの方程式を解くためのコンピュ
ータによる方法及びシステムに関する。
ータシステム、より詳細には、マトリックス形式にて表
わすことができるセットの方程式を解くためのコンピュ
ータによる方法及びシステムに関する。
【０００２】
【従来の技術】セットの方程式を解くことは、特に、メ
カニクス、経済学、流体力学及び電気回路シミュレーシ
ョンの分野において有効である。例えば、回路シミュレ
ーションは、典型的には、電気回路の挙動をモデル化す
るセットの方程式を組み立て、次に、このセットの方程
式を解くことによって回路内の未知の電圧及び電流の値
について知ることからなる。シミュレートされる回路を
記述する方程式は、通常、非線型であり、このために、
反復的技法、例えば、典型的には、ニュートン・ラフソ
ン（Newton Raphson）法がこのようなセットの方程式を
解くために使用される。ニュートン・ラフソン法を含む
様々な反復的技法が当業者においては周知である。
カニクス、経済学、流体力学及び電気回路シミュレーシ
ョンの分野において有効である。例えば、回路シミュレ
ーションは、典型的には、電気回路の挙動をモデル化す
るセットの方程式を組み立て、次に、このセットの方程
式を解くことによって回路内の未知の電圧及び電流の値
について知ることからなる。シミュレートされる回路を
記述する方程式は、通常、非線型であり、このために、
反復的技法、例えば、典型的には、ニュートン・ラフソ
ン（Newton Raphson）法がこのようなセットの方程式を
解くために使用される。ニュートン・ラフソン法を含む
様々な反復的技法が当業者においては周知である。
【０００３】ニュートン・ラフソン法の一部はセットの
線型方程式を解くことを含む。経験的に、セットの方程
式を解くための時間が大きな回路をシミュレートするた
めに必要される時間の大部分を占める。従来の回路シミ
ュレーション技法を使用する場合、最も強力なスーパー
コンピュータでもシミュレーションを完結するために幾
時間も必要であり、従って、大きな集積回路のシミュレ
ーションは、現実的に不可能である。
線型方程式を解くことを含む。経験的に、セットの方程
式を解くための時間が大きな回路をシミュレートするた
めに必要される時間の大部分を占める。従来の回路シミ
ュレーション技法を使用する場合、最も強力なスーパー
コンピュータでもシミュレーションを完結するために幾
時間も必要であり、従って、大きな集積回路のシミュレ
ーションは、現実的に不可能である。
【０００４】セットの線型方程式を解くために多くの方
法を使用することができるが、当業者に周知の下限上限
分解（Lower Upper Decomposition 、ＬＵＤ）という方
法が一般的にはこの精度及び安定性のために好まれる。
法を使用することができるが、当業者に周知の下限上限
分解（Lower Upper Decomposition 、ＬＵＤ）という方
法が一般的にはこの精度及び安定性のために好まれる。
【０００５】ＬＵＤを並列化するための幾つかの努力が
なされている。Ｊ．ヒュング（Huang ）及びＯ．ウィン
グ（Wing）によって回路及びシステムに関する米国電気
電子学会議事録（I.E.E.E.Trans.on Circuits and Syst
ems ）、Ｖｏｌ．ＣＡＳ−２６、ページ７２６−７３２
（１９７９年９月）に掲載の論文『希薄マトリックスの
最適並列三角測量（Optimal Parallel Traiangulation
of Sparse Matrix ）；Ｎ．カルマルカ（Karmarkar ）
によって離散数学に関するシャム会議（Siam Conferenc
e on Discrete Mathematics ）、アトランタ（１９９０
年６月）において発表の論文『希薄マトリックス計算の
ための新たなパラレルコンピュータ（ANew Parallel Co
mputer for Sparse Matrix Computation ）』；及び
Ｏ．ウィング（Wing）及びＪ．ヒュング（Huang ）によ
ってコンピュータに関する米国電気電子学会議事録『I.
E.E.E. Trans. on Computers）、Ｖｏｌ．Ｃ−２９、ペ
ージ６３２−６３８（１９８０年７月）に掲載の論文
『線型方程式の並列解決の計算モデル（A Computation
Model of Parallel Solution of Linear Equations）に
おいてこれらが見られる。これら方法は、ＬＵＤにおい
て要求される各ステップをリコンパイルし、タスクグラ
フを構築することに集中するが、このタスクグラフが次
にマルチプロセッサ上でランするようにスケジュールさ
れる。これら手順はスケジュールされるべき多数のタス
クを与え、現実的な回路に対してはあまりにも多くのメ
モリを必要とする。
なされている。Ｊ．ヒュング（Huang ）及びＯ．ウィン
グ（Wing）によって回路及びシステムに関する米国電気
電子学会議事録（I.E.E.E.Trans.on Circuits and Syst
ems ）、Ｖｏｌ．ＣＡＳ−２６、ページ７２６−７３２
（１９７９年９月）に掲載の論文『希薄マトリックスの
最適並列三角測量（Optimal Parallel Traiangulation
of Sparse Matrix ）；Ｎ．カルマルカ（Karmarkar ）
によって離散数学に関するシャム会議（Siam Conferenc
e on Discrete Mathematics ）、アトランタ（１９９０
年６月）において発表の論文『希薄マトリックス計算の
ための新たなパラレルコンピュータ（ANew Parallel Co
mputer for Sparse Matrix Computation ）』；及び
Ｏ．ウィング（Wing）及びＪ．ヒュング（Huang ）によ
ってコンピュータに関する米国電気電子学会議事録『I.
E.E.E. Trans. on Computers）、Ｖｏｌ．Ｃ−２９、ペ
ージ６３２−６３８（１９８０年７月）に掲載の論文
『線型方程式の並列解決の計算モデル（A Computation
Model of Parallel Solution of Linear Equations）に
おいてこれらが見られる。これら方法は、ＬＵＤにおい
て要求される各ステップをリコンパイルし、タスクグラ
フを構築することに集中するが、このタスクグラフが次
にマルチプロセッサ上でランするようにスケジュールさ
れる。これら手順はスケジュールされるべき多数のタス
クを与え、現実的な回路に対してはあまりにも多くのメ
モリを必要とする。
【０００６】Ｐ．サダヤパン（Sadayappan）及びＶ．ビ
スバナサン（Visvanathan ）によってコンピュータに関
する米国電気電子学会議事録（I.E.E.E, Transactions
on Computers）、Ｖｏｌ．Ｃ−３７、ページ１６３４−
１６４２（１９８８年１２月）に発表の論文『共有メモ
リ多重プロセッサ上での回路シミュレーション（Ciruit
Simulation on Shared Memory Multiprocessor ）』に
おいて提案されるもう一つのアプローチは部分的コンパ
イルアプローチを使用するが、これは、希薄マトリック
スのＬＵＤから高い程度の平行動作を抽出するのに非常
に有効的である一方、スケジュールされるべきタスクグ
ラフの複雑さが最小限にされることを示す。このアプロ
ーチは一般ＬＵＤアプローチとコンパイルアプローチと
の間の良好な妥協である。
スバナサン（Visvanathan ）によってコンピュータに関
する米国電気電子学会議事録（I.E.E.E, Transactions
on Computers）、Ｖｏｌ．Ｃ−３７、ページ１６３４−
１６４２（１９８８年１２月）に発表の論文『共有メモ
リ多重プロセッサ上での回路シミュレーション（Ciruit
Simulation on Shared Memory Multiprocessor ）』に
おいて提案されるもう一つのアプローチは部分的コンパ
イルアプローチを使用するが、これは、希薄マトリック
スのＬＵＤから高い程度の平行動作を抽出するのに非常
に有効的である一方、スケジュールされるべきタスクグ
ラフの複雑さが最小限にされることを示す。このアプロ
ーチは一般ＬＵＤアプローチとコンパイルアプローチと
の間の良好な妥協である。
【０００７】サダヤパン・ビスバナサンアプローチは最
初は共有メモリ多重プロセッサのために開発されたが、
後に、Ｊ．トロッター（Trotter ）及びＰ．アグラワル
（Agrawal ）によって米国電気電子学会議事録ＩＣＣＡ
Ｄ、サンタクララ、ページ４３８−４４１（１９９０年
１１月）に掲載の論文『分散メモリ多重プロセッサシス
テム上での回路シミュレーション法（Circuit Simulati
on Methods on a Distributed Memory Multiprocessor
System）』において分散メモリ多重プロセッサ上での使
用に対して拡張されている。この論文がここでは参照の
ために本明細書に編入されている。
初は共有メモリ多重プロセッサのために開発されたが、
後に、Ｊ．トロッター（Trotter ）及びＰ．アグラワル
（Agrawal ）によって米国電気電子学会議事録ＩＣＣＡ
Ｄ、サンタクララ、ページ４３８−４４１（１９９０年
１１月）に掲載の論文『分散メモリ多重プロセッサシス
テム上での回路シミュレーション法（Circuit Simulati
on Methods on a Distributed Memory Multiprocessor
System）』において分散メモリ多重プロセッサ上での使
用に対して拡張されている。この論文がここでは参照の
ために本明細書に編入されている。
【０００８】Ｔ．ナカタ（Nakata）、Ｎ．タナベ（Tana
be）、Ｈ．オノズカ（Onozuka ）、Ｔ．クロベ（Kurob
e）及びＮ．コイケ（Koike ）らによって米国電気電子
学会議事録ＩＣＣＡＤ（I.E.E.E. ICCAD）、ページ３６
４−３６７（１９８７年）に発表の論文『モジュラ回路
シミュレーションのための多重プロセッサシステム（AM
ultiprocessor System for Modular Circuit Simulatio
n）』によって提案されるもう一つのアプローチは分散
メモリ多重プロセッサ上へのコンパイルなしにＬＵＤを
使用する。ナカタらのシステムにおいては、各プロセッ
サは共有バスを使用して他のプロセッサのメモリにアク
セスする。
be）、Ｈ．オノズカ（Onozuka ）、Ｔ．クロベ（Kurob
e）及びＮ．コイケ（Koike ）らによって米国電気電子
学会議事録ＩＣＣＡＤ（I.E.E.E. ICCAD）、ページ３６
４−３６７（１９８７年）に発表の論文『モジュラ回路
シミュレーションのための多重プロセッサシステム（AM
ultiprocessor System for Modular Circuit Simulatio
n）』によって提案されるもう一つのアプローチは分散
メモリ多重プロセッサ上へのコンパイルなしにＬＵＤを
使用する。ナカタらのシステムにおいては、各プロセッ
サは共有バスを使用して他のプロセッサのメモリにアク
セスする。
【０００９】
【発明が解決しようとする課題】本発明は先行技術とは
異なるアプローチを使用してマトリックス形式にて表わ
されるセットの方程式を解くためのメカニズムを提供す
る。セットの方程式は、本発明によって以前のメカニズ
ムよりも素早く解くことができる。
異なるアプローチを使用してマトリックス形式にて表わ
されるセットの方程式を解くためのメカニズムを提供す
る。セットの方程式は、本発明によって以前のメカニズ
ムよりも素早く解くことができる。
【００１０】
【課題を解決するための手段】本発明の一つの実施例に
おいては、通信網を介して相互接続される複数の処理要
素が含まれる。プロセッサ間の通信のスケジューリング
は専用の網プロセッサによって指令される。
おいては、通信網を介して相互接続される複数の処理要
素が含まれる。プロセッサ間の通信のスケジューリング
は専用の網プロセッサによって指令される。
【００１１】
１．イントロダクション 本発明はモデリング或はシミュケーションのためのコン
ピュータシステム及び方法を提供する。以降に説明され
る本発明の実施例は一例としての問題を解決するという
背景において最も簡単に理解できる。この一例としての
実施例は多様な分野から発生する問題を解決することが
できるが、一例としての問題は電気工学分野における問
題である。次のセクションにおいては、一例としての問
題が示される。次に本発明の実施例が示され、最後に、
この一例としての問題がこの実施例に従っていかに解か
れるかが示される。
ピュータシステム及び方法を提供する。以降に説明され
る本発明の実施例は一例としての問題を解決するという
背景において最も簡単に理解できる。この一例としての
実施例は多様な分野から発生する問題を解決することが
できるが、一例としての問題は電気工学分野における問
題である。次のセクションにおいては、一例としての問
題が示される。次に本発明の実施例が示され、最後に、
この一例としての問題がこの実施例に従っていかに解か
れるかが示される。
【００１２】２．一例としての問題 ２．１ 電気回路の設計 電気回路、例えば、図１の略図によって示されるような
回路は、典型的には、特定の機能を遂行するように設計
される。電気回路の設計に関しては多くのことが知られ
ているが、これは、実質的に経験的であり、製造された
回路は、しばしば、設計者によって意図されたような性
能を示さない。製造及びテストのコストが低い場合は、
望ましい性能が示されるまで、回路を設計、製造、テス
トし、また再設計することもできる。但し、製造及び／
或はテストのコストが高くなると、製造する前に回路設
計が意図された性能を示すかを検証することが有利にな
る。
回路は、典型的には、特定の機能を遂行するように設計
される。電気回路の設計に関しては多くのことが知られ
ているが、これは、実質的に経験的であり、製造された
回路は、しばしば、設計者によって意図されたような性
能を示さない。製造及びテストのコストが低い場合は、
望ましい性能が示されるまで、回路を設計、製造、テス
トし、また再設計することもできる。但し、製造及び／
或はテストのコストが高くなると、製造する前に回路設
計が意図された性能を示すかを検証することが有利にな
る。
【００１３】設計の電気特性を予測する一つの手段は”
回路シミュレーション（circuit simulation）”として
知られる技術を通じてである。回路シミュレーションは
回路要素の数学的モデル及び回路のトポロジーに基づい
て回路の数学的モデルを構築することから成る。回路の
モデルをいったん構築できれば、周知の技術を通じてこ
の振る舞いを正確に予測することができる。
回路シミュレーション（circuit simulation）”として
知られる技術を通じてである。回路シミュレーションは
回路要素の数学的モデル及び回路のトポロジーに基づい
て回路の数学的モデルを構築することから成る。回路の
モデルをいったん構築できれば、周知の技術を通じてこ
の振る舞いを正確に予測することができる。
【００１４】２．２ 一例としての電気回路 当業者においては周知の通り、図１の略図によって表わ
される電気回路は一つの電圧源及び５つの抵抗を含む。
説明の目的上、この電圧源は１０ボルトであり、回路の
設計者は製造された回路のＶ2 における電圧が２．０ボ
ルト、そしてＶ3 における電圧が０．１７５ボルトを示
すことを意図するものと想定する。この設計が要求され
るような性能を示すことを確保するためには、これをシ
ミュレートすることが必要である。
される電気回路は一つの電圧源及び５つの抵抗を含む。
説明の目的上、この電圧源は１０ボルトであり、回路の
設計者は製造された回路のＶ2 における電圧が２．０ボ
ルト、そしてＶ3 における電圧が０．１７５ボルトを示
すことを意図するものと想定する。この設計が要求され
るような性能を示すことを確保するためには、これをシ
ミュレートすることが必要である。
【００１５】２．３ 一例としての電気回路のモデリン
グ 当業者においては周知の通り、図１に表わされる電気回
路は、キルヒホッフの電流則及びキルヒホッフの電圧
則、並びに修正接続点解析（Modified Nodal Analysis
）に従って、図２に示されるようなセットの５つの方
程式に従ってモデル化することができることが分かる。
一般に、回路シミュレーションは回路をモデル化するこ
れらの方程式が集中的にシミュレートされることを要求
する。これらが、特に、コンピュータによってより簡単
にシミュレートできるようにするために、これらの方程
式は典型的にはマトリックス形式にて表わされる。当業
者においては周知のとおり、図２のセットの方程式は図
３に示されるようなマトリックス形式にて表わすことが
できる。
グ 当業者においては周知の通り、図１に表わされる電気回
路は、キルヒホッフの電流則及びキルヒホッフの電圧
則、並びに修正接続点解析（Modified Nodal Analysis
）に従って、図２に示されるようなセットの５つの方
程式に従ってモデル化することができることが分かる。
一般に、回路シミュレーションは回路をモデル化するこ
れらの方程式が集中的にシミュレートされることを要求
する。これらが、特に、コンピュータによってより簡単
にシミュレートできるようにするために、これらの方程
式は典型的にはマトリックス形式にて表わされる。当業
者においては周知のとおり、図２のセットの方程式は図
３に示されるようなマトリックス形式にて表わすことが
できる。
【００１６】２．４ 回路のシミュレーション 当業者において周知のように、図３のマトリックスは幾
つかの周知の技術を使用して解くことができる。Ｊ．バ
ルチ（Vlach ）及びＫ．シングハル（Singhal）らによ
る文献『回路解析及び設計のためのコンピュータによる
方法（ComputerMethods for Circuit Analysis and Des
ign）』、ヴァン・ノストランド・レインホールド（Van
Nostrand Reinhold ）、１９８３年、及びＰ．Ｃ．シ
ールド（Shields ）による初級線型代数（Elementary L
inear Algebra ）、第三版、１９８０年が本明細書の参
考のためにここに編入される。回路シミュレーションに
おいては、高度の精度が要求され、従って、厳密な解を
与える技法が好ましい。このような技法の一つは、下限
上限分解（Lower Upper Decomposition 、ＬＵＤ）に続
く順方向削除（Forward Elimination 、ＦＥ）及び逆方
向置換（Back Substitution 、ＢＳ）である。
つかの周知の技術を使用して解くことができる。Ｊ．バ
ルチ（Vlach ）及びＫ．シングハル（Singhal）らによ
る文献『回路解析及び設計のためのコンピュータによる
方法（ComputerMethods for Circuit Analysis and Des
ign）』、ヴァン・ノストランド・レインホールド（Van
Nostrand Reinhold ）、１９８３年、及びＰ．Ｃ．シ
ールド（Shields ）による初級線型代数（Elementary L
inear Algebra ）、第三版、１９８０年が本明細書の参
考のためにここに編入される。回路シミュレーションに
おいては、高度の精度が要求され、従って、厳密な解を
与える技法が好ましい。このような技法の一つは、下限
上限分解（Lower Upper Decomposition 、ＬＵＤ）に続
く順方向削除（Forward Elimination 、ＦＥ）及び逆方
向置換（Back Substitution 、ＢＳ）である。
【００１７】当業者においては周知のように、ＬＵＤは
正規化（normalization ）及び更新（updating）の二つ
の動作を含む。要約すると、正規化はロウの各アフタ対
角線要素（after-diagonal element）をその対角線要素
で割る操作を含み、更新は最も最近正規化されたロウの
対角線要素以下のロウを操作する動作を含む。この手順
は左側の最も上の対角線要素から開始され、対角線を下
の方向に進む。ＬＵＤは全ての対角線要素が正規化され
た時点で完了する。ある技法によると、ＬＵＤが完結さ
れた後に、Ｖ2 及びＶ3 に対する解を得るためにＦＥ及
びＢＳが遂行される。
正規化（normalization ）及び更新（updating）の二つ
の動作を含む。要約すると、正規化はロウの各アフタ対
角線要素（after-diagonal element）をその対角線要素
で割る操作を含み、更新は最も最近正規化されたロウの
対角線要素以下のロウを操作する動作を含む。この手順
は左側の最も上の対角線要素から開始され、対角線を下
の方向に進む。ＬＵＤは全ての対角線要素が正規化され
た時点で完了する。ある技法によると、ＬＵＤが完結さ
れた後に、Ｖ2 及びＶ3 に対する解を得るためにＦＥ及
びＢＳが遂行される。
【００１８】経験上から、幾つかのマトリックスは高い
パーセントのゼロ要素を含み、従って、”希薄（spars
e）”であると呼ばれる。これとは対象的に、低いパー
セントのゼロ要素を持つマトリックスは”密（dense
）”であると呼ばれる。希薄マトリックスのＬＵＤは
密マトリックスのＬＵＤと同一であるが、希薄マトリッ
クス内の多数のゼロ要素の存在はＬＵＤを遂行するため
に実行される多くの動作が不必要であることを意味す
る。
パーセントのゼロ要素を含み、従って、”希薄（spars
e）”であると呼ばれる。これとは対象的に、低いパー
セントのゼロ要素を持つマトリックスは”密（dense
）”であると呼ばれる。希薄マトリックスのＬＵＤは
密マトリックスのＬＵＤと同一であるが、希薄マトリッ
クス内の多数のゼロ要素の存在はＬＵＤを遂行するため
に実行される多くの動作が不必要であることを意味す
る。
【００１９】好ましい実施例においては、順方向削除が
ＬＵＤと同時に当業者に周知な方法にて遂行される。要
約すると、係数を表わすマトリックスが図３の方程式の
右側を表わすベクトル分だけ増大される。図４は図３の
マトリックスに対応する増大されたマトリックスを表わ
す。
ＬＵＤと同時に当業者に周知な方法にて遂行される。要
約すると、係数を表わすマトリックスが図３の方程式の
右側を表わすベクトル分だけ増大される。図４は図３の
マトリックスに対応する増大されたマトリックスを表わ
す。
【００２０】図５は図４のマトリックス表現（represen
tation）を示すが、ここで、”Ｘ”はマトリックス内の
非ゼロ値の位置を表わす。当業者において周知の通り、
ＬＵＤの際に、追加の非ゼロ要素がマトリックス内の決
定可能な位置内に導入される。これらは図５内のＦによ
って表わされる。
tation）を示すが、ここで、”Ｘ”はマトリックス内の
非ゼロ値の位置を表わす。当業者において周知の通り、
ＬＵＤの際に、追加の非ゼロ要素がマトリックス内の決
定可能な位置内に導入される。これらは図５内のＦによ
って表わされる。
【００２１】２．５ マトリックスを解くためのタスク
グラフ 一般に、ＬＵＤ、ＦＥ及びＢＳは各ロウが連続的に正規
化され、正規化されたロウの対角線下の非ゼロ要素（つ
まり、”Ｘ”或は”Ｆ”）が更新されるべきことを要求
する。当業者において周知のように、マトリックス内の
Ｘ及びＦの位置のみに基づいて、そのマトリックスによ
って表わされるセットの方程式を解くために必要とされ
る操作のスケジュールを生成することができる。遂行さ
れるべき操作及びこれらの相互依存の表現を描くことが
できる。このような表現は”タスクグラフ（task grap
h）”として知られている。
グラフ 一般に、ＬＵＤ、ＦＥ及びＢＳは各ロウが連続的に正規
化され、正規化されたロウの対角線下の非ゼロ要素（つ
まり、”Ｘ”或は”Ｆ”）が更新されるべきことを要求
する。当業者において周知のように、マトリックス内の
Ｘ及びＦの位置のみに基づいて、そのマトリックスによ
って表わされるセットの方程式を解くために必要とされ
る操作のスケジュールを生成することができる。遂行さ
れるべき操作及びこれらの相互依存の表現を描くことが
できる。このような表現は”タスクグラフ（task grap
h）”として知られている。
【００２２】マトリックスからのタスクグラフの構築は
当業者においては周知である。Ｏ．ウイング（Wing）及
びＪ．ヒュング（Huang ）によってコンピュータに関す
る米国電気電子学会議事録（I.E.E.E. Trans. on Compu
ters）、Ｖｏｌ．Ｃ−２９、ページ６３２−６３８（１
９８０年７月）に掲載の論文『線型方程式のパラレル解
決の計算モデル（A Computation Model of Parallel So
lution of Linear Equation ）』、及びＰ．サダヤパン
（Sadayappan）及びＶ．ビスバナサン（V.Visvanathan
）によってコンピュータに関する米国電気電子学会議
事録（I.E.E.E. Trans. on Computers）、Ｖｏｌ．Ｃ−
３７、ページ１６３４−１６４２（１９８８年１２月）
に掲載の論文『共有メモリ多重プロセッサ上での回路シ
ミュレーション（Circuit Simulation on Shared Memor
y Multiprocessors ）がここに本明細書の参考のために
編入される。タスクグラフはマトリックス内の非ゼロ及
び充填要素（fill-in element ）のパターンから誘導す
ることができる。図６は図５に示されるマトリックスと
関連するタスクグラフを表わす。このタスクグラフは各
ロウ正規化、ロウ更新及び逆方向置換（back-substitut
ion ）操作を一つのタスクとして表わし、これらタスク
の相互依存を示すことによって得ることができる。タス
クはタスクグラフ内において遂行されるべき操作の記述
を包囲する円によって表わされる。”Ｎ”を接頭語とす
る記述は正規化操作を表わす。”Ｕ”を接頭語とする記
述は更新操作を表わし、そして”Ｂ”を接頭語とする記
述は逆方向置換操作を表わす。接頭語”Ｎ”及び”Ｕ”
に続く数は操作されるべきロウを示す。例えば、記述”
Ｎ１”を含むタスクはロウ１を正規化することを意味
し、記述”Ｕ２Ｗ１”を含むタクスはロウ１からの情報
にてロウ２を更新することを意味する。接頭語”Ｂ”に
続くペアの数は、それぞれ、逆方向置換に関与するマト
リックス内の要素のロウ及びカラムである。あるタスク
はそれに情報を供給する全ての先行するタスクが終了し
てからのみ遂行できる。
当業者においては周知である。Ｏ．ウイング（Wing）及
びＪ．ヒュング（Huang ）によってコンピュータに関す
る米国電気電子学会議事録（I.E.E.E. Trans. on Compu
ters）、Ｖｏｌ．Ｃ−２９、ページ６３２−６３８（１
９８０年７月）に掲載の論文『線型方程式のパラレル解
決の計算モデル（A Computation Model of Parallel So
lution of Linear Equation ）』、及びＰ．サダヤパン
（Sadayappan）及びＶ．ビスバナサン（V.Visvanathan
）によってコンピュータに関する米国電気電子学会議
事録（I.E.E.E. Trans. on Computers）、Ｖｏｌ．Ｃ−
３７、ページ１６３４−１６４２（１９８８年１２月）
に掲載の論文『共有メモリ多重プロセッサ上での回路シ
ミュレーション（Circuit Simulation on Shared Memor
y Multiprocessors ）がここに本明細書の参考のために
編入される。タスクグラフはマトリックス内の非ゼロ及
び充填要素（fill-in element ）のパターンから誘導す
ることができる。図６は図５に示されるマトリックスと
関連するタスクグラフを表わす。このタスクグラフは各
ロウ正規化、ロウ更新及び逆方向置換（back-substitut
ion ）操作を一つのタスクとして表わし、これらタスク
の相互依存を示すことによって得ることができる。タス
クはタスクグラフ内において遂行されるべき操作の記述
を包囲する円によって表わされる。”Ｎ”を接頭語とす
る記述は正規化操作を表わす。”Ｕ”を接頭語とする記
述は更新操作を表わし、そして”Ｂ”を接頭語とする記
述は逆方向置換操作を表わす。接頭語”Ｎ”及び”Ｕ”
に続く数は操作されるべきロウを示す。例えば、記述”
Ｎ１”を含むタスクはロウ１を正規化することを意味
し、記述”Ｕ２Ｗ１”を含むタクスはロウ１からの情報
にてロウ２を更新することを意味する。接頭語”Ｂ”に
続くペアの数は、それぞれ、逆方向置換に関与するマト
リックス内の要素のロウ及びカラムである。あるタスク
はそれに情報を供給する全ての先行するタスクが終了し
てからのみ遂行できる。
【００２３】３．実施例 ３．１ 概要 図６に示されるように、タスクグラフが二つ或はそれ以
上のタスクが独立していることを示す場合、タスクグラ
フはこれらタスクをパラレルにて遂行することによって
より速く完結することができる。図７に表わされる本発
明の実施例はススクがほぼパラレルに遂行されることを
許す。
上のタスクが独立していることを示す場合、タスクグラ
フはこれらタスクをパラレルにて遂行することによって
より速く完結することができる。図７に表わされる本発
明の実施例はススクがほぼパラレルに遂行されることを
許す。
【００２４】３．２ 実施例の編成 図７は本発明の実施例の全体の様子を示す。これは分散
メモリマルチプロセッサシステムに基づき、３つの処理
要素７０７（”ＰＥ”）、通信網コントローラ７０
５（”ＣＮＣ”）によって制御される一つの通信網７０
３（”ＣＮ”）及び一つのホストプロセッサ７０１から
成る。この実施例においては、３つのＰＥが存在する
が、当業者においては、いかにして異なる数のＰＥを持
つように設計を修正したら良いかは周知である。この実
施例においては、ＣＮＣはホストに対するインターフェ
ースを提供するが、他の実施例においては、ホストが直
接にＰＥ或はＣＮの一部とインターフェースすることも
できる。この実施例においては、ＣＮＣはＣＮ及び各Ｐ
Ｅ内の通信プロセッサ８０９を制御する。
メモリマルチプロセッサシステムに基づき、３つの処理
要素７０７（”ＰＥ”）、通信網コントローラ７０
５（”ＣＮＣ”）によって制御される一つの通信網７０
３（”ＣＮ”）及び一つのホストプロセッサ７０１から
成る。この実施例においては、３つのＰＥが存在する
が、当業者においては、いかにして異なる数のＰＥを持
つように設計を修正したら良いかは周知である。この実
施例においては、ＣＮＣはホストに対するインターフェ
ースを提供するが、他の実施例においては、ホストが直
接にＰＥ或はＣＮの一部とインターフェースすることも
できる。この実施例においては、ＣＮＣはＣＮ及び各Ｐ
Ｅ内の通信プロセッサ８０９を制御する。
【００２５】各ＰＥは通信網にインターフェースを提供
する一つの通信プロセッサ、アドレス計算の任務を持つ
整数ユニット、浮動小数点ユニット、正規化されたばか
りのロウを保持するためのキャッシュ、及びマトリック
スの一部を保持するためのランダムアクセスメモリを持
つ。ホストプロセッサはタスクグラフ及びタスクスケジ
ュールを構築するために必要な前処理を遂行する。
する一つの通信プロセッサ、アドレス計算の任務を持つ
整数ユニット、浮動小数点ユニット、正規化されたばか
りのロウを保持するためのキャッシュ、及びマトリック
スの一部を保持するためのランダムアクセスメモリを持
つ。ホストプロセッサはタスクグラフ及びタスクスケジ
ュールを構築するために必要な前処理を遂行する。
【００２６】３．３ 操作 初期値設定プログラムはホスト上で実行される。システ
ム内の各処理要素は初期値設定制御信号を持つが、これ
によって通信網からメモリ内にデータが読み込まれる。
処理要素内にプログラム及びデータがいったんロードさ
れると、これらはタスクの遂行を開始することができ
る。
ム内の各処理要素は初期値設定制御信号を持つが、これ
によって通信網からメモリ内にデータが読み込まれる。
処理要素内にプログラム及びデータがいったんロードさ
れると、これらはタスクの遂行を開始することができ
る。
【００２７】３．４ 通信網コントローラ（ＣＮＣ） 図９に示されるように、ＣＮＣ９０３はホスト９０９と
処理要素９０５との間の通信を扱い、またシーケンシン
グユニットを制御する。シーケンシングユニットはＣＮ
Ｃ内に存在し、前処理の際に生成された通信スケジュー
ルを取り出す。通信スケジュールは処理要素間の通信を
制御するために使用される。
処理要素９０５との間の通信を扱い、またシーケンシン
グユニットを制御する。シーケンシングユニットはＣＮ
Ｃ内に存在し、前処理の際に生成された通信スケジュー
ルを取り出す。通信スケジュールは処理要素間の通信を
制御するために使用される。
【００２８】３．５ 通信網（ＣＮ） 前述したように、ロウ操作及び通信はタスクグラフの実
行の前に事前に決定される。処理要素９０５は、従っ
て、それが通信網９０１に送信する情報が通信網コント
ローラ９０３によって正しくルートされることを想定す
ることができる。より具体的には、処理要素９０５内の
通信プロセッサ９０７は通信網コントローラがこれを通
信網上に置くことができることを示すまで情報を保持す
る。
行の前に事前に決定される。処理要素９０５は、従っ
て、それが通信網９０１に送信する情報が通信網コント
ローラ９０３によって正しくルートされることを想定す
ることができる。より具体的には、処理要素９０５内の
通信プロセッサ９０７は通信網コントローラがこれを通
信網上に置くことができることを示すまで情報を保持す
る。
【００２９】通信網を実現する方法は幾通りもある。一
つのオプションはクロスバースイッチの使用を伴う。他
の幾つかのオプションでは環状通信システム或はバスが
使用される。Ｒ．テリチェフスキー（Telichevesky）、
Ｐ．アグラワル（Agrawal ）及びＪ．トロッタ（Trotte
r ）らによって米国電気電子学会議事録ＩＣＣＤ９１
（I.E.E.E. Proceedings ICCD 91）、ボストン（１９９
１）に発表の論文『多重プロセッサ上のでの効率的な希
薄マトリックス因子化のための高速シケジューリングス
キーム（Fast Scheduling Schemes for Efficient Spar
se Matrix Factorization on Multiprocessors）』は処
理要素の速度の半分の速度でランするバスシステムで本
発明の一つの実施例における場合のように処理要素内の
プロセッサとしてインテル１８６０マイクロプロセッサ
が使用された場合、１６のプロセッサに十分に対応でき
ることを示す。バススキームは実現が容易であり、また
複数のプロセッサユニットに同報通信できるという長所
を持つ。
つのオプションはクロスバースイッチの使用を伴う。他
の幾つかのオプションでは環状通信システム或はバスが
使用される。Ｒ．テリチェフスキー（Telichevesky）、
Ｐ．アグラワル（Agrawal ）及びＪ．トロッタ（Trotte
r ）らによって米国電気電子学会議事録ＩＣＣＤ９１
（I.E.E.E. Proceedings ICCD 91）、ボストン（１９９
１）に発表の論文『多重プロセッサ上のでの効率的な希
薄マトリックス因子化のための高速シケジューリングス
キーム（Fast Scheduling Schemes for Efficient Spar
se Matrix Factorization on Multiprocessors）』は処
理要素の速度の半分の速度でランするバスシステムで本
発明の一つの実施例における場合のように処理要素内の
プロセッサとしてインテル１８６０マイクロプロセッサ
が使用された場合、１６のプロセッサに十分に対応でき
ることを示す。バススキームは実現が容易であり、また
複数のプロセッサユニットに同報通信できるという長所
を持つ。
【００３０】３．６ 処理要素（ＰＥ） 処理要素７０７はタスクを遂行するための主計算エンジ
ンである。従って、これは通信するため及び様々な機能
を評価するために使用される複数の資源を含む。これは
倍精度浮動小数点値を迅速に読むことを可能にする広い
データバス（６４ビット）を持つ。これはまた８Ｋデー
タキャッシュを含むが、これは、ソースロウ及びそのイ
ンデックス値を保持するのに十分な容量である。正規化
及び更新のためのコードを保持するためにインストラク
ションキャッシュを使用することもできる。主メモリは
プロセッサにどのロウを正規化及び更新すべきかを告げ
る事前にコンパイルされたインストラクションリストの
みを保持する。整数ユニットはアドレス計算のために浮
動小数点ユニットとパラレルに動作できる。浮動小数点
ユニットは、パイプライン連結された掛け算加算モード
（これは更新のコア操作である）にて使用し、スループ
ットを向上させることができる。ＰＥはデータ構造内の
様々な要素のアドレスを計算するために整数を操作でき
なければならない。マトリックスのロウ及びこれらのイ
ンデックスを格納するために高速メモリ或はキャッシュ
が使用される。これらタスクのためにカスタムＶＬＳＩ
集積回路を特別に設計することもできる。別の実施例に
おいては、専用プロセッサがマイクロコントローラ及び
高速専用浮動小数点ユニットと共に使用される。別の方
法として、キャッシュメモリ及び浮動小数点ユニットを
持つ任意の汎用マイクロプロセッサを使用することもで
きる。
ンである。従って、これは通信するため及び様々な機能
を評価するために使用される複数の資源を含む。これは
倍精度浮動小数点値を迅速に読むことを可能にする広い
データバス（６４ビット）を持つ。これはまた８Ｋデー
タキャッシュを含むが、これは、ソースロウ及びそのイ
ンデックス値を保持するのに十分な容量である。正規化
及び更新のためのコードを保持するためにインストラク
ションキャッシュを使用することもできる。主メモリは
プロセッサにどのロウを正規化及び更新すべきかを告げ
る事前にコンパイルされたインストラクションリストの
みを保持する。整数ユニットはアドレス計算のために浮
動小数点ユニットとパラレルに動作できる。浮動小数点
ユニットは、パイプライン連結された掛け算加算モード
（これは更新のコア操作である）にて使用し、スループ
ットを向上させることができる。ＰＥはデータ構造内の
様々な要素のアドレスを計算するために整数を操作でき
なければならない。マトリックスのロウ及びこれらのイ
ンデックスを格納するために高速メモリ或はキャッシュ
が使用される。これらタスクのためにカスタムＶＬＳＩ
集積回路を特別に設計することもできる。別の実施例に
おいては、専用プロセッサがマイクロコントローラ及び
高速専用浮動小数点ユニットと共に使用される。別の方
法として、キャッシュメモリ及び浮動小数点ユニットを
持つ任意の汎用マイクロプロセッサを使用することもで
きる。
【００３１】３．７．１ 整数ユニット 整数ユニット８０３はメモリシステムに対するアドレス
を計算し、プロセッサの基本分岐及び制御インストラク
ションを実現する。様々なアドレスを計算するための整
数ユニットの使用が浮動小数点プロセッサの速度に悪影
響を与えないように配慮すべきである。
を計算し、プロセッサの基本分岐及び制御インストラク
ションを実現する。様々なアドレスを計算するための整
数ユニットの使用が浮動小数点プロセッサの速度に悪影
響を与えないように配慮すべきである。
【００３２】３．７．２ キャッシュ 処理要素は一つ或は複数のマトリックスのロウを表わす
データを保持するのに十分な大きさのキャッシュ８０５
を持つ。これはマトリックスの他のロウをより高いロウ
番号にて更新するために使用されるソースロウを効率的
に格納することを可能にする。
データを保持するのに十分な大きさのキャッシュ８０５
を持つ。これはマトリックスの他のロウをより高いロウ
番号にて更新するために使用されるソースロウを効率的
に格納することを可能にする。
【００３３】３．７．３浮動小数点ユニット 処理要素は全ての必要な演算計算を扱うための高速浮動
小数点ユニット８０７を含む。正確な回路シミュレーシ
ョンのために倍精度が好ましい。
小数点ユニット８０７を含む。正確な回路シミュレーシ
ョンのために倍精度が好ましい。
【００３４】３．７．４ メモリ メモリシステム８１１はマトリックス内のロウを表わす
データへのランダムアクセスを許す。メモリがランダム
及び高速度にてアクセスされるため、可能な限りの高速
度を達成するために静的メモリが好ましい。
データへのランダムアクセスを許す。メモリがランダム
及び高速度にてアクセスされるため、可能な限りの高速
度を達成するために静的メモリが好ましい。
【００３５】３．７．５ 通信プロセッサ（ＣＰ） 通信プロセッサ８０９は処理要素７０７の通信網７０３
にインターフェースを提供する部分である。通信プロセ
ッサは処理要素がデータを通信プロセッサに送ること或
はこの逆を可能にする双方向データバッファを含む。こ
のバッファの利点はデータを通信網に伝送するために待
ち行列に待たせている間に、及びデータが受信されてい
る間に処理要素が計算を遂行できることである。マトリ
ックス内の要素を表わすデータは通信網上をアンタッグ
形式（untagged form ）にて伝送される。従って、処理
要素はその意味を示すためにデータの文脈に依存する。
こうして、バッファは図１０に示されるような先入先だ
し（ＦＩＦＯ）待ち行列として実現される。高速通信を
達成するため、通信バスは９６ビット幅とされる。他の
幾つかの実施例においては、通信バスは異なる幅を持つ
ことも考えられる。処理要素の内部バスは６４ビット幅
であるが、但し、通信バスの幅と等しい或は等しくない
他の幅であっても良い。
にインターフェースを提供する部分である。通信プロセ
ッサは処理要素がデータを通信プロセッサに送ること或
はこの逆を可能にする双方向データバッファを含む。こ
のバッファの利点はデータを通信網に伝送するために待
ち行列に待たせている間に、及びデータが受信されてい
る間に処理要素が計算を遂行できることである。マトリ
ックス内の要素を表わすデータは通信網上をアンタッグ
形式（untagged form ）にて伝送される。従って、処理
要素はその意味を示すためにデータの文脈に依存する。
こうして、バッファは図１０に示されるような先入先だ
し（ＦＩＦＯ）待ち行列として実現される。高速通信を
達成するため、通信バスは９６ビット幅とされる。他の
幾つかの実施例においては、通信バスは異なる幅を持つ
ことも考えられる。処理要素の内部バスは６４ビット幅
であるが、但し、通信バスの幅と等しい或は等しくない
他の幅であっても良い。
【００３６】４．スケジューリング技法 上に説明のコンピュータはマトリックスを解くために使
用できる。このコンピュータは、３つの処理要素を持
ち、各々が自体のメモリを持つため、マトリックスのロ
ウはこれら処理要素の間で分散される。各ロウに関する
操作はある程度まで独立しているが、処理要素間で交信
を必要とする幾らかの情報がある。このため、プロセッ
サが他のプロセッサによって遂行された計算の結果を必
要とする場合、通信が起こる。
用できる。このコンピュータは、３つの処理要素を持
ち、各々が自体のメモリを持つため、マトリックスのロ
ウはこれら処理要素の間で分散される。各ロウに関する
操作はある程度まで独立しているが、処理要素間で交信
を必要とする幾らかの情報がある。このため、プロセッ
サが他のプロセッサによって遂行された計算の結果を必
要とする場合、通信が起こる。
【００３７】図１３は異なるプロセッサ上で異なるタス
クが実行されることを示すタスクグラフを表わす。第一
の処理要素によって遂行されるタスクは円によって表わ
される。第二の処理要素によって遂行されるタスクは四
角によって表わされ、第三の処理要素によって遂行され
るタスクは三角によって表わされる。通信網を通じての
処理要素間通信は図１３においてタスク間の点線によっ
て表わされる。タスクはそれが依存する全てのタクスが
完結した時実行することができる。従って、各処理要素
によって遂行されるべき下位セットのタスクをスケジュ
ールすることが可能である。加えて、処理要素間で起こ
るべき通信のリストをスケジュールすることができる。
セットの方程式は各プロセッサにそれが実行すべきタス
クのリストを提供し、スケジューラに通信のリストを提
供することによって解くことができるが、これらの両者
ともタスクグラフから得ることができる。図１４は図１
３のタスクグラフから得られるスケジュールを示す。本
セクションの残りの部分では図１３のタスクグラフ及び
図１４のタスクスケジュールが一例としての問題及び図
７のコンピュータを与えられた時、いかにして構築され
るかを詳細に説明する。
クが実行されることを示すタスクグラフを表わす。第一
の処理要素によって遂行されるタスクは円によって表わ
される。第二の処理要素によって遂行されるタスクは四
角によって表わされ、第三の処理要素によって遂行され
るタスクは三角によって表わされる。通信網を通じての
処理要素間通信は図１３においてタスク間の点線によっ
て表わされる。タスクはそれが依存する全てのタクスが
完結した時実行することができる。従って、各処理要素
によって遂行されるべき下位セットのタスクをスケジュ
ールすることが可能である。加えて、処理要素間で起こ
るべき通信のリストをスケジュールすることができる。
セットの方程式は各プロセッサにそれが実行すべきタス
クのリストを提供し、スケジューラに通信のリストを提
供することによって解くことができるが、これらの両者
ともタスクグラフから得ることができる。図１４は図１
３のタスクグラフから得られるスケジュールを示す。本
セクションの残りの部分では図１３のタスクグラフ及び
図１４のタスクスケジュールが一例としての問題及び図
７のコンピュータを与えられた時、いかにして構築され
るかを詳細に説明する。
【００３８】４．１ 表記法及び定義
【外１】
【００３９】マトリックスＡのＬＵ分解（decompositio
n ）は以下の３つの基本タイプの一連の動作として表わ
すことができる。
n ）は以下の３つの基本タイプの一連の動作として表わ
すことができる。
【００４０】Ｄｋとして表記される除法は以下のように
定義される。つまり、ｋ＝１、２、．．．、ｎに対し
て：
定義される。つまり、ｋ＝１、２、．．．、ｎに対し
て：
【数１】
【００４１】Ｎｋとして表記されるロウに関する正規化
（row-wise normalization）は以下のように定義され
る。つまり、全ての非ゼロａkjに対して、
（row-wise normalization）は以下のように定義され
る。つまり、全ての非ゼロａkjに対して、
【数２】
【００４２】ロウｋにて更新されているロウｉに対応す
るｋ→ｉにて表記されるロウに関する更新（row-wise u
pdate ）は以下のように定義される。つまり、全ての非
ゼロａkjに対して、
るｋ→ｉにて表記されるロウに関する更新（row-wise u
pdate ）は以下のように定義される。つまり、全ての非
ゼロａkjに対して、
【数３】
【００４３】我々は方程式３内のｋをソースロウと呼
び、ｉを宛先（destination)、目標（target）或は出力
（fanout）ロウと呼ぶものとする。この文献内におい
て、除法は通常正規化の初期フェーズであると見なされ
る。但し、最新鋭のハードウエアは浮動小数点除法（通
常非常にコストの高い操作）を背景プロセスとして乗法
−加法操作（multiply-add operation）と同時に遂行す
ることを可能にし、この別個のタスクとしての扱いを正
当化する。各ロウに関する正規化或は更新は、通常、最
大性能を達成するためにパイプライン連結された一連の
要素乗法−加法操作としてリアルプロセッサ内で実現さ
れる。
び、ｉを宛先（destination)、目標（target）或は出力
（fanout）ロウと呼ぶものとする。この文献内におい
て、除法は通常正規化の初期フェーズであると見なされ
る。但し、最新鋭のハードウエアは浮動小数点除法（通
常非常にコストの高い操作）を背景プロセスとして乗法
−加法操作（multiply-add operation）と同時に遂行す
ることを可能にし、この別個のタスクとしての扱いを正
当化する。各ロウに関する正規化或は更新は、通常、最
大性能を達成するためにパイプライン連結された一連の
要素乗法−加法操作としてリアルプロセッサ内で実現さ
れる。
【００４４】これら操作は以下の規則に従う限り任意の
シーケンスにて実行することができる。 Ｉ．ＮｋはＤｋが完結するまで開始できない。 ＩＩ．Ｄｋはａkkを修正する全ての更新操作が完結する
まで開始できない。 ＩＩＩ．ｋ→ｉはａikを修正する全ての更新が完結する
まで開始できない。 ＩＶ．ｋ→ｉ内の要素ａijはａkjの正規化が完結するま
で更新できない。
シーケンスにて実行することができる。 Ｉ．ＮｋはＤｋが完結するまで開始できない。 ＩＩ．Ｄｋはａkkを修正する全ての更新操作が完結する
まで開始できない。 ＩＩＩ．ｋ→ｉはａikを修正する全ての更新が完結する
まで開始できない。 ＩＶ．ｋ→ｉ内の要素ａijはａkjの正規化が完結するま
で更新できない。
【００４５】規則（Ｉ）から（ＩＩＩ）は強い意味にお
いてロウに関する操作との関連で依存性を確立する。つ
まり、ある操作は他が全ての結果の格納を完了するまで
オペランドを取りに行く動作を開始できない。これは、
通常、パイプライン連結されたシステムに対しては悪い
特性である。但し、規則（ＩＶ）は、ロウ更新タスク
が、両方のパイプラインが同一速度にてランするという
前提で、正規化操作の第一の結果が入手されると直ちに
開始されることを許す。この規則は新しいタイプの依存
性を確立するが、我々はこれを穏やかな依存（mild dep
endency ）と呼ぶ。
いてロウに関する操作との関連で依存性を確立する。つ
まり、ある操作は他が全ての結果の格納を完了するまで
オペランドを取りに行く動作を開始できない。これは、
通常、パイプライン連結されたシステムに対しては悪い
特性である。但し、規則（ＩＶ）は、ロウ更新タスク
が、両方のパイプラインが同一速度にてランするという
前提で、正規化操作の第一の結果が入手されると直ちに
開始されることを許す。この規則は新しいタイプの依存
性を確立するが、我々はこれを穏やかな依存（mild dep
endency ）と呼ぶ。
【００４６】これらタスク及びこれらの間の依存は一つ
のノードセットＶ及び（強い及び穏やかな依存に対応す
る）２つの弧セットＥs 及びＥm から成る一般マルチタ
スクグラフＧ（Ｖ、Ｅs 、Ｅm ）として便宜的に表わす
ことができる。このタスクグラフはサイクルを持たず、
直接循環グラフ（Direct Acyclic Graph、ＤＡＧ）であ
る。多重プロセッサベクトルマシーン内のパイプライン
連結を正しく活用するために、我々は以下のタスクモデ
ルを提案する。
のノードセットＶ及び（強い及び穏やかな依存に対応す
る）２つの弧セットＥs 及びＥm から成る一般マルチタ
スクグラフＧ（Ｖ、Ｅs 、Ｅm ）として便宜的に表わす
ことができる。このタスクグラフはサイクルを持たず、
直接循環グラフ（Direct Acyclic Graph、ＤＡＧ）であ
る。多重プロセッサベクトルマシーン内のパイプライン
連結を正しく活用するために、我々は以下のタスクモデ
ルを提案する。
【００４７】各ノードυi ∈Ｖは図１４に示されるよう
にパイプライン連結されたタスクに対応する。図１４は
リアルプロセッサ内でのタスクの実行を示す。第一のピ
ースのデータはこのパイプラインにｔ＝ｔifにおいて入
る。パイプライン遅延に対応する時間遅延ｐi （ｔ＝ｔ
of＝ｔif＋ｐi ）の後に、第一の要素の演算の結果が入
手可能となる。パイプラインのスループット時間に要素
操作の数を掛けた値に対応する時間ｃi の後に、最後の
ピースのデータがパイプライン内に供給され、プロセッ
サはパイプラインに新たなタスクに対応する幾つかのデ
ータの供給を開始する準備が整う。ｔ＝ｔol＝ｔif＋ｃ
i ＋ｐi において、最後の要素演算の結果が得られ、タ
スクυi は終了する。タスクυj がυi に強く依存する
場合は、これは、ｔ＝ｔolにおいて開始できるが、穏や
かな依存の場合は、これは別のプロセッサ内においてｔ
＝ｔofとなると直ちに、或は同一プロセッサ内でｔ−ｔ
ilにおいて開始することができる。強い依存はｅij s に
よって表わされ、穏やかな依存はｅij m によって表わさ
れる。
にパイプライン連結されたタスクに対応する。図１４は
リアルプロセッサ内でのタスクの実行を示す。第一のピ
ースのデータはこのパイプラインにｔ＝ｔifにおいて入
る。パイプライン遅延に対応する時間遅延ｐi （ｔ＝ｔ
of＝ｔif＋ｐi ）の後に、第一の要素の演算の結果が入
手可能となる。パイプラインのスループット時間に要素
操作の数を掛けた値に対応する時間ｃi の後に、最後の
ピースのデータがパイプライン内に供給され、プロセッ
サはパイプラインに新たなタスクに対応する幾つかのデ
ータの供給を開始する準備が整う。ｔ＝ｔol＝ｔif＋ｃ
i ＋ｐi において、最後の要素演算の結果が得られ、タ
スクυi は終了する。タスクυj がυi に強く依存する
場合は、これは、ｔ＝ｔolにおいて開始できるが、穏や
かな依存の場合は、これは別のプロセッサ内においてｔ
＝ｔofとなると直ちに、或は同一プロセッサ内でｔ−ｔ
ilにおいて開始することができる。強い依存はｅij s に
よって表わされ、穏やかな依存はｅij m によって表わさ
れる。
【００４８】図６は図５に示される希薄マトリックスの
ＬＵ分解を表わすタスクグラフを示す。我々は、このケ
ースにおいては、パイプライン遅延は１サイクル、乗法
−加法演算に対するこのスループットは１サイクル、そ
して除法（非パイプライン）は１サイクルを要するもの
と仮定する。
ＬＵ分解を表わすタスクグラフを示す。我々は、このケ
ースにおいては、パイプライン遅延は１サイクル、乗法
−加法演算に対するこのスループットは１サイクル、そ
して除法（非パイプライン）は１サイクルを要するもの
と仮定する。
【００４９】
【外２】
【００５０】
【数４】
【００５１】タスクグラフの高さＨは最も高いレベルの
所の頂点のレベルであると定義される。つまり、
所の頂点のレベルであると定義される。つまり、
【００５２】
【数５】
【００５３】タスクグラフの高さがマトリックス分解の
最小完結時間と関連することは明らかである。短くて太
いタスクグラフは長くて細いタスクよりも良好なパラレ
ル性を活かすことができると期待できる。図６の例にお
いては、タスクグラフの高さは７である。但し、タスク
のレベルのみでは幾つかのハードウエア特徴及び異なる
タスクサイズを正しくモデル化するのには不十分である
ために、我々は、任意のタスクυi の完結時間ｄi につ
いての概念を導入するが、これは以下のように定義され
る。
最小完結時間と関連することは明らかである。短くて太
いタスクグラフは長くて細いタスクよりも良好なパラレ
ル性を活かすことができると期待できる。図６の例にお
いては、タスクグラフの高さは７である。但し、タスク
のレベルのみでは幾つかのハードウエア特徴及び異なる
タスクサイズを正しくモデル化するのには不十分である
ために、我々は、任意のタスクυi の完結時間ｄi につ
いての概念を導入するが、これは以下のように定義され
る。
【００５４】
【数６】
【００５５】
【外３】
【００５６】
【数７】
【００５７】
【外４】
【００５８】
【数８】
【００５９】残り完結時間は、実際には、タスクυi が
いったん終了すると、υi に依存する全てのタスクの完
結のための最小時間はδi であることが知られているた
めに、任意のタスクの早い実行がどれだけ重要であるか
の尺度である。β−タスクに対するδはゼロであること
は明らかである。以下においては、我々は、δ−技法に
基づく線型時間及び疑似線型時間（linear time and qu
asi-linear time ）スケジューリングスキームにおける
全タスクグラフに対する残り完結時間の計算を行なうた
めのアルゴリズムについて説明する。
いったん終了すると、υi に依存する全てのタスクの完
結のための最小時間はδi であることが知られているた
めに、任意のタスクの早い実行がどれだけ重要であるか
の尺度である。β−タスクに対するδはゼロであること
は明らかである。以下においては、我々は、δ−技法に
基づく線型時間及び疑似線型時間（linear time and qu
asi-linear time ）スケジューリングスキームにおける
全タスクグラフに対する残り完結時間の計算を行なうた
めのアルゴリズムについて説明する。
【００６０】４．２ スケジューリング技法 多重プロセッサ環境においては、希薄マトリックスの因
子化（sparse matrixfactorization ）の際の計算資源
の活用に大きな影響を与える２つの主な要因が存在す
る。第一はプロセッサへのデータの割り当てであり、第
二は各プロセッサ内及び通信網内でのタスクスケジュー
リングである。以前、Ｒ．テリチェフスキー（Telichev
esky）、Ｐ．アグラワル（Agrawal ）及びＪ．トロッタ
ー（Trotter ）によって１９９１年９月にスペインのバ
ルセロナで開催されたアプリケーションスペシフィック
アレイプロセッサに関する国際会議（Int.Conf. on App
lications Specific Array Processors ）に発表の論文
『多重プロセッサ上での回路シミュレーションマトリッ
クスの因子化のための効率的な区分化法（EfficientPar
titioning Schemes for Circuit Simulation Matrix Fa
ctorization on Multiprocessors ）』において、我々
は幾つかの区分化アルゴリズムについて研究し、負荷均
衡技法が全体としての効率の点からほぼ最適な区画を与
えることを経験的に示した。２つのスケジューリング技
法が様々な区分化技法と組合わせて使用された。一つは
Ｊ．トロッタ（Trotter ）及びＰ．アグラワル（Agrawa
l ）によってコンピュータ支援設計に関する米国電気電
子学会主催の国際会議（I.E.E.E.Int. Conf. on Comput
er Aided Design）、サンタクララ、ＣＡ、ページ４３
８−４１１（１９９０年１１月）に発表の論文『分散メ
モリ多重プロセッサシステム上での回路シミュレーショ
ンアルゴリズム（Circuit Simulation Algorithmson a
Distributed Memory Multiprocessor System ）におい
て説明される単純なレベルをベースとする技法であり、
もう一つは貪欲スケジューリング技法（greedy schedul
ing technique ）である。レベルをベースとする技法に
おいては、あるレベルにおいてスケジュールされた全て
のタスクが次のレベルのタスクの実行の前に完結され
る。プロセッサは固定ステップ（lock-step ）様式にて
動作する。実行のために準備できたタスクが存在するの
にプロセッサが待たなければならないことがあるために
性能がある程度失われることは明らかである。後に説明
される単純な貪欲スケジューリングメカニズムはレベル
に基づく技法よりは良い結果を与える。但し、これは区
分化アルゴリズムによって課せられる理論上の最大性能
よりははるかに落ちる。
子化（sparse matrixfactorization ）の際の計算資源
の活用に大きな影響を与える２つの主な要因が存在す
る。第一はプロセッサへのデータの割り当てであり、第
二は各プロセッサ内及び通信網内でのタスクスケジュー
リングである。以前、Ｒ．テリチェフスキー（Telichev
esky）、Ｐ．アグラワル（Agrawal ）及びＪ．トロッタ
ー（Trotter ）によって１９９１年９月にスペインのバ
ルセロナで開催されたアプリケーションスペシフィック
アレイプロセッサに関する国際会議（Int.Conf. on App
lications Specific Array Processors ）に発表の論文
『多重プロセッサ上での回路シミュレーションマトリッ
クスの因子化のための効率的な区分化法（EfficientPar
titioning Schemes for Circuit Simulation Matrix Fa
ctorization on Multiprocessors ）』において、我々
は幾つかの区分化アルゴリズムについて研究し、負荷均
衡技法が全体としての効率の点からほぼ最適な区画を与
えることを経験的に示した。２つのスケジューリング技
法が様々な区分化技法と組合わせて使用された。一つは
Ｊ．トロッタ（Trotter ）及びＰ．アグラワル（Agrawa
l ）によってコンピュータ支援設計に関する米国電気電
子学会主催の国際会議（I.E.E.E.Int. Conf. on Comput
er Aided Design）、サンタクララ、ＣＡ、ページ４３
８−４１１（１９９０年１１月）に発表の論文『分散メ
モリ多重プロセッサシステム上での回路シミュレーショ
ンアルゴリズム（Circuit Simulation Algorithmson a
Distributed Memory Multiprocessor System ）におい
て説明される単純なレベルをベースとする技法であり、
もう一つは貪欲スケジューリング技法（greedy schedul
ing technique ）である。レベルをベースとする技法に
おいては、あるレベルにおいてスケジュールされた全て
のタスクが次のレベルのタスクの実行の前に完結され
る。プロセッサは固定ステップ（lock-step ）様式にて
動作する。実行のために準備できたタスクが存在するの
にプロセッサが待たなければならないことがあるために
性能がある程度失われることは明らかである。後に説明
される単純な貪欲スケジューリングメカニズムはレベル
に基づく技法よりは良い結果を与える。但し、これは区
分化アルゴリズムによって課せられる理論上の最大性能
よりははるかに落ちる。
【００６１】システムの利用率を向上させるためには、
良好と呼ばれるスケジューリングアルゴリズムは、起動
されたタスク間で最も重要なタスクを選択し、これを最
初に実行するようにスケジュールする能力がなければな
らない。Ｖ．シャーカ（Sarkar）は、ＭＩＴプレス（Th
e MIT Press ）、１９８９年に掲載の論文『多重コンピ
ュータ上での実行のための区分化及びスケジューリング
並列プログラム（Partitioning and Scheduling Parall
el Programs for Execution on Multicomputers ）』に
おいてクリティカルパススケジューリングに基づくアル
ゴリズムを提案するが、これは非常に良好な結果を与え
る。このスキームにおいては、第一にスケジュールされ
るタスクはクリティカルパス内に存在するタスクであ
る。次に、各ブランチが分析され、ローカルクリティカ
ルパスが反復的にスケジュールされる。不幸にして、こ
のアルゴリズムの時間に関する複雑さ（time complexit
y ）はＯ（Ｅ（Ｖ＋Ｅ））である。ここで、Ｅ及びＶ
は、それぞれ、タスクグラフ内のエッジの数及び頂点の
数を表わす。Ｅは依存を表わし、Ｖはタスクグラフ内に
存在するロウに関する操作の数を表わす。大きなタスク
グラフに対しては、スケジューリング時間が法外なもの
になる。
良好と呼ばれるスケジューリングアルゴリズムは、起動
されたタスク間で最も重要なタスクを選択し、これを最
初に実行するようにスケジュールする能力がなければな
らない。Ｖ．シャーカ（Sarkar）は、ＭＩＴプレス（Th
e MIT Press ）、１９８９年に掲載の論文『多重コンピ
ュータ上での実行のための区分化及びスケジューリング
並列プログラム（Partitioning and Scheduling Parall
el Programs for Execution on Multicomputers ）』に
おいてクリティカルパススケジューリングに基づくアル
ゴリズムを提案するが、これは非常に良好な結果を与え
る。このスキームにおいては、第一にスケジュールされ
るタスクはクリティカルパス内に存在するタスクであ
る。次に、各ブランチが分析され、ローカルクリティカ
ルパスが反復的にスケジュールされる。不幸にして、こ
のアルゴリズムの時間に関する複雑さ（time complexit
y ）はＯ（Ｅ（Ｖ＋Ｅ））である。ここで、Ｅ及びＶ
は、それぞれ、タスクグラフ内のエッジの数及び頂点の
数を表わす。Ｅは依存を表わし、Ｖはタスクグラフ内に
存在するロウに関する操作の数を表わす。大きなタスク
グラフに対しては、スケジューリング時間が法外なもの
になる。
【００６２】２つの新しいスケジューリング技法は残り
完結時間（δ）に基づく。これらスキームにおいては、
クリティカルパス内或は密集ブランチ内のタスクが他よ
りも大きなδ持つ傾向があるために、大きなδを持つタ
スクがその他のタスクの前に実行されるようにスケジュ
ールされる。このスケジューリング技法の正味効果はシ
ーカ技法ほど良好ではないが、δが全タスクグラフに対
して線型時間にて計算できるために、より小さなコスト
にて実現できる。以下では、我々は、いかにしてδを計
算するかを示し、次に、δ−技法に基づく２つのスケジ
ューリング技法を紹介し、最後に、実験的な結果を示
す。比較のために、我々は、Ｒ．テリチェフスキー（Te
lichevesky）、Ｐ．アグラワル（Agrawal ）及びＪ．ト
ロッター（Trotter ）によって１９９１年９月にスペイ
ンのバルセロナで開催されたアプリケーションスペシフ
ィックアレイプロセッサに関する国際会議（Int.Conf.
on Applications Specific Array Processors ）に発表
の論文『多重プロセッサ上での回路シミュレーションマ
トリックスの因子化のための効率的な区分化技法（Effi
cient Partitioning Schemes for Circuit Simulation
Matrix Factorizationon Multiprocessors ）』に記述
される貪欲スケジューリング技法の説明から開始する。
完結時間（δ）に基づく。これらスキームにおいては、
クリティカルパス内或は密集ブランチ内のタスクが他よ
りも大きなδ持つ傾向があるために、大きなδを持つタ
スクがその他のタスクの前に実行されるようにスケジュ
ールされる。このスケジューリング技法の正味効果はシ
ーカ技法ほど良好ではないが、δが全タスクグラフに対
して線型時間にて計算できるために、より小さなコスト
にて実現できる。以下では、我々は、いかにしてδを計
算するかを示し、次に、δ−技法に基づく２つのスケジ
ューリング技法を紹介し、最後に、実験的な結果を示
す。比較のために、我々は、Ｒ．テリチェフスキー（Te
lichevesky）、Ｐ．アグラワル（Agrawal ）及びＪ．ト
ロッター（Trotter ）によって１９９１年９月にスペイ
ンのバルセロナで開催されたアプリケーションスペシフ
ィックアレイプロセッサに関する国際会議（Int.Conf.
on Applications Specific Array Processors ）に発表
の論文『多重プロセッサ上での回路シミュレーションマ
トリックスの因子化のための効率的な区分化技法（Effi
cient Partitioning Schemes for Circuit Simulation
Matrix Factorizationon Multiprocessors ）』に記述
される貪欲スケジューリング技法の説明から開始する。
【００６３】４．２．１ 貪欲Ｏ（Ｅ）＋Ｏ（Ｖ）スケ
ジューリング発見的方法 貪欲技法（greedy technique）は以下のように動作す
る。各プロセッサは実行のために準備ができた全ての割
り当てられたタスクを実行する。つまり、それが依存す
る全てのタスクは既に完結されている。完結されてない
時は、プロセッサは停止することとなる。この技法は非
常に高速であり、殆どのケースにおいて、レベルに基づ
くアプローチよりも良好な結果を与える。但し、これ
は、プロセッサ間のより複雑な同期機構を必要とする。
以下では、この技法についての簡単な説明が行なわれ
る。
ジューリング発見的方法 貪欲技法（greedy technique）は以下のように動作す
る。各プロセッサは実行のために準備ができた全ての割
り当てられたタスクを実行する。つまり、それが依存す
る全てのタスクは既に完結されている。完結されてない
時は、プロセッサは停止することとなる。この技法は非
常に高速であり、殆どのケースにおいて、レベルに基づ
くアプローチよりも良好な結果を与える。但し、これ
は、プロセッサ間のより複雑な同期機構を必要とする。
以下では、この技法についての簡単な説明が行なわれ
る。
【００６４】我々は各タスクυj にυj が起動される前
に満たされなければならない依存ｄj の数を関連付け
る。初期タスクでは、明らかに、ｄj ＝０である。我々
はまたυj をそのデータ依存及びプロセッサ割り当てを
考慮したときタスクが実行できる最も早い時間を表わす
時間スタンプｔj と関連付ける。この技法の開始におい
ては、全てのｔj は０である。この技法が終了した時、
各ｔj はタスクυj の実行に対する開始時間を含む。各
プロセッサｐはローカルタイマｆp を持つが、これは、
最後のスケジュールされたタスクが完結した時の時間を
保持する。この技法は、タスクグラフが構築され、全て
のｄj が正しくセットされ、全てのｆp がゼロとされ、
そしてデータがＲ．テリチェフスキー（Telichevesk
y）、Ｐ．アグラワル（Agrawal ）及びＪ．トロッター
（Trotter ）によって１９９１年９月にスペインのバル
セロナで開催されたアプリケーションスペシフィックア
レイプロセッサに関する国際会議（Int.Conf. on Appli
cations Specific Array Processors ）に発表の論文
『多重プロセッサ上での回路シミュレーションマトリッ
クスの因子化のための効率的な区分化技法（Efficient
Partitioning Schemes for Circuit Simulation Matrix
Factorization on Multiprocessors ）』において説明
される負荷均衡区分化技法を使用して正しく分配された
後に開始する。
に満たされなければならない依存ｄj の数を関連付け
る。初期タスクでは、明らかに、ｄj ＝０である。我々
はまたυj をそのデータ依存及びプロセッサ割り当てを
考慮したときタスクが実行できる最も早い時間を表わす
時間スタンプｔj と関連付ける。この技法の開始におい
ては、全てのｔj は０である。この技法が終了した時、
各ｔj はタスクυj の実行に対する開始時間を含む。各
プロセッサｐはローカルタイマｆp を持つが、これは、
最後のスケジュールされたタスクが完結した時の時間を
保持する。この技法は、タスクグラフが構築され、全て
のｄj が正しくセットされ、全てのｆp がゼロとされ、
そしてデータがＲ．テリチェフスキー（Telichevesk
y）、Ｐ．アグラワル（Agrawal ）及びＪ．トロッター
（Trotter ）によって１９９１年９月にスペインのバル
セロナで開催されたアプリケーションスペシフィックア
レイプロセッサに関する国際会議（Int.Conf. on Appli
cations Specific Array Processors ）に発表の論文
『多重プロセッサ上での回路シミュレーションマトリッ
クスの因子化のための効率的な区分化技法（Efficient
Partitioning Schemes for Circuit Simulation Matrix
Factorization on Multiprocessors ）』において説明
される負荷均衡区分化技法を使用して正しく分配された
後に開始する。
【００６５】１．各プロセッサｐについて、ｄj ＝０と
なるように全てのタスクυj ∈Ｑp に訪れる。各訪れた
タスクυj に対して以下を遂行する。 ａ．υj を時間ｔj ＝ｍａｘ（ｔj 、ｆp ）にスケジュ
ールする。 ｂ．プロセッサｐ内のローカルタイマをｆp ＝ｔj ＋Ｃ
（υj ）にセットする。 ｃ．υj の完了、つまり、∃ｅijに依存する全てのタス
クυi に訪れる。個々の訪れたυi に対して以下を遂行
する。 ｉ． ｔi をｍａｘ（ｔi 、ｆp ）にセットする。 ｉｉ．ｄi ＝ｄi −１にセットする。
なるように全てのタスクυj ∈Ｑp に訪れる。各訪れた
タスクυj に対して以下を遂行する。 ａ．υj を時間ｔj ＝ｍａｘ（ｔj 、ｆp ）にスケジュ
ールする。 ｂ．プロセッサｐ内のローカルタイマをｆp ＝ｔj ＋Ｃ
（υj ）にセットする。 ｃ．υj の完了、つまり、∃ｅijに依存する全てのタス
クυi に訪れる。個々の訪れたυi に対して以下を遂行
する。 ｉ． ｔi をｍａｘ（ｔi 、ｆp ）にセットする。 ｉｉ．ｄi ＝ｄi −１にセットする。
【００６６】２．セット１を全てのタスクが全てのプロ
セッサ内でスケジュールされるまで反復する。 我々は、貪欲アルゴリズムに対する完結時間ｔG をスケ
ジューリングが完結した時のｆp の最大値であると定義
する。我々はまた貪欲スケジューリング利用率（greedy
scheduling utilization ）ηG を以下のように定義す
る。
セッサ内でスケジュールされるまで反復する。 我々は、貪欲アルゴリズムに対する完結時間ｔG をスケ
ジューリングが完結した時のｆp の最大値であると定義
する。我々はまた貪欲スケジューリング利用率（greedy
scheduling utilization ）ηG を以下のように定義す
る。
【００６７】
【数９】
【００６８】４．２．２ Ｏ（Ｖ）＋Ｏ（Ｅ）での残り
完結時間の計算 この技法の開始において、我々は、タスクグラフがレベ
ル化され、個々のノードυi はそれが依存するタスクの
リストυj を含むものと想定する。この依存は図６に示
されるのとは反対のアーク方向に対応する。最初、我々
は、Ｄ＝０にセットし、このため個々のノードυi はδ
i ＝０を含む。タスクグラフ内のレベルは１からＨまで
のレンジに及ぶが、ここで、Ｈは最高レベルである。こ
の技法は以下のように進行する。
完結時間の計算 この技法の開始において、我々は、タスクグラフがレベ
ル化され、個々のノードυi はそれが依存するタスクの
リストυj を含むものと想定する。この依存は図６に示
されるのとは反対のアーク方向に対応する。最初、我々
は、Ｄ＝０にセットし、このため個々のノードυi はδ
i ＝０を含む。タスクグラフ内のレベルは１からＨまで
のレンジに及ぶが、ここで、Ｈは最高レベルである。こ
の技法は以下のように進行する。
【００６９】１．各レベルｋの所で、ｋ＝Ｈから開始し
ｋ＝１に向って、ｈi ＝ｋとなるように全てのノードυ
i に訪れる。訪れた各ノードυi に対して以下を遂行す
る。 ａ．δs ＝δi ＋ｃi ＋ｐi にセットする。 ｂ．反対方向に全てのアークｅji s を横断し、δj ＝ｍ
ａｘ（δj 、δs ）にセットする。 ｃ．全てのアークｅji m を反対方向に横断し、以下を遂
行する。 ｉ．δm ＝δs −ｃj にセットする。 ｉｉ．δj ＝ｍａｘ（δm 、δi 、δj ）にセットす
る。
ｋ＝１に向って、ｈi ＝ｋとなるように全てのノードυ
i に訪れる。訪れた各ノードυi に対して以下を遂行す
る。 ａ．δs ＝δi ＋ｃi ＋ｐi にセットする。 ｂ．反対方向に全てのアークｅji s を横断し、δj ＝ｍ
ａｘ（δj 、δs ）にセットする。 ｃ．全てのアークｅji m を反対方向に横断し、以下を遂
行する。 ｉ．δm ＝δs −ｃj にセットする。 ｉｉ．δj ＝ｍａｘ（δm 、δi 、δj ）にセットす
る。
【００７０】２．Ｄ＝ｍａｘ（Ｄ、δs ）にセットす
る。 この技法の実行の終端において、全てのノードυi はδ
i にセットされ、Ｄは最早完結時間にセットされる。必
要であれば、我々は、１（ｂ）及び１（ｃ）内にδj を
最大となるようにさせたエッジをクリティカルエッジ
（critical edge）ｅj cとして注釈を付けることもでき
る。このセットのクリティカルエッジはクリティカルパ
ス及びその分岐を形成する。
る。 この技法の実行の終端において、全てのノードυi はδ
i にセットされ、Ｄは最早完結時間にセットされる。必
要であれば、我々は、１（ｂ）及び１（ｃ）内にδj を
最大となるようにさせたエッジをクリティカルエッジ
（critical edge）ｅj cとして注釈を付けることもでき
る。このセットのクリティカルエッジはクリティカルパ
ス及びその分岐を形成する。
【００７１】４．２．３ 垂直Ｏ（Ｖ ｌｏｇ Ｖ）ス
ケジューリング発見的方法 我々は各タスクυi をセクション４．２．２において計
算された残り完結時間δi と関連付ける。我々はまた各
υi をそのデータ依存及びプロセッサ割り当てを考慮し
たときタスクを実行することができる最も早い時間を表
わすタイムスタンプｔi と関連付ける。最後に、各ノー
ドはυi が起動される前に満たされなければならない依
存の数ｎｄi に関する情報を含む。各プロセッサｐは最
後のスケジュールされたタスクが完了した時間を保持す
るローカルタイマｆp を持つ。補助ｔV レジスタは分解
を完結するために必要な合計時間を含む。ここに説明さ
れる技法は２つのフェーズに分割される。第一のフェー
ズは実際のスケジューリングであり、第二のフェーズは
シミュレーションのみを目的としたスイムスタンプの計
算である。この技法は、ある区分化技法に従ってタスク
グラフが構築され、全てのδi 及びｎｄi が正しくセッ
トされ、全てのｆp ＝０、全てのｔi ＝０、ｔV ＝０及
びデータが分配された後に開始される。
ケジューリング発見的方法 我々は各タスクυi をセクション４．２．２において計
算された残り完結時間δi と関連付ける。我々はまた各
υi をそのデータ依存及びプロセッサ割り当てを考慮し
たときタスクを実行することができる最も早い時間を表
わすタイムスタンプｔi と関連付ける。最後に、各ノー
ドはυi が起動される前に満たされなければならない依
存の数ｎｄi に関する情報を含む。各プロセッサｐは最
後のスケジュールされたタスクが完了した時間を保持す
るローカルタイマｆp を持つ。補助ｔV レジスタは分解
を完結するために必要な合計時間を含む。ここに説明さ
れる技法は２つのフェーズに分割される。第一のフェー
ズは実際のスケジューリングであり、第二のフェーズは
シミュレーションのみを目的としたスイムスタンプの計
算である。この技法は、ある区分化技法に従ってタスク
グラフが構築され、全てのδi 及びｎｄi が正しくセッ
トされ、全てのｆp ＝０、全てのｔi ＝０、ｔV ＝０及
びデータが分配された後に開始される。
【００７２】１．各プロセッサ内でタスクをδの減少順
（decreasing order）に分類する（Ｏ（Ｖ ｌｏｇ
Ｖ）ステップ）。定理１は結果としてのスケジュールが
デッドロックを持たないことを示す。
（decreasing order）に分類する（Ｏ（Ｖ ｌｏｇ
Ｖ）ステップ）。定理１は結果としてのスケジュールが
デッドロックを持たないことを示す。
【００７３】２．各プロセッサｐについて、次のスケジ
ュールされたタスクυi に訪れる。各訪れたタスクυi
に対して以下を実行する。 ａ．ｎｄi ≠０ならば別のプロセッサに進み、そうでな
い時は、進行する。 ｂ．ｔi ＝ｔif＝ｍａｘ（ｔi 、ｆp ）にセットする。 ｃ．ｔol＝ｔif＋ｃi ＋ｐi にセットする。 ｄ．ｔof＝ｔif＋ｃi ＋ｐi にセットする。 ｅ．ｆp ＝ｔil＝ｔif＋ｃi にセットする。 ｆ．全てのアークｅij s を横断し、υi に強く依存する
各訪れられたυj に対して以下を遂行する。 ｉ．ｎｄj ＝ｎｄj −１にセットする。 ｉｉ．ｔj ＝ｍａｘ（ｔj 、ｔol）にセットする。 ｇ．全てのアークｅij m を横断し、υi に穏やかに依存
する各訪れらたυj に対して以下を実行する。 ｉ ｎｄj ＝ｎｄj −１にセットする。 ｉｉ．ｔj ＝ｍａｘ（ｔj 、ｔof）にセットする。 ｈ．ｔV ＝ｍａｘ（ｔol、ｔV ）にセットする。
ュールされたタスクυi に訪れる。各訪れたタスクυi
に対して以下を実行する。 ａ．ｎｄi ≠０ならば別のプロセッサに進み、そうでな
い時は、進行する。 ｂ．ｔi ＝ｔif＝ｍａｘ（ｔi 、ｆp ）にセットする。 ｃ．ｔol＝ｔif＋ｃi ＋ｐi にセットする。 ｄ．ｔof＝ｔif＋ｃi ＋ｐi にセットする。 ｅ．ｆp ＝ｔil＝ｔif＋ｃi にセットする。 ｆ．全てのアークｅij s を横断し、υi に強く依存する
各訪れられたυj に対して以下を遂行する。 ｉ．ｎｄj ＝ｎｄj −１にセットする。 ｉｉ．ｔj ＝ｍａｘ（ｔj 、ｔol）にセットする。 ｇ．全てのアークｅij m を横断し、υi に穏やかに依存
する各訪れらたυj に対して以下を実行する。 ｉ ｎｄj ＝ｎｄj −１にセットする。 ｉｉ．ｔj ＝ｍａｘ（ｔj 、ｔof）にセットする。 ｈ．ｔV ＝ｍａｘ（ｔol、ｔV ）にセットする。
【００７４】３．ステップ２を全てのタスクが訪れられ
るまで反復する。
るまで反復する。
【００７５】ステップ１に提案されるスケジューリング
スキームはあまりにも単純であり、デッドロック無しの
コードを生成することが明らかでないためこれが正しい
かどうか疑問に思われるかもしれない。ところがこれに
反して、以下の証明はデッドロック無しのコードに対す
る必要で十分な条件を与える。
スキームはあまりにも単純であり、デッドロック無しの
コードを生成することが明らかでないためこれが正しい
かどうか疑問に思われるかもしれない。ところがこれに
反して、以下の証明はデッドロック無しのコードに対す
る必要で十分な条件を与える。
【００７６】定理１ この証明は３つの部分に分けられ
る。第一の部分は単一プロセッサのケースに対応し、残
りの二つの部分は、プロセッサ間デッドロックを扱う。 ａ．２つのタスクυi 及びυj が同一プロセッサ内に存
在し、υi がυj に依存するものと想定する。すると、
デッドロックはυi がυj の前に実行されるようにスケ
ジュールされた時にのみ起こる。然しながら、υi がυ
j に依存する場合、少なくとも１つの直接経路Ｒk j,iが
存在するはずであり、従って、υp ∈Ｒk j,i及びυp ≠
υj という条件下で、δj ＝δi ＋Σk=j iコスト（υ
p ）である。コスト（υp ）＞０と想定すると、他は物
理的に可能でないために、δj ＞δi であり、υj はυ
i よりも前に実行されるようにスケジュールされること
となり、これは、初期デッドロック仮説に反する。 ｂ．υi 及びυj がプロセッサｐr 内に存在し、υm が
プロセッサｐs 内に存在するものと想定する。プロセッ
サ間デッドロックはυm がυj に依存し、υiがυm に
依存する時にのみ発生するが、但し、υi はυj の前に
起こるようにスケジュールされている。パート（ａ）と
同一の議論を用いて、我々は、δj ＞δm 及びδm ＞δ
i ということができる。推移関係δj ＞δi を用いる
と、（ａ）の場合と同一議論によってこの定理の証明を
完結することができる。 ｃ．（ｂ）からの帰納的結論により、我々は、いかなる
数のプロセッサ内にもデッドロックが存在しないことを
証明することができる。
る。第一の部分は単一プロセッサのケースに対応し、残
りの二つの部分は、プロセッサ間デッドロックを扱う。 ａ．２つのタスクυi 及びυj が同一プロセッサ内に存
在し、υi がυj に依存するものと想定する。すると、
デッドロックはυi がυj の前に実行されるようにスケ
ジュールされた時にのみ起こる。然しながら、υi がυ
j に依存する場合、少なくとも１つの直接経路Ｒk j,iが
存在するはずであり、従って、υp ∈Ｒk j,i及びυp ≠
υj という条件下で、δj ＝δi ＋Σk=j iコスト（υ
p ）である。コスト（υp ）＞０と想定すると、他は物
理的に可能でないために、δj ＞δi であり、υj はυ
i よりも前に実行されるようにスケジュールされること
となり、これは、初期デッドロック仮説に反する。 ｂ．υi 及びυj がプロセッサｐr 内に存在し、υm が
プロセッサｐs 内に存在するものと想定する。プロセッ
サ間デッドロックはυm がυj に依存し、υiがυm に
依存する時にのみ発生するが、但し、υi はυj の前に
起こるようにスケジュールされている。パート（ａ）と
同一の議論を用いて、我々は、δj ＞δm 及びδm ＞δ
i ということができる。推移関係δj ＞δi を用いる
と、（ａ）の場合と同一議論によってこの定理の証明を
完結することができる。 ｃ．（ｂ）からの帰納的結論により、我々は、いかなる
数のプロセッサ内にもデッドロックが存在しないことを
証明することができる。
【００７７】上の技法はデッドロックの無いスケジュー
ルを生成するが、ひつとの明らかな短所を持つ。これは
起動されたタスクが存在するのにもかかわらず幾つかの
プロセッサがアイドル状態で他のプロセッサからのデー
タの到着を待つ可能性があるためである。次にセクショ
ンにおいては、幾つかの貪欲さ（greediness）を導入す
ることによってプロセッサアイドル時間を低減する垂直
スケジューリング技法の修正バージョンが示される。
ルを生成するが、ひつとの明らかな短所を持つ。これは
起動されたタスクが存在するのにもかかわらず幾つかの
プロセッサがアイドル状態で他のプロセッサからのデー
タの到着を待つ可能性があるためである。次にセクショ
ンにおいては、幾つかの貪欲さ（greediness）を導入す
ることによってプロセッサアイドル時間を低減する垂直
スケジューリング技法の修正バージョンが示される。
【００７８】４．２．４ δ−貪欲Ｏ（Ｖ ｌｏｇ
Ｖ）スケジューリングスキーム この技法はセクション４．２．３において我々が考えた
のと同一の想定に基づくが、但し、我々はこのスキーム
においては貪欲要素（greedy element）を加える。貪欲
技法とδ技法は衝突するものであるために、我々はこれ
らの間の妥協をスケジューリング弾性（scheduling ela
sticity ）кの形式にて定量的に生成しなければならな
いが、次にこれについて議論する。セクション４．２．
３のステップ２（ｂ）において、我々は、ｔif＝ｍａｘ
（ｔi 、ｆp ）にセットした。このコードはυi それが
依存するタスクの完結によって起動される前（ｔi ）、
或はプロセッサがそれを実行する準備が整う前（fp）の
いずれか遅い方が起こる前に開始できないことを意味す
る。ｔi ＞ｆp ならば、プロセッサは停止する。但し、
他のタスクυj が存在し、ｔj ＜ｔi であるが、但し、
δj ＜δi 及びｎｄj ＝０である状況が考えられる。こ
のケースにおいては、我々はスラック（slack ）を低減
するためにυi の前にυj を実行することができる。図
１２は我々がυi の前にυj を挿入しようと試みたとき
発生する可能性のある４つの可能なタイミング状態を示
す。（ａ）及び（ｃ）においては、ｔj ＞ｆp であり、
従って、少しのスラックが残されるが、（ｂ）及び
（ｄ）ではυj はスラックを起こさない。（ａ）及び
（ｂ）においては、υj の挿入はυi の開始を遅延する
が、一方、（ｃ）及び（ｄ）においては、挿入されたタ
スクがυi が起動される前に終了するために、遅延は起
こらない。タスクυj を挿入するか否かを決定するのに
使用される技法はкに依存し、このため、条件
Ｖ）スケジューリングスキーム この技法はセクション４．２．３において我々が考えた
のと同一の想定に基づくが、但し、我々はこのスキーム
においては貪欲要素（greedy element）を加える。貪欲
技法とδ技法は衝突するものであるために、我々はこれ
らの間の妥協をスケジューリング弾性（scheduling ela
sticity ）кの形式にて定量的に生成しなければならな
いが、次にこれについて議論する。セクション４．２．
３のステップ２（ｂ）において、我々は、ｔif＝ｍａｘ
（ｔi 、ｆp ）にセットした。このコードはυi それが
依存するタスクの完結によって起動される前（ｔi ）、
或はプロセッサがそれを実行する準備が整う前（fp）の
いずれか遅い方が起こる前に開始できないことを意味す
る。ｔi ＞ｆp ならば、プロセッサは停止する。但し、
他のタスクυj が存在し、ｔj ＜ｔi であるが、但し、
δj ＜δi 及びｎｄj ＝０である状況が考えられる。こ
のケースにおいては、我々はスラック（slack ）を低減
するためにυi の前にυj を実行することができる。図
１２は我々がυi の前にυj を挿入しようと試みたとき
発生する可能性のある４つの可能なタイミング状態を示
す。（ａ）及び（ｃ）においては、ｔj ＞ｆp であり、
従って、少しのスラックが残されるが、（ｂ）及び
（ｄ）ではυj はスラックを起こさない。（ａ）及び
（ｂ）においては、υj の挿入はυi の開始を遅延する
が、一方、（ｃ）及び（ｄ）においては、挿入されたタ
スクがυi が起動される前に終了するために、遅延は起
こらない。タスクυj を挿入するか否かを決定するのに
使用される技法はкに依存し、このため、条件
【００７９】
【数１０】
【００８０】が満たされる場合、我々はυj をυi の前
に挿入する。к≦０の場合は、挿入は許されず、この技
法は垂直スケジューリングと同一の結果を与える。к≦
１の場合は、δ−技法と貪欲技法との間に矛盾は起こら
ない。このケースにおいては、図１２の部分（ａ）及び
（ｂ）に示される挿入は許されない。к＞１の場合は、
貪欲技法とδ−に基づくスキームとの間に妥協が存在す
る。
に挿入する。к≦０の場合は、挿入は許されず、この技
法は垂直スケジューリングと同一の結果を与える。к≦
１の場合は、δ−技法と貪欲技法との間に矛盾は起こら
ない。このケースにおいては、図１２の部分（ａ）及び
（ｂ）に示される挿入は許されない。к＞１の場合は、
貪欲技法とδ−に基づくスキームとの間に妥協が存在す
る。
【００８１】この技法は、以下の手順によって置換され
るライン２（ｂ）を除いては、セクション４．２．３に
説明されたものと基本的に等しい。 １．ｔi ≦ｆp の場合、ｔif＝ｆp にセットし、リター
ンする。 ２．υs ＝υi 、スラックs ＝スラックi ＝ｔi −ｆp
にセットする。 ３．プロセッサｐ内で起動されている（ｎｄj ＝０）全
てのタスクυj に訪れ、訪れた各タスクに対して以下を
遂行する。 ａ．スラックj ＝ｍａｘ（ｔj −ｆp 、０）にセットす
る。 ｂ．（スラックj ＜スラックs ）及び（スラックj ＋ｃ
j ＜к・スラックi ）の場合は、以下を遂行する。 ｉ．スラックs ＝スラックj にセットする。 ｉｉ．υs ＝υj にセットする。 ｉｉｉ．スラックs ＝０の場合は、サーチを終了する。 ４．υs ＝υi の場合は、ｔif＝ｔi にセットし、リタ
ーンする（サーチは失敗） ５．υs をυi の前にスケジュールし、ｔif＝ｆp ＋ス
ラックs にセットする。
るライン２（ｂ）を除いては、セクション４．２．３に
説明されたものと基本的に等しい。 １．ｔi ≦ｆp の場合、ｔif＝ｆp にセットし、リター
ンする。 ２．υs ＝υi 、スラックs ＝スラックi ＝ｔi −ｆp
にセットする。 ３．プロセッサｐ内で起動されている（ｎｄj ＝０）全
てのタスクυj に訪れ、訪れた各タスクに対して以下を
遂行する。 ａ．スラックj ＝ｍａｘ（ｔj −ｆp 、０）にセットす
る。 ｂ．（スラックj ＜スラックs ）及び（スラックj ＋ｃ
j ＜к・スラックi ）の場合は、以下を遂行する。 ｉ．スラックs ＝スラックj にセットする。 ｉｉ．υs ＝υj にセットする。 ｉｉｉ．スラックs ＝０の場合は、サーチを終了する。 ４．υs ＝υi の場合は、ｔif＝ｔi にセットし、リタ
ーンする（サーチは失敗） ５．υs をυi の前にスケジュールし、ｔif＝ｆp ＋ス
ラックs にセットする。
【００８２】４．２．５ シミュレーションの結果及び
解説 セクション４．２．３において、我々は、垂直技法に対
する完結時間ｔv を計算した。同様な手順を用いてδ−
貪欲技法に対するｔ を計算することができる。Ｐをプ
ロセッサの数、Ｔを逐次実行時間とすると、我々は、垂
直及びδ−貪欲技法、並びに最適区分化（optimal part
itioning）に対するスケジューリング利用率（scheduli
ng utilization）をそれぞれηv 、η並びにηopt によ
って以下のように表わすことができる。
解説 セクション４．２．３において、我々は、垂直技法に対
する完結時間ｔv を計算した。同様な手順を用いてδ−
貪欲技法に対するｔ を計算することができる。Ｐをプ
ロセッサの数、Ｔを逐次実行時間とすると、我々は、垂
直及びδ−貪欲技法、並びに最適区分化（optimal part
itioning）に対するスケジューリング利用率（scheduli
ng utilization）をそれぞれηv 、η並びにηopt によ
って以下のように表わすことができる。
【００８３】
【数１１】
【００８４】
【数１２】
【００８５】
【数１３】
【００８６】
【数１４】
【００８７】ここで、Σj Ｃ（υj ）はロウｉを宛先と
して持つタスクυj の総実行時間を表わす。ｔopt はＬ
Ｕ分解（decomposition ）の際に実現が可能パラレル量
に対する障壁を表わし、区分化動作に起因する最小完結
時間に対応する。これはマトリックスの各ロウに対して
依存及び任意のロウを更新するために必要とされる操作
の数を決定することによって簡単に計算することができ
る。
して持つタスクυj の総実行時間を表わす。ｔopt はＬ
Ｕ分解（decomposition ）の際に実現が可能パラレル量
に対する障壁を表わし、区分化動作に起因する最小完結
時間に対応する。これはマトリックスの各ロウに対して
依存及び任意のロウを更新するために必要とされる操作
の数を決定することによって簡単に計算することができ
る。
【００８８】テーブル１は前に説明の技法を使用しての
ＬＵ分解に対するシミュレーション結果を示す。レベル
に基づくスケジューリング及び貪欲スケジューリングの
ケースについては、我々は、我々の先の研究、つまり、
Ｒ．テリチェフスキー（Telichevesky）、Ｐ．アグラワ
ル（Agrawal ）及びＪ．トロッター（Trotter ）によっ
て１９９１年９月にスペインのバルセロナで開催された
アプリケーションスペシフィックアレイプロセッサに関
する国際会議（Int.Conf. on Applications Specific A
rray Processors ）に発表の論文『多重プロセッサ上で
の回路シミュレーションマトリックスの因子化のための
効率的な区分化技法（Efficient Partitioning Schemes
for Circuit Simulation Matrix Factorization on Mu
ltiprocessors ）』に報告の結果をここでも示す。これ
ら技法間の正当な比較を達成するために、我々は、各要
素操作が１サイクルを取る非常に単純なコスト関数を使
用し、非パイプライン連結（全てのｉに対してｐi ＝
０）を想定する。
ＬＵ分解に対するシミュレーション結果を示す。レベル
に基づくスケジューリング及び貪欲スケジューリングの
ケースについては、我々は、我々の先の研究、つまり、
Ｒ．テリチェフスキー（Telichevesky）、Ｐ．アグラワ
ル（Agrawal ）及びＪ．トロッター（Trotter ）によっ
て１９９１年９月にスペインのバルセロナで開催された
アプリケーションスペシフィックアレイプロセッサに関
する国際会議（Int.Conf. on Applications Specific A
rray Processors ）に発表の論文『多重プロセッサ上で
の回路シミュレーションマトリックスの因子化のための
効率的な区分化技法（Efficient Partitioning Schemes
for Circuit Simulation Matrix Factorization on Mu
ltiprocessors ）』に報告の結果をここでも示す。これ
ら技法間の正当な比較を達成するために、我々は、各要
素操作が１サイクルを取る非常に単純なコスト関数を使
用し、非パイプライン連結（全てのｉに対してｐi ＝
０）を想定する。
【００８９】垂直スケジューリングは、殆どのケースに
おいて、生成されたコードが結果としてタスク間に多く
のスラックを与えるために、貧しい結果を与える。但
し、我々が多くのプロセッサを使用することにより最小
完結時間の境界に接近すると（このケースにおいては、
多くのスラックが存在する）、この技法は、８個以上の
プロセッサに対するｆｅｂ及びｏｍｅｇａに対してテー
ブルに示されるように、ほぼ最適な結果を生成する傾向
を示す。
おいて、生成されたコードが結果としてタスク間に多く
のスラックを与えるために、貧しい結果を与える。但
し、我々が多くのプロセッサを使用することにより最小
完結時間の境界に接近すると（このケースにおいては、
多くのスラックが存在する）、この技法は、８個以上の
プロセッサに対するｆｅｂ及びｏｍｅｇａに対してテー
ブルに示されるように、ほぼ最適な結果を生成する傾向
を示す。
【００９０】対比的に、δ−貪欲スケジューリング法は
８０％のケースにおいて、より良い結果を与える。これ
は垂直及び貪欲スキームの両方の長所を結合する。単純
な貪欲技法がδ−貪欲技法よりも良好な性能を示すのは
２つのケースにおいてのみ見られるが、これは、適度の
数のプロセッサを使用した場合のｉｉｒ１２及びｍｆｒ
に対してである。これらケースにおいては、効率が最小
スラックを持つタスクの貪欲割り当てによって支配され
るために、クリティカルパスは重要な役割を果さない。
全てのケースにおいて、我々は、Кを以下に従って計算
した。
８０％のケースにおいて、より良い結果を与える。これ
は垂直及び貪欲スキームの両方の長所を結合する。単純
な貪欲技法がδ−貪欲技法よりも良好な性能を示すのは
２つのケースにおいてのみ見られるが、これは、適度の
数のプロセッサを使用した場合のｉｉｒ１２及びｍｆｒ
に対してである。これらケースにおいては、効率が最小
スラックを持つタスクの貪欲割り当てによって支配され
るために、クリティカルパスは重要な役割を果さない。
全てのケースにおいて、我々は、Кを以下に従って計算
した。
【００９１】
【数１５】
【００９２】Ｐが増加すると、我々は、より多くの利用
可能なスラックを持ち、従って、垂直順位の変更の可能
性はあまり許されなくなる。総コストとクリティカルパ
スのサイズとの間の比が増加すると、垂直順位にあまり
注意が払われなくなり、そして挿入のチャンスが増大す
る。
可能なスラックを持ち、従って、垂直順位の変更の可能
性はあまり許されなくなる。総コストとクリティカルパ
スのサイズとの間の比が増加すると、垂直順位にあまり
注意が払われなくなり、そして挿入のチャンスが増大す
る。
【００９３】本セクションにおいて示された結果は異な
る技法の比較のためには有益である。但し、これらが表
わすコスト関数は現実的でない。次のセクションにおい
ては、我々は、高バンド幅網を通じて接続された最新の
マイクロプロセッサの性能を比較するために現実的なコ
スト関数を伴う複数のシミュレーションの結果を提出す
る。
る技法の比較のためには有益である。但し、これらが表
わすコスト関数は現実的でない。次のセクションにおい
ては、我々は、高バンド幅網を通じて接続された最新の
マイクロプロセッサの性能を比較するために現実的なコ
スト関数を伴う複数のシミュレーションの結果を提出す
る。
【００９４】４．３ アーキテクチャの評価 プロセッサが高速バスを通じて接続される場合は、我々
のタスクグラフの単純な修正によってこのシミュレーシ
ョンを行なうことができる。最初に、我々は、バスのス
ループットが正規化されたパイプラインと同一であると
いう前提の下で正規化に穏やかに依存する同報通信タス
クＢｉを加える。次に、我々は、更新の依存を変える。
つまり、適当なソースのロウ正規化への依存が適当なソ
ースのロウ同報通信への依存と置換される。最後に、我
々は問題のロウに割れ当てられたプロセッサがバスを使
用してロウを同報通信するようにする。このモデルの使
用には複数の長所が存在する。第一に、これは一般タス
クモデルと一貫する。従って、任意のスケジューリング
技法を修正することなく実行することができる。第二
に、バストランザクションを、これらが他のタスクと同
様に残り完結時間に関する情報を持つため、これらの重
要性に従って自動的にスケジュールすることができる。
最後に、システムが注意深く設計された場合、我々はバ
スをパイプラインデバイスとして使用し、複雑なバッフ
ァリングスキーム及びこれらがシステム内に導入するオ
ーバヘッドを回避することができる。この概念をより良
く理解するために、図１５に示されるタイミング図を考
察する。プロセッサｐ1 が正規化Ｎｉを実行しており、
一方、プロセッサｐ2 がロウ更新ｉ→ｊを遂行するため
にＮｉによって生成されるデータを必要とするものと想
定する。これらタスクがクリティカルである場合は、バ
スをこれら２つのタスク間のパイプとして動作するよう
にスケジュールし、プロセッサｐ1 上のパイプラインか
らデータを取り出し、プロセッサｐ2 上のパイプライン
にこれを供給することができる。このモデルは我々にシ
ステムの性能に関する正しい情報を提供するのみでな
く、通信資源の利用率を向上させる。
のタスクグラフの単純な修正によってこのシミュレーシ
ョンを行なうことができる。最初に、我々は、バスのス
ループットが正規化されたパイプラインと同一であると
いう前提の下で正規化に穏やかに依存する同報通信タス
クＢｉを加える。次に、我々は、更新の依存を変える。
つまり、適当なソースのロウ正規化への依存が適当なソ
ースのロウ同報通信への依存と置換される。最後に、我
々は問題のロウに割れ当てられたプロセッサがバスを使
用してロウを同報通信するようにする。このモデルの使
用には複数の長所が存在する。第一に、これは一般タス
クモデルと一貫する。従って、任意のスケジューリング
技法を修正することなく実行することができる。第二
に、バストランザクションを、これらが他のタスクと同
様に残り完結時間に関する情報を持つため、これらの重
要性に従って自動的にスケジュールすることができる。
最後に、システムが注意深く設計された場合、我々はバ
スをパイプラインデバイスとして使用し、複雑なバッフ
ァリングスキーム及びこれらがシステム内に導入するオ
ーバヘッドを回避することができる。この概念をより良
く理解するために、図１５に示されるタイミング図を考
察する。プロセッサｐ1 が正規化Ｎｉを実行しており、
一方、プロセッサｐ2 がロウ更新ｉ→ｊを遂行するため
にＮｉによって生成されるデータを必要とするものと想
定する。これらタスクがクリティカルである場合は、バ
スをこれら２つのタスク間のパイプとして動作するよう
にスケジュールし、プロセッサｐ1 上のパイプラインか
らデータを取り出し、プロセッサｐ2 上のパイプライン
にこれを供給することができる。このモデルは我々にシ
ステムの性能に関する正しい情報を提供するのみでな
く、通信資源の利用率を向上させる。
【００９５】仮想上のアーキテクチュアの特性をこうし
てモデル化した上で、我々は、ダイナミックラムメモリ
の一部を表わすベンチマーク回路マトリックスを使用し
てこれらの性能の比較を行なった。
てモデル化した上で、我々は、ダイナミックラムメモリ
の一部を表わすベンチマーク回路マトリックスを使用し
てこれらの性能の比較を行なった。
【００９６】
【表１】
【００９７】
【表２】
【００９８】テーブル２は異なるハードウエア構成に対
する結果をミリ秒にて示す。ｉ８６０は４０Ｍｈｚにて
ランするインテルｉ８６０にて構築されたシステムを表
わす。Ｗg 及びＷs は２０Ｍｈｚにてランするウエイテ
ック（Weitek）ＦＰＵ及び汎用コントローラ或は専用コ
ントローラにて構築されたシステムを表わす。Ｂg 及び
Ｂs は構築が可能な場合１００Ｍｈｚにてランするビッ
トＦＰＵ及び汎用或は専用コントローラを含むシステム
を表わす。ビット（Bit ）ＦＰＵに対しては、我々は、
チップ内に利用可能な分割ユニット（Division Unit ）
を正しくモデル化するためにスケジューリングアルゴリ
ズムを変更した。全てのケースにおいて、我々はバスを
プロセッサ内の浮動小数点パイプラインと同一のスルー
プットを持つものとしてモデル化する。比較の目的から
は、クレイＸ−ＭＰスーパーコンピュータ（Cray X-MP
Supercomputer ）上での同じマトリックスの因子化は５
９．８ｍｓを要し、一方、サン４ワークステーション
（Sun 4 Workstation ）内では１９４２０ｍｓを要す
る。ここで得られた結果は、このようなマシーンの設計
及び構築を奨励する。
する結果をミリ秒にて示す。ｉ８６０は４０Ｍｈｚにて
ランするインテルｉ８６０にて構築されたシステムを表
わす。Ｗg 及びＷs は２０Ｍｈｚにてランするウエイテ
ック（Weitek）ＦＰＵ及び汎用コントローラ或は専用コ
ントローラにて構築されたシステムを表わす。Ｂg 及び
Ｂs は構築が可能な場合１００Ｍｈｚにてランするビッ
トＦＰＵ及び汎用或は専用コントローラを含むシステム
を表わす。ビット（Bit ）ＦＰＵに対しては、我々は、
チップ内に利用可能な分割ユニット（Division Unit ）
を正しくモデル化するためにスケジューリングアルゴリ
ズムを変更した。全てのケースにおいて、我々はバスを
プロセッサ内の浮動小数点パイプラインと同一のスルー
プットを持つものとしてモデル化する。比較の目的から
は、クレイＸ−ＭＰスーパーコンピュータ（Cray X-MP
Supercomputer ）上での同じマトリックスの因子化は５
９．８ｍｓを要し、一方、サン４ワークステーション
（Sun 4 Workstation ）内では１９４２０ｍｓを要す
る。ここで得られた結果は、このようなマシーンの設計
及び構築を奨励する。
【００９９】５．一例としての問題の解決 図１の回路は図２に示されるセットの方程式にてモデル
化することができるが、これら方程式はまた図３に示さ
れるようなマトリックス形式にて表わすこともできる。
図５に示されるマトリックスのゼロ／非ゼロ構造はマト
リックスによって表わされるセットの方程式を解くため
に必要な正規化、更新及び逆方向置換タスクを決定する
ために使用される。これらタスクは多重処理システム内
の一つ以上の処理要素がこれらタスクを並列に実行でき
ることが許されるようにスケジュールされる。前述のよ
うに、これらタスクはロウレベルの操作に基づき、従っ
て、マトリックスの全ロウが対応する処理要素間で分配
される。
化することができるが、これら方程式はまた図３に示さ
れるようなマトリックス形式にて表わすこともできる。
図５に示されるマトリックスのゼロ／非ゼロ構造はマト
リックスによって表わされるセットの方程式を解くため
に必要な正規化、更新及び逆方向置換タスクを決定する
ために使用される。これらタスクは多重処理システム内
の一つ以上の処理要素がこれらタスクを並列に実行でき
ることが許されるようにスケジュールされる。前述のよ
うに、これらタスクはロウレベルの操作に基づき、従っ
て、マトリックスの全ロウが対応する処理要素間で分配
される。
【０１００】この区分化は、Ｒ．テリチェフスキー（Te
lichevesky）、Ｐ．アグラワル（Agrawal ）及びＪ．ト
ロッター（Trotter ）によって１９９１年９月にスペイ
ンのバルセロナで開催されたアプリケーションスペシフ
ィックアレイプロセッサに関する国際会議（Int.Conf.
on Applications Specific Array Processors ）に発表
の論文『多重プロセッサ上での回路シミュレーションマ
トリックスの因子化のための効率的な区分化技法（Effi
cient Partitioning Schemes for Circuit Simulation
Matrix Factorization on Multiprocessors ）』におい
て教示される方法に基づく。この方法は、個々の処理要
素によって実行されるべきセットのタスクを固定する。
いったんこのタスクの区分化が行なわれると、これらタ
スクをコンピュータ上でスケジュールすることができ
る。図１３のタスクグラフにおいて、タスク間の点線は
対応する処理要素間で通信網を通じてデータ通信が起こ
るべきであることを示す。
lichevesky）、Ｐ．アグラワル（Agrawal ）及びＪ．ト
ロッター（Trotter ）によって１９９１年９月にスペイ
ンのバルセロナで開催されたアプリケーションスペシフ
ィックアレイプロセッサに関する国際会議（Int.Conf.
on Applications Specific Array Processors ）に発表
の論文『多重プロセッサ上での回路シミュレーションマ
トリックスの因子化のための効率的な区分化技法（Effi
cient Partitioning Schemes for Circuit Simulation
Matrix Factorization on Multiprocessors ）』におい
て教示される方法に基づく。この方法は、個々の処理要
素によって実行されるべきセットのタスクを固定する。
いったんこのタスクの区分化が行なわれると、これらタ
スクをコンピュータ上でスケジュールすることができ
る。図１３のタスクグラフにおいて、タスク間の点線は
対応する処理要素間で通信網を通じてデータ通信が起こ
るべきであることを示す。
【０１０１】本発明の実施例の一例においては、（”ス
ケジューラ”）は最初にタスクグラフ内の個々のタスク
にコストを割り当てる。図１３は個々のタスクに関連す
るｐ及びｃのコスト値を持つタスクグラフを示す。例え
ば、Ｎ１タスクのコストｐは、タスクＮ１の結果が１時
間ユニットの後に他のタスクによって使用が可能となる
ために１である。タスクの総コストはｐ＋ｃであり、こ
れは、図１４に示されるように関連する長方形の時間の
長さによって表わされる。これらコストに基づいて、”
最早完結時間（earliest completion time）”と呼ばれ
るメトリックδを計算することが可能である。このメト
リックは、無限量の処理資源が存在すると仮定したとき
残りのタスクグラフを計算することができる最少量の時
間を示す。δの値はグラフ内の個々のタスクに対して終
端タスク（例えば、タスクＢ２、３）から開始して、初
期タスク（例えば、タスクＮ１及びタスクＮ４）に向か
って進行する。任意のタスクに対するδの値は任意のタ
スクのコストに任意のタスクに依存するタスクの最大δ
値を加えることによって決定される。例えば、図１３に
示されるように、タスクＵ５Ｗ２に対するδはこのコス
ト（ｃ＋ｐ＝３＋０＝３）をこれに依存するタスク、つ
まり、Ｕ５Ｗ３タスクの最大δ値を加えることによって
計算される。
ケジューラ”）は最初にタスクグラフ内の個々のタスク
にコストを割り当てる。図１３は個々のタスクに関連す
るｐ及びｃのコスト値を持つタスクグラフを示す。例え
ば、Ｎ１タスクのコストｐは、タスクＮ１の結果が１時
間ユニットの後に他のタスクによって使用が可能となる
ために１である。タスクの総コストはｐ＋ｃであり、こ
れは、図１４に示されるように関連する長方形の時間の
長さによって表わされる。これらコストに基づいて、”
最早完結時間（earliest completion time）”と呼ばれ
るメトリックδを計算することが可能である。このメト
リックは、無限量の処理資源が存在すると仮定したとき
残りのタスクグラフを計算することができる最少量の時
間を示す。δの値はグラフ内の個々のタスクに対して終
端タスク（例えば、タスクＢ２、３）から開始して、初
期タスク（例えば、タスクＮ１及びタスクＮ４）に向か
って進行する。任意のタスクに対するδの値は任意のタ
スクのコストに任意のタスクに依存するタスクの最大δ
値を加えることによって決定される。例えば、図１３に
示されるように、タスクＵ５Ｗ２に対するδはこのコス
ト（ｃ＋ｐ＝３＋０＝３）をこれに依存するタスク、つ
まり、Ｕ５Ｗ３タスクの最大δ値を加えることによって
計算される。
【０１０２】タスクＮ１のδはタスクＵ２Ｗ１（δ＝１
０）、Ｕ５Ｗ１（δ＝８）、Ｂ１、４（δ＝０）及びＢ
１、２（δ＝０）に対してδの最大を取り、ここでは、
最大は１０に等しいが、これを、Ｎ１タスクのコストに
加えることによって決定することができる。Ｎ１のコス
トは、タスクＵ５Ｗ１及びＵ２Ｗ１がＮ１に穏やかに依
存するために１であり、結果として、Ｎ１に対するδと
して１１が与えられる。タスクグラフ内の全てのタスク
に対してδs が計算されたら、これらはδの値の減少順
に格納される。スケジュールが次に各処理要素上で実行
されるべきセットのタスクを取り、この処理要素に対し
て、実行されるべきタスクをδの逆順にスケジュールす
ることによって誘導される。任意のタスクの完了と、ス
ケジュールされるべき次のタスクとの間に時間がある時
は、この間に実行されるべき別のタスクをスケジュール
することを試みる。この手順が全ての処理要素上の全て
のタスクがスケジュールされるまで継続される。加え
て、通信網コントローラによって通信網上の通信の順序
付けをするために使用される通信のスケジュールが決定
される。図１４は３つのプロセッサの各々に対する実行
されるべきタスクのスケジュール及び処理要素間でデー
タを交信するために必要とされる通信のシーケンスを示
す。
０）、Ｕ５Ｗ１（δ＝８）、Ｂ１、４（δ＝０）及びＢ
１、２（δ＝０）に対してδの最大を取り、ここでは、
最大は１０に等しいが、これを、Ｎ１タスクのコストに
加えることによって決定することができる。Ｎ１のコス
トは、タスクＵ５Ｗ１及びＵ２Ｗ１がＮ１に穏やかに依
存するために１であり、結果として、Ｎ１に対するδと
して１１が与えられる。タスクグラフ内の全てのタスク
に対してδs が計算されたら、これらはδの値の減少順
に格納される。スケジュールが次に各処理要素上で実行
されるべきセットのタスクを取り、この処理要素に対し
て、実行されるべきタスクをδの逆順にスケジュールす
ることによって誘導される。任意のタスクの完了と、ス
ケジュールされるべき次のタスクとの間に時間がある時
は、この間に実行されるべき別のタスクをスケジュール
することを試みる。この手順が全ての処理要素上の全て
のタスクがスケジュールされるまで継続される。加え
て、通信網コントローラによって通信網上の通信の順序
付けをするために使用される通信のスケジュールが決定
される。図１４は３つのプロセッサの各々に対する実行
されるべきタスクのスケジュール及び処理要素間でデー
タを交信するために必要とされる通信のシーケンスを示
す。
【０１０３】各プロセッサに対していったんタスクスケ
ジュールが生成されると、方程式を解くためにコンピュ
ータが使用される。タスクのリスト及びこれらタスクを
実行するために必要とされるインストラクションがホス
トから各処理要素に送られる。マトリックスのロウがホ
ストからそのロウの操作に責務を持つ対応する処理要素
に送られる。通信網によって運ばれるべき通信のシーケ
ンスを表わすリストがホストから通信網コントローラに
送られる。
ジュールが生成されると、方程式を解くためにコンピュ
ータが使用される。タスクのリスト及びこれらタスクを
実行するために必要とされるインストラクションがホス
トから各処理要素に送られる。マトリックスのロウがホ
ストからそのロウの操作に責務を持つ対応する処理要素
に送られる。通信網によって運ばれるべき通信のシーケ
ンスを表わすリストがホストから通信網コントローラに
送られる。
【０１０４】図１４に示されるように、実行される最初
のタスクは処理要素Ｐ１（円によって表わされる）上の
Ｎ１（つまり、ロウ１の正規化）である。このタスクが
完結した後のマトリックス内の値が図１６に示される。
Ｎ１タスクの結果はＰ１によって四角によって表わされ
る処理要素Ｐ２に送られる。送信のスケジュールは通信
網コントローラによって監督されることに注意する。次
に、タスクＵ２Ｗ１はタスク１によって生成されたデー
タに依存し、このデータが入手できるようになると実行
を開始できる。タスクＵ５Ｗ１が次にＰ２上で実行され
るが、これは前にＰ１から送られたのと同じデータを使
用する。これら３つのタスクが完結した後のマトリック
スの値が図１７に示される。
のタスクは処理要素Ｐ１（円によって表わされる）上の
Ｎ１（つまり、ロウ１の正規化）である。このタスクが
完結した後のマトリックス内の値が図１６に示される。
Ｎ１タスクの結果はＰ１によって四角によって表わされ
る処理要素Ｐ２に送られる。送信のスケジュールは通信
網コントローラによって監督されることに注意する。次
に、タスクＵ２Ｗ１はタスク１によって生成されたデー
タに依存し、このデータが入手できるようになると実行
を開始できる。タスクＵ５Ｗ１が次にＰ２上で実行され
るが、これは前にＰ１から送られたのと同じデータを使
用する。これら３つのタスクが完結した後のマトリック
スの値が図１７に示される。
【０１０５】処理要素Ｐ１上で生成されたタスクＮ４か
らのデータはＰ２及びＰ３の両方によってタスクＢ２、
４、Ｂ３、４及びＵ５Ｗ４を実行するために必要とされ
ることに注意する。このケースにおいては、通信網コン
トローラによってデータが処理要素Ｐ２及びＰ３の両方
に同報通信される。終極的には、全てのタスクが完結さ
れ、処理要素のメモリは、集合として、解ベクトル（つ
まり、セットの方程式に対する解）を含む。図１８のマ
トリックスは全てのタスクが実行された後のマトリック
スを示すが、このときの解ベクトルはマトリックスの最
後のカラムにある。これはホストによってコンピュータ
から読み出される。
らのデータはＰ２及びＰ３の両方によってタスクＢ２、
４、Ｂ３、４及びＵ５Ｗ４を実行するために必要とされ
ることに注意する。このケースにおいては、通信網コン
トローラによってデータが処理要素Ｐ２及びＰ３の両方
に同報通信される。終極的には、全てのタスクが完結さ
れ、処理要素のメモリは、集合として、解ベクトル（つ
まり、セットの方程式に対する解）を含む。図１８のマ
トリックスは全てのタスクが実行された後のマトリック
スを示すが、このときの解ベクトルはマトリックスの最
後のカラムにある。これはホストによってコンピュータ
から読み出される。
【０１０６】図１８の最後のカラム内に示されるよう
に、Ｖ2 及びＶ3 に対する電圧は、それぞれ、１．９５
及び１．７７であると決定される。
に、Ｖ2 及びＶ3 に対する電圧は、それぞれ、１．９５
及び１．７７であると決定される。
【図１】本発明の一つの実施例によって分析されるべき
典型的な電気回路の略図である。
典型的な電気回路の略図である。
【図２】図１の電気回路の電気特性をモデル化するセッ
トの方程式を示す。
トの方程式を示す。
【図３】図２に示されるセットの方程式のマトリックス
表現を示す。
表現を示す。
【図４】図３に示されるマトリックスに対応する増強マ
トリックスを示す。
トリックスを示す。
【図５】図４に示される増強マトリックスのゼロ／非ゼ
ロ構造を示す。
ロ構造を示す。
【図６】図５の増強マトリックスを解くためのタスクグ
ラフを示す。
ラフを示す。
【図７】本発明の一つの実施例の概要を示す。
【図８】図７に示される処理要素の概要を示す。
【図９】図７に示される処理要素間の通信のためのメカ
ニズムを示す。
ニズムを示す。
【図１０】図８に示される通信プロセッサの通信プロセ
ッサの概要を示す。
ッサの概要を示す。
【図１１】一つの実施例によって遂行されるべきタスク
の時間的表現を示す。
の時間的表現を示す。
【図１２】タスクをタスクスケジュール内に挿入するた
めのオプションを示す。
めのオプションを示す。
【図１３】図３の増強マトリックスを解くためのタスク
グラフを示す。
グラフを示す。
【図１４】図１３のタスクグラフに対応するタスク実行
のスケジュールを示す。
のスケジュールを示す。
【図１５】一つの実施例におけるパイプラインバス動作
のタイミングを示す。
のタイミングを示す。
【図１６】最初のタスクが完結した後の図４のマトリッ
クスを示す。
クスを示す。
【図１７】３つのタスクが完結した後の図４のマトリッ
クスを示す。
クスを示す。
【図１８】図１の回路に対応する解マトリックスを示
す。
す。
７０１ ホスト ７０３ 通信網 ７０５ 通信網コントローラ ７０７ 処理要素
───────────────────────────────────────────────────── フロントページの続き (72)発明者 プラシマ アグラワル アメリカ合衆国 07974 ニュージャーシ ィ，ニュープロヴィデンス，コルチェスタ ー ロード 40 (72)発明者 リカード テリチェヴスキー アメリカ合衆国 02139 マサチューセッ ツ，カンブリッジ，ナンバー339，アルバ ニー ストリート 143 (72)発明者 ジョン エー．トロッター アメリカ合衆国 08876 ニュージャーシ ィ，サマーヴィル，アパートメント 307, ニュー ストリート 11
Claims (2)
- 【請求項１】 多重インストラクション流 −多重デー
タ流コンピュータシステムにおいて、該システムが： （１）複数の処理要素を接続するための通信手段を含
み； （２）該複数の処理要素が（ａ）セットのデータ信号、
セットのインストラクション信号及びセットの結果信号
を保持するためのメモリ、（ｂ）該セットのインストラ
クション信号に基づいて該セットのデータ信号を処理し
て該セットの結果信号を生成するための手段、及び
（ｃ）該通信手段から該セットのインストラクション信
号及び該セットのデータ信号を受信し、また通信網コン
トローラに応答して該通信手段を介して該セットの結果
信号を該処理要素の一つ或は複数に送るための通信プロ
セッサを含み； （３）該通信網コントローラが（ａ）該処理要素の各々
が該通信手段から該セットのインストラクション信号及
び該セットのデータ信号をいつ受信するかを制御するた
めの手段、及び（ｂ）該処理要素が該セットの結果を該
通信手段にいつ送るかを制御するための手段を含むこと
を特徴とするシステム。 - 【請求項２】 複数の処理要素からなる多重インストラ
クション流 −多重データ流コンピュータ上で使用され
るセットの線型方程式の操作によって表わされる物理的
現象をモデル化するための方法において、該方法が：該
セットの線型方程式の操作を複数のタスクに分解するス
テップ；該タスクを該処理要素に分配するステップ、 該タクスの各々に対して、該処理要素の一つによって該
タスクの処理に必要とされる時間の量に基づいて資源メ
トリックを計算するステップ；該タスクの各々に対し
て、該タスクの処理を終えた後該セットの線型方程式の
操作を完結するために該処理要素によって必要とされる
時間の量に基づいて完結メトリックを計算するステッ
プ；及び該タスクの各々を該資源メトリック及び完結メ
トリックに基づく順番に処理するステップを含むことを
特徴とする方法。 【０００１】
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US77517091A | 1991-10-11 | 1991-10-11 | |
| US775170 | 1991-10-11 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05216848A true JPH05216848A (ja) | 1993-08-27 |
Family
ID=25103543
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4270671A Withdrawn JPH05216848A (ja) | 1991-10-11 | 1992-10-09 | 方程式セットを解くための多重プロセッサコンピュータ |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5392429A (ja) |
| EP (1) | EP0536946A3 (ja) |
| JP (1) | JPH05216848A (ja) |
| CA (1) | CA2076293A1 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5478072A (en) * | 1993-08-10 | 1995-12-26 | Gosen Co., Ltd. | Racket string and stringed rackets using the same |
Families Citing this family (53)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5564021A (en) * | 1994-05-31 | 1996-10-08 | Us West Technologies, Inc. | Method for assigning inter-nodal traffic loads to channels in sonet rings |
| DE69230093T2 (de) * | 1991-11-19 | 2000-04-13 | International Business Machines Corp., Armonk | Multiprozessorsystem |
| US5446908A (en) * | 1992-10-21 | 1995-08-29 | The United States Of America As Represented By The Secretary Of The Navy | Method and apparatus for pre-processing inputs to parallel architecture computers |
| US5701482A (en) * | 1993-09-03 | 1997-12-23 | Hughes Aircraft Company | Modular array processor architecture having a plurality of interconnected load-balanced parallel processing nodes |
| US5519848A (en) * | 1993-11-18 | 1996-05-21 | Motorola, Inc. | Method of cell characterization in a distributed simulation system |
| US5963911A (en) * | 1994-03-25 | 1999-10-05 | British Telecommunications Public Limited Company | Resource allocation |
| JP3308770B2 (ja) * | 1994-07-22 | 2002-07-29 | 三菱電機株式会社 | 情報処理装置および情報処理装置における計算方法 |
| US5548798A (en) * | 1994-11-10 | 1996-08-20 | Intel Corporation | Method and apparatus for solving dense systems of linear equations with an iterative method that employs partial multiplications using rank compressed SVD basis matrices of the partitioned submatrices of the coefficient matrix |
| US5768594A (en) * | 1995-07-14 | 1998-06-16 | Lucent Technologies Inc. | Methods and means for scheduling parallel processors |
| JPH0981508A (ja) * | 1995-08-31 | 1997-03-28 | Internatl Business Mach Corp <Ibm> | 通信方法及び装置 |
| US5983230A (en) * | 1995-12-18 | 1999-11-09 | Xerox Corporation | Ordered sparse accumulator and its use in efficient sparse matrix computation |
| JP2830838B2 (ja) * | 1996-05-30 | 1998-12-02 | 日本電気株式会社 | 回路分割方法および装置 |
| US6049774A (en) * | 1996-07-08 | 2000-04-11 | At&T Corp. | Machine, method and medium for dynamic optimization for resource allocation |
| US5889989A (en) * | 1996-09-16 | 1999-03-30 | The Research Foundation Of State University Of New York | Load sharing controller for optimizing monetary cost |
| US5954792A (en) * | 1996-12-30 | 1999-09-21 | Cadence Design Systems, Inc. | Method for schedule validation of embedded systems |
| US6654780B1 (en) | 1997-03-28 | 2003-11-25 | International Business Machines Corporation | System of managing processor resources in a non-dedicated computer system |
| US6282560B1 (en) * | 1997-03-28 | 2001-08-28 | International Business Machines Corporation | Managing processor resources in a non-dedicated computer system |
| JP3087696B2 (ja) * | 1997-07-25 | 2000-09-11 | 日本電気株式会社 | 分散メモリ型マルチプロセッサ・システム制御方法およびコンピュータ読み取り可能な記録媒体 |
| US7805724B1 (en) * | 1998-05-27 | 2010-09-28 | Arc International I.P., Inc. | Apparatus, method and computer program for dynamic slip control in real-time scheduling |
| US6327622B1 (en) * | 1998-09-03 | 2001-12-04 | Sun Microsystems, Inc. | Load balancing in a network environment |
| US6470368B1 (en) * | 1999-05-21 | 2002-10-22 | Sun Microsystems, Inc. | Using tiling to improve performance in a sparse symmetric direct matrix solver |
| US6397236B1 (en) * | 1999-05-21 | 2002-05-28 | Sun Microsystems, Inc. | Hybrid technique for performing a column modification operation in a sparse symmetric direct matrix solver |
| SG80035A1 (en) * | 1999-05-27 | 2001-04-17 | Inst Of Microelectronics | Viterbi decoding of punctured convolutional codes without real-time branch metric computation |
| US7337437B2 (en) * | 1999-12-01 | 2008-02-26 | International Business Machines Corporation | Compiler optimisation of source code by determination and utilization of the equivalence of algebraic expressions in the source code |
| US7010788B1 (en) * | 2000-05-19 | 2006-03-07 | Hewlett-Packard Development Company, L.P. | System for computing the optimal static schedule using the stored task execution costs with recent schedule execution costs |
| US7043510B1 (en) * | 2000-06-20 | 2006-05-09 | International Business Machines Corporation | Determining the equivalence of two sets of simultaneous linear algebraic equations |
| US8176108B2 (en) * | 2000-06-20 | 2012-05-08 | International Business Machines Corporation | Method, apparatus and computer program product for network design and analysis |
| US7010789B1 (en) * | 2000-09-29 | 2006-03-07 | International Business Machines Corporation | Independent net task identification for efficient partition and distribution |
| JP3827941B2 (ja) * | 2000-11-16 | 2006-09-27 | 株式会社日立製作所 | 連立一次方程式求解方法及びその実施装置並びにその処理プログラムを記録した記録媒体 |
| KR100836998B1 (ko) * | 2001-05-14 | 2008-06-10 | 가부시끼가이샤 얼라이드 엔지니어링 | 병렬 유한 요소법 계산 시스템 |
| US20030149962A1 (en) * | 2001-11-21 | 2003-08-07 | Willis John Christopher | Simulation of designs using programmable processors and electronically re-configurable logic arrays |
| US7328195B2 (en) | 2001-11-21 | 2008-02-05 | Ftl Systems, Inc. | Semi-automatic generation of behavior models continuous value using iterative probing of a device or existing component model |
| US6961743B2 (en) * | 2002-01-08 | 2005-11-01 | Sun Microsystems, Inc. | Method and apparatus for solving an equality constrained global optimization problem |
| GB0208329D0 (en) * | 2002-04-11 | 2002-05-22 | Univ York | Data processing particularly in communication systems |
| US7065545B2 (en) * | 2002-05-07 | 2006-06-20 | Quintero-De-La-Garza Raul Gera | Computer methods of vector operation for reducing computation time |
| EP1376380A1 (en) * | 2002-06-14 | 2004-01-02 | EADS Deutschland GmbH | Procedure for computing the Choleski decomposition in a parallel multiprocessor system |
| US7089275B2 (en) * | 2003-01-29 | 2006-08-08 | Sun Microsystems, Inc. | Block-partitioned technique for solving a system of linear equations represented by a matrix with static and dynamic entries |
| US20040249616A1 (en) * | 2003-04-16 | 2004-12-09 | Vierus Stephanie A. | Resource modeler system and method |
| US7171544B2 (en) * | 2003-12-15 | 2007-01-30 | International Business Machines Corporation | Run-time parallelization of loops in computer programs by access patterns |
| JP2006085619A (ja) * | 2004-09-17 | 2006-03-30 | Fujitsu Ltd | 帯係数行列を持つ連立１次方程式の解法プログラム |
| US20060167836A1 (en) * | 2005-01-24 | 2006-07-27 | International Business Machines Corporation | Method and structure for algorithmic overlap in parallel processing for exploitation when load imbalance is dynamic and predictable |
| US20070255778A1 (en) * | 2006-04-27 | 2007-11-01 | Jean-Paul Theis | Software method for solving systems of linear equations having integer variables |
| US8711146B1 (en) * | 2006-11-29 | 2014-04-29 | Carnegie Mellon University | Method and apparatuses for solving weighted planar graphs |
| US7917876B1 (en) | 2007-03-27 | 2011-03-29 | Xilinx, Inc. | Method and apparatus for designing an embedded system for a programmable logic device |
| US7991909B1 (en) * | 2007-03-27 | 2011-08-02 | Xilinx, Inc. | Method and apparatus for communication between a processor and processing elements in an integrated circuit |
| US20080250008A1 (en) * | 2007-04-04 | 2008-10-09 | Microsoft Corporation | Query Specialization |
| US8166479B2 (en) | 2007-06-26 | 2012-04-24 | Softlife Projects Limited As Applied Cytometry Systems | Optimizing data analysis through directional dependencies of a graph including plurality of nodes and attributing threading models and setting status to each of the nodes |
| US8204925B2 (en) * | 2008-05-22 | 2012-06-19 | National Instruments Corporation | Controlling or analyzing a process by solving a system of linear equations in real-time |
| US8417755B1 (en) | 2008-05-28 | 2013-04-09 | Michael F. Zimmer | Systems and methods for reducing memory traffic and power consumption in a processing environment by solving a system of linear equations |
| US9128763B2 (en) * | 2011-08-23 | 2015-09-08 | Infosys Limited | System and method for job scheduling optimization |
| US9779374B2 (en) * | 2013-09-25 | 2017-10-03 | Sap Se | System and method for task assignment in workflows |
| CN112799603B (zh) * | 2021-03-02 | 2024-05-14 | 王希敏 | 多数据流驱动的信号处理系统的任务行为模型 |
| CN117574148A (zh) * | 2023-11-20 | 2024-02-20 | 国网冀北电力有限公司信息通信分公司 | 智能预测模型的训练方法、预测方法及相关设备 |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3648253A (en) * | 1969-12-10 | 1972-03-07 | Ibm | Program scheduler for processing systems |
| US4318173A (en) * | 1980-02-05 | 1982-03-02 | The Bendix Corporation | Scheduler for a multiple computer system |
| US4814973A (en) * | 1983-05-31 | 1989-03-21 | Hillis W Daniel | Parallel processor |
| US4642756A (en) * | 1985-03-15 | 1987-02-10 | S & H Computer Systems, Inc. | Method and apparatus for scheduling the execution of multiple processing tasks in a computer system |
| US5012409A (en) * | 1988-03-10 | 1991-04-30 | Fletcher Mitchell S | Operating system for a multi-tasking operating environment |
| US5210872A (en) * | 1991-06-28 | 1993-05-11 | Texas Instruments Inc. | Critical task scheduling for real-time systems |
-
1992
- 1992-08-18 CA CA002076293A patent/CA2076293A1/en not_active Abandoned
- 1992-10-01 EP EP19920308946 patent/EP0536946A3/en not_active Withdrawn
- 1992-10-09 JP JP4270671A patent/JPH05216848A/ja not_active Withdrawn
-
1993
- 1993-07-28 US US08/098,660 patent/US5392429A/en not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5478072A (en) * | 1993-08-10 | 1995-12-26 | Gosen Co., Ltd. | Racket string and stringed rackets using the same |
Also Published As
| Publication number | Publication date |
|---|---|
| US5392429A (en) | 1995-02-21 |
| EP0536946A2 (en) | 1993-04-14 |
| CA2076293A1 (en) | 1993-04-12 |
| EP0536946A3 (en) | 1994-09-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5392429A (en) | Method of operating a multiprocessor computer to solve a set of simultaneous equations | |
| US10579390B2 (en) | Execution of data-parallel programs on coarse-grained reconfigurable architecture hardware | |
| Rodrigue | Parallel computations | |
| US9558306B2 (en) | Retiming a design for efficient parallel simulation | |
| Kapre et al. | Accelerating SPICE model-evaluation using FPGAs | |
| Askew et al. | Monte Carlo simulation on transputer arrays | |
| Burleson et al. | The spring scheduling co-processor: A scheduling accelerator | |
| Bernhard | Computers: Computing at the speed limit: Computers 1000 times faster than today's supercomputers would benefit vital scientific applications | |
| Page et al. | Scalability of sparse matrix dense vector multiply (SpMV) on a migrating thread architecture | |
| Kumar et al. | Performance evaluation of highly concurrent computers by deterministic simulation | |
| Raghavan et al. | Logic simulation on vector processors | |
| Wang et al. | Casta: Cuda-accelerated static timing analysis for VLSI designs | |
| JP2003503800A (ja) | ロジック・イベント・シミュレーション | |
| CN110008436A (zh) | 基于数据流架构的快速傅里叶变换方法、系统和存储介质 | |
| Wu et al. | Parallelizing sparse LU decomposition on FPGAs | |
| Chen et al. | Parallel circuit simulation on multi/many-core systems | |
| Fellman | Design issues and an architecture for the monolithic implementation of a parallel digital signal processor | |
| Styles et al. | Exploiting program branch probabilities in hardware compilation | |
| Kormicki et al. | Parallel logic simulation on a network of workstations using parallel virtual machine | |
| Kumar et al. | Parallelization of PageRank on multicore processors | |
| Korch et al. | Implementation and optimization of a 1D2V PIC method for nonlinear kinetic models on GPUs | |
| Robertson et al. | Simulation of the mc88000 microprocessor system on a transputer network | |
| Li et al. | Gamify Stencil Dwarf on Cloud for Democratizing Scientific Computing | |
| Chen et al. | Parallel construction algorithms for BDDs | |
| Zhou et al. | NUMA-aware parallel sparse LU factorization for SPICE-based circuit simulators on ARM multi-core processors |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20000104 |