JPH0721144A - 多重プロセッサアーキテクチャにおけるプログラム自動展開方法 - Google Patents

多重プロセッサアーキテクチャにおけるプログラム自動展開方法

Info

Publication number
JPH0721144A
JPH0721144A JP6073505A JP7350594A JPH0721144A JP H0721144 A JPH0721144 A JP H0721144A JP 6073505 A JP6073505 A JP 6073505A JP 7350594 A JP7350594 A JP 7350594A JP H0721144 A JPH0721144 A JP H0721144A
Authority
JP
Japan
Prior art keywords
processor
tasks
task
allocation
physical
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.)
Pending
Application number
JP6073505A
Other languages
English (en)
Inventor
Peter D Hunt
ディー．ハント ピーター
Jon K Elliott
ケー．エリオット ジョン
Richard J Tobias
ジェイ．トビアス リチャード
Alan J Herring
ジェイ．ハーリング アラン
Craig R Morgan
アール．モーガン クライグ
John A Hiller
エー．ヒラー ジョン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Lockheed Martin Rolm Mil Spec Corp
Original Assignee
Loral Rohm Mil Spec Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Loral Rohm Mil Spec Corp filed Critical Loral Rohm Mil Spec Corp
Publication of JPH0721144A publication Critical patent/JPH0721144A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5061—Partitioning or combining of resources
    • G06F9/5066—Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Multi Processors (AREA)

Abstract

(57)【要約】 （修正有） 【目的】 様々な多重プロセッサアーキテクチャ中の複
雑な問題を有するタスクのアロケーションの改良を行な
う。 【構成】 多重プロセッサアーキテクチャ内のプロセッ
サに複雑な問題を有するタスクを展開させることを可能
にするため、問題の解決の実行に導く各タスクを事前割
り当て及び事前スケジュールする問題解決のデータフロ
ーグラフを使用し、事前割り当て及び事前スケジュール
のサブグラフ実行プログラムから得られたオブジェクト
コードが展開されるときに利用可能な資源に応じて目標
ハードウエアに展開させる。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、多重プロセッサアーキ
テクチャに関し、特に、ソフトウエア手順処理を効率よ
く並列に実行する多重プロセッサアーキテクチャにおい
てソフトウエア手順処理を自動展開する方法に関する。
【０００２】
【従来の技術】並列式プロセッサアーキテクチャ等の多
重プロセッサアーキテクチャは大量のデータにアクセス
し高速で多くの数のタスクを同時に処理するために相互
に接続した多くのプロセッサを備えている。多くの多重
プロセッサは、データアレイであるオペランドを備えた
命令を実行することができ、ペクタプロセッサ又はアレ
イプロセッサと呼ばれている。多重プロセッサの最大活
用のためには、できるだけ多くのタスクが各プロセッサ
において同時に実行されるように予めする必要がある。
更に、各タスクが実行可能にあるときには入力オペラン
ドの利用可能を確かにするために様々なタスクの相互関
係は連続的に考慮されなければならない。必要な入力デ
ータの欠落で１のプロセッサの処理が複数の他のプロセ
ッサより遅れることにより、並列処理により引き出され
る全体の利益を失わないようにタスクの処理順番は注意
して定めなければならない。
【０００３】データフローグラフ（ＤＦＧ：Data Flow
Graph）は個々の処理タスクやそれらの相互関係を視覚
的に明らかにするために科学者や技術者にしばしば利用
される。データフローグラフではエッジ（相互接続）が
データの流れを示し、ノードがデータを処理する機能や
タスクである。十分なデータがノードの各入力エッジで
利用できるときノードのファイアリングと呼ばれるタス
クの実行が起きる。入力エッジと関連して閾値と呼ばれ
るプロパティがある。データが入力エッジの各々の閾値
に一致又はそれを越えたときノードは動作する。ノード
が動作する毎にノードの各入力端からいくらかの量のデ
ータが消費される。消費されるデータ量は閾値以下であ
る。また、ノードが動作する毎にいくらかのデータが生
成され、その出力エッジに出力される。通常、このデー
タは他のノードで消費される。
【０００４】ここで使用される用語について理解を容易
にするために次に説明する。 （１）プリミティブ／タスク データフローグラフのノードによって表されるタスクや
機能がプリミティブである。プリミティブは特定のタス
クを行うために予めプログラムされた処理やプログラム
のライブラリから利用される。 （２）ノード ブリミティプの視覚的表示である。データフローグラフ
のノードはプロセッサで行なわれるが、用語としてのノ
ードはプロセッサを表しておらず、プロセッサによって
実行される特定のプリミティブである。 （３）閾値 ノードが動作する前に各入力エッジは適切に実行するタ
スクのために必要なデータアイテムを少なくと含んでい
る必要がある。閾値のパラメータはノードが動作するこ
とができる前に特定の入力エッジで必要とされるデータ
の最小量を指定する。 （４）サブグラフ実行プログラム プロセッサで順次実行する１又はそれ以上のプリミティ
ブから構成されるプログラムである。サブグラフ実行プ
ログラムは１つのプログラムとして実行し、その中のプ
リミティブタスクは所定の順番に次々実行する。 （５）アロケーション（Allocation） 余分のプロセッサ資源を利用するためにサブグラフ実行
プログラムを論理プロセッサに割り当てることによって
物理プロセッサ利用を管理する処理である。 （６）展開（Deployment） データフローグラフで定められたアルゴリズムをプロセ
ッサに並列に実行させるコードのように、多重プロセッ
サにおけるプロセッサへのオブジェクトコードの分配で
ある。 （７）事前スケジューリング（Pre-scheduling） 各プリミティブがどのくらいデータを消費及び生成する
のかに基づいてプログラムが判断する取り決め（スケジ
ューリング）方法である。
【０００５】一般に、多重プロセッサでデータフローグ
ラフを実行するためには２つの方法がある。一方の方法
は「ランタイムレディ」アセスメントマネジャーを用い
るノードを割り当てることである。他方の方法は事前ス
ケジューリングと呼ばれ、データフローグラフの実行よ
り前に各タスクのための所定のスケジュールを定めるこ
とである。
【０００６】ランタイムレディアセスメントは、データ
フローグラフのプリミティブの各入力の流れはランタイ
ムプログラムによって検出されるスケジューリング方法
である。プリミティブのための全ての入力の流れの閾値
に合致したときプリミティブは実行されるべき準備状態
にある。いくつかのプリミティブは一度に実行する準備
状態にあるかもしれない。ランタイムプログラムは準備
状態のプリミティブを見つけると何らかの順番で実行す
る。
【０００７】スケジューリングに加えて、プロセッサへ
のプリミティブの割り当ては多重プロセッサシステムで
は必要である。プリミティブの割り当てがランタイムの
間に終了しないならば、「ランタイムの意味ある量は計
算し、プロセッサ通信資源は消費される。」ランタイム
スケジューリング及び割り当てプロシージャで重要な問
題がある。第１の問題はヒックキャップ（hiccup）と呼
ばれ、プリミティブの実行列が予め設定されたリアルタ
イムの最終に達したとき起こる。第２の問題は最適な多
重プロセッサ割り当て及びスケジューリングの急速な発
見である。そのような問題はＮＰ−完全解（complete s
olution）である。
【０００８】ＮＰ−完全解は閉ざされた形式の解決を持
った問題の分類である。しかしながら、適切な解決は徹
底的なサーチによって見つけ出すことである。古典的な
ＮＰ−完全解は、セールスマンが巡回し停止点に到達し
ない中では最も有効なルートを確立することを望む巡回
するセールスマンの問題である。そのような問題は、全
ての可能性の徹底的なサーチによって解決される。最適
な解決を定めるため各サーチの繰り返しの結果のその後
の分析によって続けられる。全ての可能性の徹底的なサ
ーチは長いランタイムを必要とする。その時間は入力セ
ットのサイズに応じて指数関数的に長くなる。よって、
ランタイムレディスケジューラはかなりの計算力を必要
とし、適切なスケジューリング及びプリミティブの割り
当てに達するために内部プロセッサ通信資源の過渡の使
用を必要とする。
【０００９】ランタイムスケジューリング及び割り当て
のために述べた問題はＤＦＧを実行する前に各タスクの
スケジュールを予め定めることによって避けることがで
きる。そのような事前スケジュールはその機能の１つと
してプリミティブの事前割り当てを含んでいる。事前割
り当て及び事前スケジュールは、実行のためのオブジェ
クトコードの展開の前に最適な解決を見つけるに当たっ
て指数関数的なランタイムを招くかもしれないので、発
見的で蓋然的近似方法が用いられる。事前割り当て及び
事前スケジュールは、必要な手順処理のＤＦＧ表現を使
用して最適なものを定めるため複数の割り当て／スケジ
ュールの繰り返しを続ける各プログラマーによって慣例
的に用いられている。これは時間消費で無駄であり、多
重プロセッサへの科学問題のアプリケーションを遅らせ
る。
【００１０】近時、ソフトウエアパッケージは多重プロ
セッサでのタスクの自動スケジューリングの高いレベル
の達成を可能にするようになってきた。そのようなソフ
トウエアパッケージはトレミー（Ptolemy）というタイ
トルであり、「"トレミー：Ｃ＋＋の合成パラディムシ
ュミレーション／プロトタイピングプラットホーム",技
術カレッジ内部文書, カルホルニア大学 バークレー，
カリホルニア」に述べられている。更にソフトウエアパ
ッケージはハイパー（Hyper）と呼ばれ、それは"ハイパ
ー合成システムにおけるハードウエアマッピング及びモ
ジュール選択", Ｃ．チュー，メモランダム UCB/ERL M9
2/46,(1992), 技術カレッジ, カルホルニア大学 バー
クレー，カリホルニア」及び「"高レベル合成のアルゴ
リズム：アプローチに基づく資源利用", Ｍ．パトコン
ヤック（Potkonjak）, メルモ（Mermo） No UCB/ERL M9
2/10,(1992)技術カレッジ, カルホルニア大学 バーク
レー，カリホルニア」に記述されている。
【００１１】トレミーはＤＦＧとしてプログラムされる
べき複雑な科学問題を可能にし、ここで、プリミティブ
は存在する多重プロセッサアーキテクチャにおいてプロ
セッサに割り当てられる。ハイパーはＡＳＩＣ（Applic
ation Specific IntegratedCircuit）に１つのＤＦＧを
描くことを除きトレミーと同じである。ハイパーはアプ
リケーションを処理するディジタル信号に限定される。
両プログラム共にタスクに事前割り当て及び事前スケジ
ュールのコンセプトを使用し、知られたプロセッサ又は
集積回路アーキテクチャ中のタスクのアロケーションを
可能にする。
【００１２】
【発明が解決しようとする課題】しかしながら、それら
プログラム又は発明者に知っているその他のものも様々
な多重プロセッサアーキテクチャへの事前割り当て及び
事前スケジュールタスクのランタイムアロケーションを
可能にしない。従来技術は事前割り当て及び事前スケジ
ュールされたＤＦＧの固定のプロセッサアロケーション
への適用の可能性を制限している。
【００１３】よって、本発明の目的は、様々な多重プロ
セッサアーキテクチャ中の複雑な問題のタスクのアロケ
ーションの改良方法を提供することである。本発明の他
の目的は、論理プロセッサにおいて事前割り当て及び事
前スケジュールされ、選択した多重プロセッサアーキテ
クチャ内のプロセッサに描かせたタスクのアロケーショ
ンの改良方法を提供することである。
【００１４】
【課題を解決するための手段】本発明のプログラム自動
展開方法は、多重プロセッサアーキテクチャ内のプロセ
ッサに複雑な問題を有するるタスクを展開させることを
可能にするため、問題の解決の実行に導く各タスクを事
前割り当て及び事前スケジュールする問題解決のＤＦＧ
を使用し、多重プロセッサアーキテクチャ内の多数の物
理プロセッサに問題を備えるタスクを事前割り当て及び
事前スケジューリングし、複数の目標アーキテクチャの
いくつかに配列された前記多数の物理プロセッサに前記
タスクの割り当てを可能にする方法であって、問題を解
決するために実行されるべきタスクのデータフローグラ
フを構成するステップａと、各タスク及び前記問題の費
用値を決定するステップｂと、データ構造を備えている
論理プロセッサに前記タスクを事前割り当てするステッ
プｃと、事前割り当てされたタスクを性能基準に基づい
て事前スケジューリングするステップｄと、タスクをマ
シンコードに変換するステップｅと、各論理プロセッサ
及び前記目標多重プロセッサアーキテクチャ内に配置さ
れた前記多数の物理プロセッサに事前割り当てされたタ
スクからなる前記マシンコードを展開するステップｆと
を備え、そのステップｆの展開は、選択した目標多重プ
ロセッサアーキテクチャについてのデータと、物理プロ
セッサにおいて各論理プロセッサ及び事前割り当てされ
たタスクマシンコードをマップするため選択した目標多
重プロセッサアーキテクチャに配置された物理プロセッ
サの現利用率を示すデータとを用いることを特徴として
いる。
【００１５】
【実施例】以下、本発明の実施例を図面を参照しつつ詳
細に説明する。本発明は、多重プロセッサアーキテクチ
ャ内のプロセッサに複雑な問題からなるタスクを展開さ
せることを可能にするため、問題の解決の実行に導く各
タスクを事前割り当て及び事前スケジュールする問題解
決のＤＦＧを使用する。各タスクは論理プロセッサに割
り当てられる。論理プロセッサは起こり得る物理プロセ
ッサの機能及び性能の必要条件を定めるデータ構成であ
る。割り当てたタスクに加えて、各論理プロセッサは、
そのタスク又は論理プロセッサによって実行されるべき
タスクが選ばれた多重プロセッサアーキテクチャの物理
プロセッサで展開されるとき満たさなければならない割
り当てられた基準である。事前割り当て及び事前スケジ
ュールのタスクの展開は、物理プロセッサの現在の利用
及び相互関係を示した情報と共に、多重プロセッサアー
キテクチャの利用できる物理プロセッサのマップを用い
ることにより成し得る。
【００１６】本発明は図１に述べていることによってよ
く理解できる。ＤＦＧソフトウエアパッケージを使用す
るプログラマーは選択した問題の解決を達成する手順処
理からなる様々なタスクを示すフローグラフ１０を作成
する。そのような問題はデータアレイを含み、高並列の
多重プロセッサアーキテクチャでの問題解決に役立つ。
ＤＦＧ１０は模範的な問題の解決に用いられる複数のタ
スク／プリミティブの間の関係を示している。そのＤＦ
Ｇへのデータ入力は入力ノード１２及び１４を介してさ
れる。プリミティブＡ〜Ｆの各々が複雑さの広い範囲を
表し、各々が予め定められタスクで、また詳細な性能デ
ータ及びコードのオブジェクトファイルネームがＤＦＧ
を構築するために用いられるワークステーション等のデ
ータ処理システムのデータベースに既に存在するタスク
からなる。
【００１７】ＤＦＧ１０が一旦作成されると、プログラ
マーはノード相互接続ファイル（Node Interconnect Fi
le）１６及び目的画面位置ファイル（Object Screen Po
sitional File）１８を含むグラフデータベース１５を
作成する。ノード相互接続ファイル１６はＤＦＧ１０の
エッジ（edges）の各々の完全な記述を備え、目的画面
位置ファイル１８に関連させてＤＦＧ１０について述べ
ている。
【００１８】グラフデータベース１５は２つの付加ファ
イルを備えいている。ノード割り当てデータファイル２
０は、サブグラフ実行プログラム（ＳＥＰ）を割り当て
た論理プロセッサのリスト、そのＳＥＰの処理の間に使
用されるべき特定のプリミティブ及び相互依存プログラ
ム間の通信遅延基準を備えられる。ファイル２２はノー
ド割り当てデータファイル２０にリストされた各論理プ
ロセッサと関係するプリミティブの各々の実行の順番を
定める各ＳＥＰの事前スケジュールを含む。
【００１９】図２においては、事前割り当て及び事前ス
ケジュールの処理手順が述べられている。グラフデータ
ベース１５内のファイル１６からのノード相互接続デー
タはＳＥＰの構築を達成するようにＤＦＧ１０内のプリ
ミティブを区分けし複数の論理プロセッサにおいてそれ
らのプリミティブをマッピングする処理手順からなる事
前割り当てソフトウエアツール２４に供給される。論理
プロセッサは物理プロセッサとは区別されるべきであ
る。論理プロセッサはＤＦＧ１０からＳＥＰの実行を成
すために物理プロセッサによって行なわれる必要がある
機能を述べているだけである。それに続く展開手順処理
（図３に述べられている）の間、予め設定された必要条
件に合致しかつＳＥＰを取り込むための利用処理時間を
有する論理プロセッサに割り当てられたＳＥＰはいずれ
かの物理プロセッサにおいて展開される。
【００２０】事前割り当てツール２４は目標ハードウエ
ア性能データを含むファイル２５からの入力を受ける。
その目標ハードウエアはＤＦＧを実行するために用いら
れるべきいくつかの選択された多重プロセッサアーキテ
クチャである。選択のアーキテクチャに一致させるため
にファイル２５のデータを変換することにより事前割り
当て及び事前スケジュール動作はその選択のアーキテク
チャに一致させる。ファイル２５のデータは物理プロセ
ッサ能力及び相互接続ラインの時間遅延詳細に関して目
標ハードウエアのアーキテクチャを定める。例えば、物
理プロセッサは１以上のクロスバースイッチによって分
離される。クロスバースイッチは接続したプロセッサの
メモリバンク間の伝播遅延を与える。伝播遅延は特定さ
れ各々のプロセッサの仕様と共にあり、目標アーキテク
チャの類似をもたらす論理プロセッサの合成を可能にす
る。
【００２１】プリミティブライブラリファイル２７は目
標ハードウエアの各プリミティブを実行するために必要
なクロックサイクルの数を定めるファイル２９内のプリ
ミティブ性能データに含まれる。そのようなデータは実
際のハードウエアを基にした定数を用いて個々のタスク
及び全部の問題の費用を計算する事前割り当てツール２
４を使用可能にする。重要なことは、ファイル２５及び
２７を用いることにより事前割り当てツール２４は全く
異なる目標ハードウエア構成／性能データピクチャに応
じてＤＦＧ１０内のノードを区分けするため制御され得
ることである。
【００２２】事前割り当てはノード相互接続ファイル１
６及びプリミティブ性能ファイルからの情報を一旦受け
ると、ＳＥＰ中へＤＦＧ１０の初期区分けを形成する。
区分け／割り当て動作はＮＰ−完全解であり、組み合わ
せのサーチアルゴリズムによって達成される。それは、
事前割り当てツール２４がＳＥＰ（及びプリミティブ）
が論理プロセッサに割り当てられることを判別し、事前
スケジュールツール２６が各ＳＥＰのプリミティブの実
行の順番を指定することを思い起こさせる。
【００２３】事前割り当てツールは、問題のための全費
用値と同様にＤＦＧ１０内の各プリミティブのための費
用値を初めに計算する。問題のための全費用値は事前割
り当ての量を示す単位のない値であり、好ましくは少な
くとも次のエレメント、論理プロセッサ資源費用、スケ
ジューリングの困難性の基準及びプロセッサ間通信遅延
を含んでいる。
【００２４】論理プロセッサ資源費用値は使用された論
理プロセッサの数及び各々により消費されたクロックサ
イクルの関数である。論理プロセッサ資源費用は論理プ
ロセッサに割り当てられた各プリミティブの実行のため
に使用されたクロックサイクルの数を合計することによ
って算出される。各プリミティブのためのスケジューリ
ングの困難性は各プリミティブ毎にプリミティブがＤＦ
Ｇ内で処理できるとき可能な限り早い（ＡＳＡＰ）時間
及び可能な限り遅い（ＡＬＡＰ）時間を示す値を判別す
ることにより定められる。ＡＳＡＰ時間はプリミティブ
が与えられた問題を実行することかできる最も早い時間
である。ＡＬＡＰ時間は与えられた特定問題を実行する
ことができる最も遅い時間である。プリミティブのスラ
ック（遊び）時間はＡＳＡＰ時刻とＡＬＡＰ時間との間
であり、プリミティブが実行を開始しなければならない
間の時間の長さを定める。２つのプリミティブの間のオ
ーバラップ時間はそれらがほぼ同時に実行されるなら
ば、各スラック時間の重なりであり、２つのプリミティ
ブ間の干渉のレベルを示す。
【００２５】スケジューリングの困難性は特定のプリミ
ティブに特定の論理プロセッサを割り当てることからの
結果が、１つのプリミティブとオーバラップしている他
のプリミティブとの間のオーバラップ時間を判別するこ
とにより見つけ出される。スケジューリングの困難性は
プリミティブの各々のスラック時間の長さに応じてい
る。オーバラップのプリミティブのスラック時間が大き
くなるほど、オーバラップの量が小さいならば干渉は少
なくなる。このファンクション（関数）は次の式（１）
に示した如く算出される。
【００２６】
【数１】
【００２７】ここで、Ｌpjは論理プロセッサｊ、ＡSLは
プリミティブＡのスラック時間、ＢSLはプリミティブＢ
のスラック時間、ＯABはプリミティブＡ，Ｂのスラック
時間のオーバラップである。ＤＦＧ問題の全スケジュー
リング費用は全てのプリミティブに亘る合計である。費
用ファンクションの項はプロセッサ間の通信遅延の費用
である。プロセッサ間の通信遅延値はＡＳＡＰ時間、Ａ
ＬＡＰ時間を固持するとき相互に関係するタスクを実行
する論理プロセッサ間で調整することができるクロック
サイクルの時間遅延を示す。他のプロセッサ間の通信費
用は必要なデータを伝達するために要求される合計時間
である。
【００２８】費用ファンクションは上記の費用エレメン
ト各々の合計であり、特定の事前割り当ての動作の程度
を形成する。事前割り当てツール２４によって実行され
た動作はＳＥＰへのノード及び論理プロセッサへのＳＥ
Ｐの割り当てを見つけ出す。その割り当ては全部の問題
に対する解決のための最小費用ファンクションを与え
る。事前割り当て問題の解決は組み合わせの最適化を含
む。最初に事前割り当てが行われ、それに続いてその費
用ファンクションの計算が行われ、そして、それに続く
その他のことが行なわれる。各行為の後、割り当ての変
化方向がより良い割り当てに導かれていることを示して
いる減少した費用ファンクションにより費用ファンクシ
ョンが増加又は減少したか判別される。
【００２９】事前割り当ての動作の結果は割り当てられ
た特定のＳＥＰを有する論理プロセッサのリストにあ
る。各ＳＥＰは論理プロセッサによって実行されるべき
割り当てられたプリミティブを示す。論理プロセッサに
伴う割り当てスケジュールは例えば、処理状態が他から
の入力に応ずる論理プロセッサで動作する互いに関係す
るＳＥＰ間としての必要なプロセッサ間の通信遅延時間
を定める。
【００３０】ＤＦＧ１０に示した模範的問題において、
ノード割り当てデータファイル２０に示されたように、
事前割り当てツール２４は３つの論理プロセッサＬＰ１
〜ＬＰ３に３つのＳＥＰの割り当てをさせる。ＳＥＰ１
は論理プロセッサＬＰ１に割り当てられ、プリミティブ
Ａ，Ｂ，Ｅを使用する。ＳＥＰ２は論理プロセッサＬＰ
２で実行され、プリミティブＣ，Ｄを使用する。ＳＥＰ
３は論理プロセッサＬＰ２に割り当てられ、プリミティ
ブＦを使用する。
【００３１】初期の事前割り当てデータは、各ＳＥＰの
プリミティブの各々の実行の順番が取り決められるよう
に今、ノード割り当てファイル２０から事前スケジュー
ルツール２６へ移動される。事前スケジュールツール２
６はＤＦＧ１０内のプリミティブを位相幾何学的に分類
（ソート）することによって得られるＡＳＡＰ基準を使
用する。この動作はＤＦＧ１０内のノードのリニアリス
ト（linear list）を構築することによって達成され、
その構築は他のノードに関係がないデータ入力を有する
第１ノードと、そのリストのうちの早期のノードにだけ
関係する入力を有する中間ノードとに応じて行なわれ
る。事前スケジュールツール２６への他の入力は目標ハ
ードウエア性能データファイル２５及びプリミティブ性
能データファイル２９から供給される。
【００３２】事前スケジュールツール２６は各ＳＥＰで
用いられた各プリミティブの実行の順番を取り決めるた
めファイル２５及び２７からのデータに関連してノード
のリニアリストを使用する。よって、事前スケジュール
ツール２６は、そのリニアリストから、プリミティブＡ
がプリミティブＥより上にリストされ、またプリミティ
ブＥがプリミティブＢの下にあるかを判別することがで
きる。割り当てた事前スケジュールはＳＥＰ１がＡ，
Ｂ，Ｅの順番でプリミティブを実行することである。残
りのＳＥＰも同様にプリミティブの順番が取り決められ
る。
【００３３】利用可能な時間内において特定の論理プロ
セッサのためにプリミティブの順番が取り決められない
こと、又はあまりにも早期にいくつかのプリミティブの
順番が取り決められることは起こり得る。この問題はＤ
ＦＧ１０内の各プリミティブを優先順位を付けることに
よって解決される。リニアリストの第１のプリミティブ
に代わって高い優先順位のプリミティブが選択される。
いくつかのプリミティブの優先順位はそのプリミティブ
とＤＦＧの終了位置との間の長さを判別することによっ
て得られる。最も高い優先順位のプリミティブはＤＦＧ
の終了位置までのノードの距離を判別することにより設
定される。この優先順位の技術は、各プリミティブが物
理プロセッサに最終的に展開されるとき最も遠くのプリ
ミティブが他のプリミティブより前に実行されること常
に確実にする。事前スケジュールが一度得られると、そ
れはＳＥＰ事前スケジュールファイル２２に記憶され、
品質値はＳＥＰ事前スケジュールの性能品質を示したも
のとして算出される。品質基準の数値が用いられるが、
好ましい基準はギャップ（gap）時間である。ギャップ
時間は論理プロセッサが不動作で、タスクを終了し必要
なデータを備えて前の論理プロセッサを待っている時間
である。スケジュール品質データは個々の論理プロセッ
サ用のギャップ時間及びＤＦＧ内の全てのＳＥＰのため
の全部のギャップ時間の合計を含んで良い。
【００３４】事前割り当てツール２４は事前スケジュー
ルツール２６からのスケジュール品質データに応答して
結果としてのギャップ時間を少なくするために各論理プ
ロセッサへのタスク割り当てを変更する。この動作は、
タスク割り当て変更の有効性について判断がされるよう
にユーザに変更したギャップ時間の報告を含む。事前割
り当てツール２４及び事前スケジュールツール２６の両
方の動作は、所定の回数だけ繰り返すか又はスケジュー
ル品質データが複数の繰り返しに亘って良くなっている
ことを示す基準により決定される回数だけ繰り返して良
い。全ての繰り返しの終了においては、ノード割り当て
ファイル２０及びＳＥＰ事前スケジュールファイル２２
がＤＦＧ１０の後の最適事前割り当て及び事前スケジュ
ールを含むと推測される。
【００３５】ファイル２２の内容は各ＳＥＰ用にリスト
するソースを発生するグラフコンパイラ３０に供給され
る。図２に示した例において、ＳＥＰソースコードファ
イルはＣ言語であると仮定されている。ＳＥＰ１，２，
３の各々用のグラフコンパイラの結果のファイルは標準
のＣコンパイラ３２に供給される。コンパイラ３２は標
準コンパイラ動作に応じてＳＥＰソースファイルの各々
のために中間コードを生成する。標準リンカ３４はコン
パイラ３２からの中間コードを、プリミティブライブラ
リ２７のプリミティブオブジェクトコードファイル３６
から各プリミティブについて述べているオブジェクトコ
ードと共に受ける。リンカ３４は各ＳＥＰ１，２，３用
の実行可能なオブジェクトコードを生成し、グラフオブ
ジェクトファイル４０の中にそのオブジェクトコードを
ロードする。
【００３６】グラフオブジェクトファイル４０のグラフ
ヘッダ部分４２にはＳＥＰの制約条件がロードされる。
制約条件は相互に関係するＳＥＰのために定める。制約
条件である最大時間距離は選択された物理プロセッサ間
に存在することができ、相互に関係するＳＥＰの実行を
まだ可能にする。例えば、グラフヘッダ４２に示したよ
うに、ＳＥＰ１はＳＥＰ２を実行するプロセッサから倍
の距離より大きく離れていない論理プロセッサにおいて
実行されなければならない。グラフヘッダ部分４２は、
また各々割り当てられたＳＥＰの実行につく論理プロセ
ッサの動作性能能力の基準を各ＳＥＰについて有してい
る。
【００３７】ＳＥＰの制約条件、利用率及びＳＥＰオブ
ジェクトコードファイルは、目標多重プロセッサアーキ
テクチャ５４内の複数の物理プロセッサにおけるオブジ
ェクトコードの展開動作において制御プロセッサ５０
（図３に示す）によって用いられる。制御プロセッサ５
０はグラフヘッダファイル４２からのデータ及びＳＥＰ
１，２，３用のオブジェクトコードファイルの各々のデ
ータにアクセスする。グラフヘッダファイル４２内のデ
ータは制御プロセッサ５０内のランタイムグラフアロケ
ーション手順処理部５６に供給される。また、制御プロ
セッサ５０は各物理プロセッサの利用率と共に多重プロ
セッサアーキテクチャ５４内の全ての物理プロセッサ５
２の利用率を記録するファイル５８を含む。ランタイム
グラフ管理手順処理部６０は多重プロセッサアーキテク
チャ５４内の複数の物理プロセッサのうちの選択した１
つにＳＥＰ１，２，３のオブジェクトコード表の各々を
展開するランタイムグラフアロケーション手順処理部５
６を制御する。
【００３８】各論理プロセッサ及びそれと関連するＳＥ
Ｐはランタイムグラフアロケーション手順処理部５６に
よってアクセスされる。制約条件及び利用率を含むＳＥ
Ｐは多重プロセッサアーキテクチャ５４内の使用可能な
物理プロセッサ５２に対し比較され、特定の論理プロセ
ッサのＳＥＰが割り当てられるべきである物理プロセッ
サについて判別される。物理プロセッサがＳＥＰのプロ
セッサ利用率必要条件が合致する使用可能な処理容量を
有し、また相互接続のＳＥＰ（そこには時間距離制約条
件が存在する）を実行する他の物理プロセッサについて
物理的に位置させている限り、選択された物理プロセッ
サに対しＳＥＰの展開をなすことができる。もし様々な
ＳＥＰの全ての資源要求が多重プロセッサアーキテクチ
ャ５４内の物理プロセッサによって満たされるならば、
ランタイムグラフアロケーション手順処理部５６はロー
ドしたオブジェクトコードのランタイム実行を生成し、
オブジェクトコードがロードされている各物理プロセッ
サ（グラフ外部入力列を含む）に入力データが供給され
るようにする。
【００３９】上記の記述は本発明の１つの実施例を示し
てに過ぎない。本発明から外れることなく様々な他の方
法や変更がこの分野の当業者には考えることができる。
よって、本発明はそのような他の方法、変更及び付加ク
レームの範囲内の変化を含んでいる。
【００４０】
【発明の効果】上記のことから、複雑な処理のＤＦＧ表
現は事前ロードの目標ハードウエア性能データに基づい
て複数の論理プロセッサに事前割り当て及び事前スケジ
ュールをされることが理解できる。そして、事前割り当
て及び事前スケジュールのＳＥＰから得られたオブジェ
クトコードが展開されるときには、利用可能な資源に応
じて目標ハードウエアに展開させることができる。異な
る多重プロセッサアーキテクチャの性能を表す時間デー
タ（実行時間、データ相互接続時間）を事前割り当て及
び事前スケジュールの各ツールに供給することによって
上記した手順処理が続けられ、ソフトウエアツールに変
更なく様々な多重プロセッサアーキテクチャに展開され
るべきことを元々のＤＦＧに可能にするのである。
【図面の簡単な説明】
【図１】本発明の方法の動作のためにメインデータベー
スを備えるグラフデータベースに供給するＤＦＧを示す
図である。
【図２】割り当て及びスケジュールされたＳＥＰのオブ
ジェクトコードへの変換を含む事前割り当て及び事前ス
ケジューリング機能を示す図である。
【図３】割り当てられたＳＥＰを有する論理プロセッサ
が多重プロセッサアーキテクチャ内の物理プロセッサに
展開される手順処理を示す図である。
【主要部分の符号の説明】
１０ ＤＦＧ ２４ 事前割り当てツール ２６ 事前スケジュールツール ２７ プリミティブライブラリ ４０ グラフオブジェクトファイル ４２ グラフヘッダファイル ５０ 制御プロセッサ ５２ 物理プロセッサ ５４ 多重プロセッサアーキテクチャ
フロントページの続き (72)発明者 ジョン ケー．エリオット アメリカ合衆国 カリフォルニア州 94566プリーサントン ドローズ コート 450 (72)発明者 リチャード ジェイ．トビアス アメリカ合衆国 カリフォルニア州 95120サン ジョセ クイーンズブリッジ ウェイ 1123 (72)発明者 アラン ジェイ．ハーリング アメリカ合衆国 カリフォルニア州 95125サン ジョセ ジェラルド ウェイ 2668 (72)発明者 クライグ アール．モーガン アメリカ合衆国 カリフォルニア州 95133サン ジョセ ケープ タウン プ レース 839 (72)発明者 ジョン エー．ヒラー アメリカ合衆国 カリフォルニア州 94306パロ アルト ラモナ ストリート 2699

Claims (11)

    【特許請求の範囲】
  1. 【請求項１】 多重プロセッサアーキテクチャ内の多数
    の物理プロセッサに問題を備えるタスクを事前割り当て
    及び事前スケジューリングし、複数の目標アーキテクチ
    ャのいくつかに配列された前記多数の物理プロセッサに
    前記タスクの割り当てを可能にする方法であって、 前記問題を解決するために実行されるべきタスクのデー
    タフローグラフを構成するステップａと、 各タスク及び前記問題の費用値を決定するステップｂ
    と、 データ構造を備えている論理プロセッサに前記タスクを
    事前割り当てするステップｃと、 前記事前割り当てされたタスクを性能基準に基づいて事
    前スケジューリングするステップｄと、 前記タスクをマシンコードに変換するステップｅと、 各論理プロセッサ及び前記目標多重プロセッサアーキテ
    クチャ内に配置された前記多数の物理プロセッサに事前
    割り当てされたタスクからなる前記マシンコードを展開
    するステップｆとを備え、 そのステップｆの展開は、前記選択した目標多重プロセ
    ッサアーキテクチャについてのデータと、前記物理プロ
    セッサにおいて各前記論理プロセッサ及び事前割り当て
    されたタスクマシンコードをマップするため前記選択し
    た目標多重プロセッサアーキテクチャに配置された前記
    物理プロセッサの現利用率を示すデータとを用いること
    を特徴とするプログラム自動展開方法。
  2. 【請求項２】 前記ステップｂにおいて決定される前記
    費用値は各タスク及び前記問題のための実行時間に関係
    した要因を含むことを特徴とする請求項１記載の方法。
  3. 【請求項３】 前記ステップｃの事前割り当ては相互に
    関係するタスクが割り当てられる論理プロセッサのため
    にプロセッサ間の通信遅延基準を決定し、前記事前割り
    当ては問題を備えた全てのタスクのために最小費用値を
    達成すべく行なうことを特徴とする請求項２記載の方
    法。
  4. 【請求項４】 前記ステップｆの前記展開は前記ステッ
    プｃで決定されたプロセッサ間通信遅延基準を満たすよ
    うに相互に関係するタスクを備えた論理プロセッサが前
    記物理プロセッサにおいてマップされることを特徴とす
    る請求項３記載の方法。
  5. 【請求項５】 選択された目標アーキテクチャについて
    の詳細を含むデータベースが備えられ、前記ステップｃ
    の事前割り当て及び前記ステップｄの事前スケジューリ
    ングでは無関係及び相互に関係する両方のタスクが前記
    物理プロセッサに割り当てされるべきであるかを決定す
    るに当たって前記詳細を利用することを特徴とする請求
    項１記載の方法。
  6. 【請求項６】 前記ステップｆは利用率記録を保持する
    ことにより物理プロセッサの現在の利用の決定を行な
    い、前記利用率記録は、前記論理プロセッサ及びそれの
    事前割り当てのタスクの展開のために物理プロセッサが
    活用されているかの決定に用いることを特徴とする請求
    項５記載の方法。
  7. 【請求項７】 利用可能な物理プロセッサに第１の論理
    プロセッサ及び割り当てられた第１のタスクを展開する
    ことにおいて、前記ステップｆはプロセッサ間遅延基準
    を満たす他の物理プロセッサが前記プロセッサ間遅延基
    準を必要とする第２の論理プロセッサの割り当て及び割
    り当てられた第２のタスクのために利用可能か否かを決
    定し、利用可能でない場合には前記プロセッサ間遅延基
    準を満たす物理プロセッサに第１及び第２の論理プロセ
    ッサの少なくとも１の展開を行なうことを特徴とする請
    求項６記載の方法。
  8. 【請求項８】 前記ステップｄにおいて定められた前記
    性能基準は、各タスクが可能な限り早い（ＡＳＡＰ）方
    式で実行されることであることを特徴とする請求項１記
    載の方法。
  9. 【請求項９】 前記ＤＦＧの位相幾何学的ソートに基づ
    いて各タスクのためにＡＳＡＰ時間及び可能な限り遅い
    （ＡＬＡＰ）時間が設定され、前記位相幾何学的ソート
    はタスクのリニアリストを得ており、前記リニアリスト
    の各タスクは、入力を必要としない前記他のタスク及び
    前記リニアリストの前記他のタスクに続く全てのタスク
    より先に位置することを特徴とする請求項８記載の方
    法。
  10. 【請求項１０】 前記ステップａは、更に、事前スケジ
    ュールの品質基準を設定するために前記事前割り当てさ
    れたタスクの事前スケジュールを分析し、変化した事前
    割り当てとなるように前記ステップｂを繰り返し、前記
    変化した事前割り当ては前記品質基準が改善された否か
    を判別するために繰り返しの再スケジューリングステッ
    プと再スケジューリングの分析ステップとによることを
    特徴とする請求項１記載の方法。
  11. 【請求項１１】 論理プロセッサの前記品質基準は、１
    つのタスクが前記論理プロセッサで実行される前に前記
    論理プロセッサが他の論理プロセッサからの入力を待た
    なければならないギャップ時間の量であることを特徴と
    する請求項１０記載の方法。
JP6073505A 1993-04-12 1994-04-12 多重プロセッサアーキテクチャにおけるプログラム自動展開方法 Pending JPH0721144A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/046,028 US5418953A (en) 1993-04-12 1993-04-12 Method for automated deployment of a software program onto a multi-processor architecture
US08/046028 1993-04-12

Publications (1)

Publication Number Publication Date
JPH0721144A true JPH0721144A (ja) 1995-01-24

Family

ID=21941193

Family Applications (1)

Application Number Title Priority Date Filing Date
JP6073505A Pending JPH0721144A (ja) 1993-04-12 1994-04-12 多重プロセッサアーキテクチャにおけるプログラム自動展開方法

Country Status (3)

Country Link
US (1) US5418953A (ja)
EP (1) EP0624842A3 (ja)
JP (1) JPH0721144A (ja)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2004509386A (ja) * 2000-06-30 2004-03-25 タレス　ネデルラント　ベー．フェー． 複数のプロセッサにソフトウェア機能を自動的に割り当てる方法
US7331045B2 (en) 2003-08-08 2008-02-12 International Business Machines Corporation Scheduling technique for software pipelining
JP2021034020A (ja) * 2019-08-15 2021-03-01 インテル・コーポレーション ワークロードのスタティックマッピングの順不同にパイプライン化された実行を可能にする方法及び装置

Families Citing this family (90)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5522041A (en) * 1992-12-17 1996-05-28 Hitachi, Ltd. Data processor and data transfer method
US5551051A (en) * 1994-09-20 1996-08-27 Motorola, Inc. Isolated multiprocessing system having tracking circuit for verifyng only that the processor is executing set of entry instructions upon initiation of the system controller program
US5631856A (en) * 1995-01-17 1997-05-20 International Business Machines Corporation Test sequence optimization process for a circuit tester
GB2302742B (en) * 1995-06-26 2000-02-16 Sony Uk Ltd Interactive interface system
US7266725B2 (en) 2001-09-03 2007-09-04 Pact Xpp Technologies Ag Method for debugging reconfigurable architectures
US5889989A (en) * 1996-09-16 1999-03-30 The Research Foundation Of State University Of New York Load sharing controller for optimizing monetary cost
DE19651075A1 (de) 1996-12-09 1998-06-10 Pact Inf Tech Gmbh Einheit zur Verarbeitung von numerischen und logischen Operationen, zum Einsatz in Prozessoren (CPU's), Mehrrechnersystemen, Datenflußprozessoren (DFP's), digitalen Signal Prozessoren (DSP's) oder dergleichen
US6064660A (en) * 1996-12-12 2000-05-16 Optimay Corporation GSM transceiver with portable protocol stack
DE19654595A1 (de) 1996-12-20 1998-07-02 Pact Inf Tech Gmbh I0- und Speicherbussystem für DFPs sowie Bausteinen mit zwei- oder mehrdimensionaler programmierbaren Zellstrukturen
ATE243390T1 (de) 1996-12-27 2003-07-15 Pact Inf Tech Gmbh Verfahren zum selbständigen dynamischen umladen von datenflussprozessoren (dfps) sowie bausteinen mit zwei- oder mehrdimensionalen programmierbaren zellstrukturen (fpgas, dpgas, o.dgl.)
US6212576B1 (en) 1997-01-27 2001-04-03 Optimay Corporation Operating system interface for use with multitasking GSM protocol stacks
US6542998B1 (en) 1997-02-08 2003-04-01 Pact Gmbh Method of self-synchronization of configurable elements of a programmable module
US6112023A (en) * 1997-02-24 2000-08-29 Lucent Technologies Inc. Scheduling-based hardware-software co-synthesis of heterogeneous distributed embedded systems
US6230303B1 (en) 1997-02-24 2001-05-08 Lucent Technologies Inc. Proximity-based cluster allocation for hardware-software co-synthesis of heterogeneous distributed embedded systems
US6110220A (en) * 1997-02-24 2000-08-29 Lucent Technologies Inc. Concurrent hardware-software co-synthesis of hard real-time aperiodic and periodic specifications of embedded system architectures
US6117180A (en) * 1997-02-24 2000-09-12 Lucent Technologies Inc. Hardware-software co-synthesis of heterogeneous distributed embedded systems for low overhead fault tolerance
US6178542B1 (en) 1997-02-24 2001-01-23 Lucent Technologies Inc. Hardware-software co-synthesis of embedded system architectures using quality of architecture metrics
JPH1125134A (ja) * 1997-05-09 1999-01-29 Toshiba Corp 論理回路自動設計方法及びシステム並びにその自動設計処理を行うプログラムを記憶した媒体
US6023680A (en) * 1997-05-15 2000-02-08 Panasonic Technologies, Inc. Methods, apparatus and computer program products for automated visual inspection
US6366876B1 (en) * 1997-09-29 2002-04-02 Sun Microsystems, Inc. Method and apparatus for assessing compatibility between platforms and applications
US8686549B2 (en) 2001-09-03 2014-04-01 Martin Vorbach Reconfigurable elements
US5999734A (en) * 1997-10-21 1999-12-07 Ftl Systems, Inc. Compiler-oriented apparatus for parallel compilation, simulation and execution of computer programs and hardware models
DE19861088A1 (de) 1997-12-22 2000-02-10 Pact Inf Tech Gmbh Verfahren zur Reparatur von integrierten Schaltkreisen
US6256679B1 (en) * 1997-12-23 2001-07-03 Simmonds Precision Products, Inc. Blackboard-centric layered software architecture for an embedded airborne fuel gauging subsystem
US6097886A (en) * 1998-02-17 2000-08-01 Lucent Technologies Inc. Cluster-based hardware-software co-synthesis of heterogeneous distributed embedded systems
US6415384B1 (en) 1998-10-30 2002-07-02 Lucent Technologies Inc. Hardware/software co-synthesis of dynamically reconfigurable embedded systems
US7003660B2 (en) 2000-06-13 2006-02-21 Pact Xpp Technologies Ag Pipeline configuration unit protocols and communication
JP3780732B2 (ja) * 1999-03-10 2006-05-31 株式会社日立製作所 分散制御システム
FR2791789B1 (fr) * 1999-04-02 2001-08-10 Thomson Csf Procede generique d'aide au placement d'applications de traitement de signal sur calculateurs paralleles
DE10081643D2 (de) 1999-06-10 2002-05-29 Pact Inf Tech Gmbh Sequenz-Partitionierung auf Zellstrukturen
JP4475614B2 (ja) * 2000-04-28 2010-06-09 大正製薬株式会社 並列処理方法におけるジョブの割り当て方法および並列処理方法
US7876748B1 (en) 2000-09-07 2011-01-25 International Business Machines Corporation Stable hash-based mapping computation for a dynamically varying target set
AU2002220600A1 (en) * 2000-10-06 2002-04-15 Pact Informationstechnologie Gmbh Cell system with segmented intermediate cell structure
US8058899B2 (en) 2000-10-06 2011-11-15 Martin Vorbach Logic cell array and bus system
US7444531B2 (en) 2001-03-05 2008-10-28 Pact Xpp Technologies Ag Methods and devices for treating and processing data
US9037807B2 (en) 2001-03-05 2015-05-19 Pact Xpp Technologies Ag Processor arrangement on a chip including data processing, memory, and interface elements
US7844796B2 (en) 2001-03-05 2010-11-30 Martin Vorbach Data processing device and method
US7581076B2 (en) * 2001-03-05 2009-08-25 Pact Xpp Technologies Ag Methods and devices for treating and/or processing data
WO2002103532A2 (de) 2001-06-20 2002-12-27 Pact Xpp Technologies Ag Verfahren zur bearbeitung von daten
US7996827B2 (en) 2001-08-16 2011-08-09 Martin Vorbach Method for the translation of programs for reconfigurable architectures
US7434191B2 (en) 2001-09-03 2008-10-07 Pact Xpp Technologies Ag Router
US20030056091A1 (en) * 2001-09-14 2003-03-20 Greenberg Craig B. Method of scheduling in a reconfigurable hardware architecture with multiple hardware configurations
US8686475B2 (en) 2001-09-19 2014-04-01 Pact Xpp Technologies Ag Reconfigurable elements
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
US7577822B2 (en) 2001-12-14 2009-08-18 Pact Xpp Technologies Ag Parallel task operation in processor and reconfigurable coprocessor configured based on information in link list including termination information for synchronization
AU2003208266A1 (en) 2002-01-19 2003-07-30 Pact Xpp Technologies Ag Reconfigurable processor
WO2003071432A2 (de) * 2002-02-18 2003-08-28 Pact Xpp Technologies Ag Bussysteme und rekonfigurationsverfahren
US7245616B1 (en) * 2002-03-20 2007-07-17 Applied Micro Circuits Corporation Dynamic allocation of packets to tasks
US8914590B2 (en) 2002-08-07 2014-12-16 Pact Xpp Technologies Ag Data processing method and device
US7254812B1 (en) * 2002-05-31 2007-08-07 Advanced Micro Devices, Inc. Multi-processor task scheduling
US7159099B2 (en) * 2002-06-28 2007-01-02 Motorola, Inc. Streaming vector processor with reconfigurable interconnection switch
US7140019B2 (en) * 2002-06-28 2006-11-21 Motorola, Inc. Scheduler of program instructions for streaming vector processor having interconnected functional units
US7415601B2 (en) * 2002-06-28 2008-08-19 Motorola, Inc. Method and apparatus for elimination of prolog and epilog instructions in a vector processor using data validity tags and sink counters
US7657861B2 (en) 2002-08-07 2010-02-02 Pact Xpp Technologies Ag Method and device for processing data
AU2003286131A1 (en) 2002-08-07 2004-03-19 Pact Xpp Technologies Ag Method and device for processing data
WO2004038599A1 (de) 2002-09-06 2004-05-06 Pact Xpp Technologies Ag Rekonfigurierbare sequenzerstruktur
US8146063B2 (en) * 2003-02-20 2012-03-27 Koninklijke Philips Electronics N.V. Translation of a series of computer instructions
JP4700611B2 (ja) 2003-08-28 2011-06-15 ペーアーツェーテー イクスペーペー テクノロジーズ アクチエンゲゼルシャフト データ処理装置およびデータ処理方法
US7290122B2 (en) * 2003-08-29 2007-10-30 Motorola, Inc. Dataflow graph compression for power reduction in a vector processor
JP4057989B2 (ja) * 2003-09-26 2008-03-05 株式会社東芝 スケジューリング方法および情報処理システム
US7607132B2 (en) * 2004-04-08 2009-10-20 Taiwan Semiconductor Manufacturing Co., Ltd. Process scheduling system and method
US8898256B2 (en) 2004-07-13 2014-11-25 International Business Machines Corporation Prioritization of application component distribution
US8171474B2 (en) * 2004-10-01 2012-05-01 Serguei Mankovski System and method for managing, scheduling, controlling and monitoring execution of jobs by a job scheduler utilizing a publish/subscription interface
JP4405365B2 (ja) * 2004-10-27 2010-01-27 パナソニック株式会社 プログラム変換装置及び方法
EP1854024A4 (en) 2005-01-13 2008-11-05 Hsbc North America Holdings In COMPUTER SOFTWARE IMPLEMENTED FRAME FOR THE CONFIGURATION AND OUTPUT MANAGEMENT OF GROUP SYSTEM SOFTWARE AND METHOD THEREFOR
US20060195845A1 (en) * 2005-02-28 2006-08-31 Rhine Scott A System and method for scheduling executables
US20070050774A1 (en) * 2005-08-24 2007-03-01 Eldson John C Time-aware systems
US7895596B2 (en) * 2005-09-13 2011-02-22 Hewlett-Packard Development Company, L.P. Processor assignment in multi-processor systems
WO2007082730A1 (de) 2006-01-18 2007-07-26 Pact Xpp Technologies Ag Hardwaredefinitionsverfahren
US20080147221A1 (en) * 2006-12-13 2008-06-19 Garg Sukesh Grid modeling tool
KR100893527B1 (ko) 2007-02-02 2009-04-17 삼성전자주식회사 재구성 가능 멀티 프로세서 시스템에서의 매핑 및 스케줄링방법
JP4811808B2 (ja) * 2007-12-13 2011-11-09 株式会社リコー 情報処理装置、情報処理方法、プログラムおよび記録媒体
US7945768B2 (en) * 2008-06-05 2011-05-17 Motorola Mobility, Inc. Method and apparatus for nested instruction looping using implicit predicates
US8261273B2 (en) * 2008-09-02 2012-09-04 International Business Machines Corporation Assigning threads and data of computer program within processor having hardware locality groups
US8266477B2 (en) * 2009-01-09 2012-09-11 Ca, Inc. System and method for modifying execution of scripts for a job scheduler using deontic logic
US8479216B2 (en) * 2009-08-18 2013-07-02 International Business Machines Corporation Method for decentralized load distribution in an event-driven system using localized migration between physically connected nodes and load exchange protocol preventing simultaneous migration of plurality of tasks to or from a same node
US8479215B2 (en) * 2009-08-18 2013-07-02 International Business Machines Corporation Decentralized load distribution to reduce power and/or cooling costs in an event-driven system
KR101086905B1 (ko) * 2009-11-25 2011-11-24 한양대학교 산학협력단 파이프라인 멀티 코어 시스템 및 파이프라인 멀티 코어 시스템의 효과적인 태스크 할당 방법
WO2011160695A1 (en) * 2010-06-24 2011-12-29 Abb As Method and tool for automatic distribution of control code in a safety system
US20120158865A1 (en) * 2010-12-20 2012-06-21 Kixia, Inc. Managing tasks and information
EP2703918A1 (en) * 2012-09-04 2014-03-05 ABB Research Ltd. Configuration of control applications on multi-host controllers
CN103246556B (zh) * 2013-05-21 2016-10-05 中国人民解放军防空兵学院 对空监视雷达通用性能仿真方法和构架
US10191733B2 (en) * 2013-06-25 2019-01-29 Sap Se Software change process orchestration in a runtime environment
AU2017261390B2 (en) * 2016-05-06 2021-12-09 Geoquest Systems B.V. Seismic processing task predictive scheduler
US10310837B2 (en) 2016-08-25 2019-06-04 General Electric Company Method and apparatus for updating industrial assets
US10200875B2 (en) * 2017-04-17 2019-02-05 DeepSig Inc. Placement and scheduling of radio signal processing dataflow operations
US11080111B1 (en) * 2020-02-24 2021-08-03 Nvidia Corporation Technique for sharing context among multiple threads
EP4177750A1 (en) * 2021-11-04 2023-05-10 Collins Aerospace Ireland, Limited Scheduling tasks for execution by a processor system
CN115657634B (zh) * 2022-09-30 2024-06-04 重庆赛力斯凤凰智创科技有限公司 汽车软件架构、模块关联方法、计算机设备和存储介质

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5021947A (en) * 1986-03-31 1991-06-04 Hughes Aircraft Company Data-flow multiprocessor architecture with three dimensional multistage interconnection network for efficient signal and data processing
US5247675A (en) * 1991-08-09 1993-09-21 International Business Machines Corporation Preemptive and non-preemptive scheduling and execution of program threads in a multitasking operating system

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2004509386A (ja) * 2000-06-30 2004-03-25 タレス　ネデルラント　ベー．フェー． 複数のプロセッサにソフトウェア機能を自動的に割り当てる方法
US7331045B2 (en) 2003-08-08 2008-02-12 International Business Machines Corporation Scheduling technique for software pipelining
US7930688B2 (en) 2003-08-08 2011-04-19 International Business Machines Corporation Scheduling technique for software pipelining
US7962907B2 (en) 2003-08-08 2011-06-14 International Business Machines Corporation Scheduling technique for software pipelining
JP2021034020A (ja) * 2019-08-15 2021-03-01 インテル・コーポレーション ワークロードのスタティックマッピングの順不同にパイプライン化された実行を可能にする方法及び装置
US11847497B2 (en) 2019-08-15 2023-12-19 Intel Corporation Methods and apparatus to enable out-of-order pipelined execution of static mapping of a workload

Also Published As

Publication number Publication date
EP0624842A2 (en) 1994-11-17
EP0624842A3 (en) 1996-01-17
US5418953A (en) 1995-05-23

Similar Documents

Publication Publication Date Title
JPH0721144A (ja) 多重プロセッサアーキテクチャにおけるプログラム自動展開方法
CN103530187B (zh) 为多处理器系统设计程序
Park et al. Edge-centric modulo scheduling for coarse-grained reconfigurable architectures
US7107568B2 (en) System and method for reducing wire delay or congestion during synthesis of hardware solvers
Wolf An architectural co-synthesis algorithm for distributed, embedded computing systems
Hoang et al. Scheduling of DSP programs onto multiprocessors for maximum throughput
EP1138001B1 (en) Reconfigurable programmable logic device computer system
WO2000031652A9 (en) Reconfigurable programmable logic device computer system
CN115421897B (zh) 一种面向芯粒的深度神经网络流水线并行调度方法及装置
Ly et al. A generalized interconnect model for data path synthesis
Polychronopoulos Toward auto-scheduling compilers
Rosvall et al. Throughput propagation in constraint-based design space exploration for mixed-criticality systems
Mendelson et al. Mapping data flow programs on a VLSI array of processors
Xie et al. Co-synthesis with custom ASICs
US20070028198A1 (en) Method and apparatus for allocating data paths to minimize unnecessary power consumption in functional units
Rosenstiel et al. Scheduling and assignment in high level synthesis
Bringmann et al. Cross-level hierarchical high-level synthesis
Haddad Optimal Load Allocation for Parallel and Distributed Processing
Rajan Automatic synthesis of microprocessors
Zhu et al. Priority list scheduling algorithm for response time analysis optimization using dependency-driven non-critical nodes parallelism factor: Y. Zhu et al.
Hsu et al. High level synthesis in the THEDA system
Falk et al. Integrated modeling using finite state machines and dataflow graphs
Dalkiliç et al. Multi-schedule design space exploration: an alternative synthesis framework
Srivastava et al. Analysis of Power Minimization for Modified Force Directed Scheduling and Integer Linear Programming
Majumder et al. Task allocation strategies for fpga based heterogeneous system on chip