(57)【要約】  一定間隔のデータ投入を受けてパイプライン的な動作を行うバスシステムを対象とし、仕様として与えたレイテンシ制約及びスループット制約を満たすための、各回路モジュールへの実時間制約を導出するために、バスシステムの回路モジュールレベルの動作をタイムペトリネットのサブクラスで記述し、バス転送の最悪実行時間見積もりを行った後、その値を用いてタイムペトリネットを解析する。その解析においては回路モジュール間でのバスコンフリクトやリソースコンフリクトによる最大限即ち最悪と考えられる待ち時間を差し引いて、実時間制約の導出を行う。これにより、要求仕様として与えた実時間制約を満たすようバスシステムを設計する際、バスシステムを構成する各回路モジュールの実時間制約を早期に出来る限り正確に見積もることができる。
2007099590.tif 000002
【特許請求の範囲】
【請求項１】
所定間隔で順次データを入力し、バスに接続された複数の回路コンポーネントをパイプライン的に動作させるデータ処理システムの設計方法であって、
前記入力データに対する前記複数個の回路コンポーネントによる処理系統をモデル化して記述した動作シナリオを１有界のタイムペトリネットに変換する第１処理と、
前記タイムペトリネットで規定される処理系統のデータパス毎に、データ転送に要する最大時間であるバス転送総時間を見積もり、当該データパス毎のデータ入力から出力までのレイテンシ制約時間から前記バス転送総時間を減算した全処理時間に対し、各回路コンポーネントによるデータ処理量の相違に応じた重みによる加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第２処理と、
前記タイムペトリネットで規定される処理系統のデータパス毎に、前記実時間制約の総和からリソース競合よる最大アクセス待ち時間を差し引き、差し引いた全処理時間に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第３処理と、
導出された実時間制約を前記タイムペトリネットに反映して当該タイムペトリネットにおける信号遷移を検証する第４処理と、を含むデータ処理システムの設計方法。
【請求項２】
前記第３処理によって導出された実時間制約により新たなリソース競合を発生しないときの実時間制約の総和である第１総制約時間と、その一つ前の第３処理により得られた実時間制約の総和である第２総制約時間との間で、所要のレイテンシ制約を満足し且つデータパス毎の各回路コンポーネントに割り当てられるデータ処理時間の総和が最大となる補完解を線形計画法により導出し、導出された補完解の時間に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第５処理を更に含む請求項１記載のデータ処理システムの設計方法。
【請求項３】
前記導出された補完解と第１総制約時間と第２総制約時間との間において、前記レイテンシ制約を満足する最大時間解を２分探索法によって取得し、取得した時間解に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第６処理を更に含む請求項２記載のデータ処理システムの設計方法。
【請求項４】
前記第２処理におけるバス転送総時間は、バス競合がないと仮定したときのデータパス毎の回路コンポーネント間の全バス転送時間と、バス競合よるアクセス待ちに対するデータパス毎の最大の待ち時間との総和時間である請求項１記載のデータ処理システムの設計方法。
【請求項５】
固定優先度方式によるバス調停の場合には優先度から導かれる最大待ち時間を前記バス競合よるアクセス待ちに対する最大の待ち時間とする請求項４記載のデータ処理システムの設計方法。
【請求項６】
ラウンドロビン方式によるバス調停の場合にはアクセス競合無しの場合のアクセス時間とアクセス競合数との積の時間を前記第２処理におけるバス転送総時間として見積もる請求項１記載のデータ処理システムの設計方法。
【請求項７】
前記リソース競合よる最大アクセス待ち時間は、前記タイムペトリネットで規定される処理系統の別のデータパスとの間でリソース競合を起こし得る回路エレメントが最大限にリソース競合を生じたとしたときの当該リソース競合対象とされる各々の回路エレメントのために導出されている実時間制約の合計時間である請求項1記載のデータ処理システムの設計方法。
【請求項８】
前記動作シナリオは、前記処理系統を形成する前記入力データの実行系列、実行系列の選択と統合の区別、実行系列間の逐次実行と並列実行の区別、回路コンポーネント間のバス転送時間、バス転送が専用バス転送か共通バス転送かの区別を表す情報を有する請求項１記載のデータ処理システムの設計方法。
【請求項９】
前記第４処理の結果に応じて前記第３処理を繰り返す請求項１記載のデータ処理システムの設計方法。
【請求項１０】
前記第１処理は、動作シナリオの各頂点をプレースに、頂点間を結ぶ経路をトランジッションに変換し、トランジッションの間にサブネットを逆並列に挿入し、リソース競合を生ずるそれぞれのプレースに共通のサブネットを逆並列に挿入して、前記１有界のタイムペトリネットに変換する請求項９記載のデータ処理システムの設計方法。
【請求項１１】
所定間隔で順次データを入力し、バスに接続された複数の回路コンポーネントをパイプライン的に動作させる半導体集積回路の設計を支援するシステムであって、
前記入力データに対する前記複数個の回路コンポーネントによる処理系統をモデル化して記述した動作シナリオを１有界のタイムペトリネットに変換して記憶部に格納する第１動作と、
前記タイムペトリネットで規定される処理系統のデータパス毎に、データ転送に要する最大時間であるバス転送総時間を見積もり、当該データパス毎のデータ入力から出力までのレイテンシ制約時間から前記バス転送総時間を減算した全処理時間に対し、各回路コンポーネントによるデータ処理量の相違に応じた重みによる加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第２動作と、
前記タイムペトリネットで規定される処理系統のデータパス毎に、前記実時間制約の総和からリソース競合よる最大アクセス待ち時間を差し引き、差し引いた全処理時間に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第３動作と、
導出された実時間制約を前記タイムペトリネットに反映して当該タイムペトリネットにおける信号遷移を検証する第４動作と、を実行するプロセッサ部を有する設計支援装置。
【請求項１２】
前記プロセッサ部は更に、前記第３動作によって導出された実時間制約により新たなリソース競合を発生しないときの実時間制約の総和である第１総制約時間と、その一つ前の第３動作により得られた実時間制約の総和時間である第２総制約時間との間で、所要のレイテンシ制約を満足し且つデータパス毎の各回路コンポーネントに割り当てられるデータ処理時間の総和が最大となる補完解を線形計画法により導出し、導出された補完解の時間に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第５動作を実行可能である請求項１１記載の設計支援装置。
【請求項１３】
前記プロセッサ部は更に、前記導出された補完解と第１総制約時間と第２総制約時間との間において、前記レイテンシ制約を満足する最大時間解を２分探索法によって取得し、取得した時間解に対し、前記加重平均を用いて各回路コンポーネントに割り当てられるデータ処理時間を回路コンポーネント毎の実時間制約として導出する第６動作を実行可能である請求項１２記載の設計支援装置。
【請求項１４】
前記プロセッサ部は、前記第２動作におけるバス転送総時間を、バス競合がないと仮定したときのデータパス毎の回路コンポーネント間の全バス転送時間と、バス競合よるアクセス待ちに対するデータパス毎の最大の待ち時間との総和時間とする請求項１１記載の設計支援装置。
【請求項１５】
前記プロセッサ部は、固定優先度方式によるバス調停の場合には優先度から導かれる最大待ち時間を前記バス競合よるアクセス待ちに対する最大の待ち時間とする請求項１４記載の設計支援装置。
【請求項１６】
前記プロセッサ部は、ラウンドロビン方式によるバス調停の場合にはアクセス競合無しの場合のアクセス時間とアクセス競合数との積の時間を前記第２動作におけるバス転送総時間として見積もる請求項１１記載の設計支援装置。
【請求項１７】
前記リソース競合よる最大アクセス待ち時間は、前記タイムペトリネットで規定される処理系統の別のデータパスとの間でリソース競合を起こし得る回路エレメントが最大限にリソース競合を生じたとしたときの当該リソース競合対象とされる各々の回路エレメントのために導出されている実時間制約の合計時間である請求項1１記載のデータ処理システムの設計方法。
【請求項１８】
前記動作シナリオは、前記処理系統を形成する前記入力データの実行系列、実行系列の選択と統合の区別、実行系列間の逐次実行と並列実行の区別、回路コンポーネント間のバス転送時間、バス転送が専用バス転送か共通バス転送かの区別を表す情報を有する請求項１１記載の設計支援装置。
【請求項１９】
前記第４動作の結果に応じて前記第３動作を繰り返す請求項１１記載の設計支援装置。
【請求項２０】
前記第１動作は、動作シナリオの各頂点をプレースに、頂点間を結ぶ経路をトランジッションに変換し、トランジッションの間にサブネットを逆並列に挿入し、リソース競合を生ずるそれぞれのプレースに共通のサブネットを逆並列に挿入して、前記１有界のタイムペトリネットに変換する動作である請求項１９記載の設計支援装置。
【請求項２１】
所定間隔で順次データを入力し、バスに接続された複数の回路コンポーネントをパイプライン的に動作させるデータ処理装置における前記回路コンポーネントに対するデータ処理時間の割り当てを検証する方法であって、
前記入力データに対する前記複数個の回路コンポーネントによる処理系統をモデル化して記述した動作シナリオを１有界のタイムペトリネットに変換する第１処理と、
前記タイムペトリネットで規定される処理系統のデータパス毎に、当該データパス毎のデータ入力から出力までのレイテンシ制約時間から、データ転送に要する最大時間であるバス転送総時間と、リソース競合よる最大アクセス待ち時間とを差し引き、差し引いた全処理時間に対し、各回路コンポーネントによるデータ処理量の相違に応じた重みによる加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第２処理と、
導出された実時間制約を前記タイムペトリネットに反映して当該タイムペトリネットにおける信号遷移を検証する第３処理と、を含む検証方法。
【請求項２２】
前記第２処理によって導出された実時間制約により新たなリソース競合を発生しないときの実時間制約の総和である第１総制約時間と、その一つ前の第２処理により得られた実時間制約の総和である第２総制約時間との間で、所要のレイテンシ制約を満足し且つデータパス毎の各回路コンポーネントに割り当てられるデータ処理時間の総和が最大となる補完解を線形計画法により導出し、導出された補完解の時間に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第４処理を更に含む請求項２１記載の検証方法。
【請求項２３】
前記導出された補完解と第１総制約時間と第２総制約時間との間において、前記レイテンシ制約を満足する最大時間解を２分探索法によって取得し、取得した時間解に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第５処理を更に含む請求項２２記載の検証法方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は回路モジュールのような回路コンポーネントをパイプライン的に動作させるデータ処理システムのスループット制約等に基づいて個々の回路コンポーネントの処理に割り当てるべき実時間制約を導出する技術に関する。
【背景技術】
【０００２】
画像処理や音声処理等のデータ処理システムのスループット制約等に基づいて個々の回路モジュールの処理に割り当てるべき動作時間は、システム設計の一環として決定されることになる。そのようなデータ処理システムの設計では、アーキテクトが全体処理に対するスループット及びレイテンシ制約から、共通バスや専用バスに接続された各モジュールの実時間制約を勘と経験により見積もることも可能である。しかしながら、実時間制約に対して過剰な余裕を持たせれば要求性能を満たさなくなる恐れがあり、逆に余裕がなければ設計過程で実時間制約の見積もり値の変更が発生し易く、設計の手戻りが多く発生する、という問題がある。【０００３】
そのような実時間制約を自動的に導出する技術について記載された文献として以下の文献がある。非特許文献１は、シングルＣＰＵ（中央処理装置）上でバッファを介して非同期通信を行う周期タスク群を横取り可能な固定優先度スケジューラによって実行する実時間システムを対象として、入出力間の遅延、関連する入力間の時間差、および出力レートに関する実時間制約を満たし、かつＣＰＵ利用率を最小化するような、各タスクの周期やデッドラインを求めるアルゴリズムを提案する。非特許文献２は、バス上のモジュールが全て周期的に動作し、モジュール間通信がマルチランデブーのみで行われるバスシステムを対象として、レイテンシ制約から各モジュールが満たすべき実時間制約の導出手法を提案する。【０００４】
【非特許文献１】Richard Gerber, Seongsoo Hong, Manas Saksena: “Guaranteeing Real-Time Requirements with Resource-Based Calibration of Periodic Processes”, IEEE Trans. On Software Engineering, Vol. 21, No. 7, 1995.
【非特許文献２】Tomoya Kitani, Yoshifumi Takamoto, Keiichi Yasumoto, Akio Nakata, Teruo Higashino: “A Flexible and High-Reliable HW/SW Co-Design Method for Real-Time Embedded Systems”, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS2004)
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１が対象とするモデルでは、バッファによるタスク間での非同期通信が前提であり、各通信バッファに書き込み可能なタスクが一つのみに限定されているため、バス調停を伴うバスシステムをモデル化することができない。従ってバスに回路モジュールが接続されたデータ処理システム（バスシステム）を対象としてその構成回路モジュールの実時間制約を導出することは不可能である。【０００６】
非特許文献２が対象とするモデルでは、全ての回路モジュールが同一周期で動作しなければならないため、バスデータ転送中であってもデータ転送に関与しない回路モジュールがバスデータ転送とは独立に動作するようなバスシステムをモデル化する事ができない。このため、全体としてパイプライン的な動作を行いブロッキング通信（転送先コンポーネントとの処理が終了するまで転送元コンポーネントはデータ転送不可とする通信）を伴うバスシステムをモデル化する事ができない。要するに、ブロック転送を行ないながら動作する複数回路モジュールをパイプライン的に動作させるシステムをモデル化することができない。従って画像処理などのデータ処理を対象としたパイプライン的な動作を行うバスシステムを対象とした構成回路モジュールの実時間制約の導出が不可能である。【０００７】
本発明の目的はバスに接続された回路コンポーネントをパイプライン的に動作させるデータ処理システムにおける各回路コンポーネントの実時間制約を導出することができるデータ処理システムの設計方法、更にはそのような実時間制約を導出可能にする設計支援装置を提供することにある。【０００８】
本発明の別の目的は、所要の性能を有するデータ処理システムのコスト低減に則した実時間制約の導出を可能にすることができるデータ処理システムの設計方法、更にはそのような実時間制約を導出可能にする設計支援装置を提供することにある。【０００９】
本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１０】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。即ち、一定間隔のデータ投入を受けてパイプライン的な動作を行うデータ処理システムを対象とし、仕様として与えられるレイテンシ制約及びスループット制約を満たすための、データ処理システムを構成する各回路モジュールへの実時間制約を導出するために、データ処理システムの回路モジュールレベルの動作をタイムペトリネットのサブクラス（動作シナリオ）で記述し、バス転送の最悪実行時間見積もりを行った後、その値を用いてタイムペトリネットを解析する。その解析においては回路モジュール間でのバスコンフリクトやリソースコンフリクトによる最大限と考えられる即ち最悪と考えられる待ち時間を差し引いて、実時間制約の導出を行い、次いでレイテンシ制約及びスループット制約を満たす各回路モジュールへの実時間制約を出来うる限り緩和する。これにより、要求仕様として与えた実時間制約を満たすようデータ処理システムを設計する際、データ処理システムを構成する各回路モジュールの実時間制約を早期に出来る限り正確に見積もることが可能になる。【００１１】
本発明について更に詳述する。【００１２】
〔１〕所定間隔で順次データを入力し、バスに接続された複数の回路コンポーネント（Ａ，Ｂ，Ｃ，Ｄ，Ｅ）をパイプライン的に動作させるデータ処理システムの設計方法は第１処理乃至第４処理を有する。第１処理は、前記入力データに対する前記複数個の回路コンポーネントによる処理系統をモデル化して記述した動作シナリオを１有界のタイムペトリネット（１−ｓａｆｅＴＰＮ）に変換する処理である。第２処理は、前記タイムペトリネットで規定される処理系統のデータパス毎に、データ転送に要する最大時間であるバス転送総時間（Ｔ２）を見積もり、当該データパス毎のデータ入力から出力までのレイテンシ制約時間（Ｔ１）から前記バス転送総時間を減算した全処理時間（Ｔ３）に対し、各回路コンポーネントによるデータ処理量の相違に応じた重みによる加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する処理である。第３処理は、前記タイムペトリネットで規定される処理系統のデータパス毎に、前記実時間制約の総和からリソース競合よる最大アクセス待ち時間（Ａｐｓ；Ｂ１＋Ｃ１、Ｂｐｓ；Ａ１＋Ｃ１、Ｃｐｓ；Ａ１＋Ｂ１）を差し引き、差し引いた全処理時間に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する処理である。第４処理は、導出された実時間制約を前記タイムペトリネットに反映して当該タイムペトリネットにおける信号遷移を検証する処理である。【００１３】
検証対象とするデータ処理システムは動作シナリオによってモデル化される。モデル化された動作記述は１有界のタイムペトリネットに変換される。タイムペトリネットにおいては、信号遷移とみなされるトランジッションに発火時間という時間制約が付され、その時間制約に従ってトークンがモデル中を流れる。このトークンの流れの様子をシミュレーションによって検証することによって、パイプライン的な動作を行う回路モジュール群の動作の検証が可能になる。このとき、１有界とは、タイムペトリネットの各プレースに無用な複数のトークが溜まることを排除することを企図する。第２処理によりバスに接続された複数の回路コンポーネントによる処理時間と回路コンポーネント間のバス転送に要する時間を区別する。特に、所要のレイテンシ制約時間に対してデータ転送に要する最大時間を差し引いた時間（全処理時間）を回路コンポーネントによる処理時間として位置付けることにより、バスコンフリクトの問題を排除して実時間制約の見積もりを可能にする。データパス毎の各回路コンポーネントに割り当てる実時間制約の見積もりは第２処理による加重平均を用いて行なうことができる。バスコンフリクトの他に、データ経路によってはリソース競合を生ずることがある。リソース競合を生ずる虞のある回路コンポーネントが存在するときは、リソース競合による待ち時間を差し引いて実時間制約を見積もる。即ち、第３処理により、リソース競合による最大アクセス待ち時間を更に差し引いてから再度加重平均を用いて各回路コンポーネントに対する実時間制約の割当てをやり直す。この第３処理の結果に対しても第４処理にて検証を行ない、第３処理及び第４処理を繰り返すことによってリソース競合による最大待ち時間を採ったとしてもレイテンシ制約等に対して不都合を生じないために必要な各回路コンポーネントの実時間制約を得ることができる。これによって得られた実時間制約は、バスコンフリクトやリソース競合回避のために最大限若しくは最悪と考えられる時間を待ったとしても破綻することなく動作を継続するのに必要な比較的高速な動作を規定することになる。したがって、其れによって得られた実時間制約を緩和して長くしても良い場合が多いと考えられる。実時間制約の緩和は回路コンポーネントの動作速度低下を可能にし、所要の性能を維持してデータ処理システムのコスト低減に寄与する。【００１４】
これに対処するための、本発明の具体的な一つの形態として、前記第３処理によって導出された実時間制約により新たなリソース競合を発生しないとき（ｊ）の実時間制約の総和である第１総制約時間と、その一つ前（ｊ−１）の第３処理により得られた実時間制約の総和である第２総制約時間との間で、所要のレイテンシ制約を満足し且つデータパス毎の各回路コンポーネントに割り当てられるデータ処理時間の総和が最大となるような補完解を線形計画法により導出し、導出された補完解の時間に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第５処理を更に採用する。さらに、前記導出された補完解と第１総制約時間と第２総制約時間との３点の間において、前記レイテンシ制約を満足する最大時間解を２分探索法によって取得し、取得した時間解に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第６処理を採用すればよい。【００１５】
本発明の更に具体的な形態として、前記第２処理におけるバス転送総時間は、バス競合がないと仮定したときのデータパス毎の回路コンポーネント間の全バス転送時間と、バス競合よるアクセス待ちに対するデータパス毎の最大の待ち時間との総和時間である。例えば、固定優先度方式によるバス調停の場合には優先度から導かれる最大待ち時間を前記バス競合よるアクセス待ちに対する最大の待ち時間とする。【００１６】
本発明の別の一つの具体的な形態として、ラウンドロビン方式によるバス調停の場合にはアクセス競合無しの場合のアクセス時間とアクセス競合数との積の時間を前記第２処理におけるバス転送総時間として見積もればよい。【００１７】
本発明の更に別の一つの具体的な形態として、前記リソース競合よる最大アクセス待ち時間は、前記タイムペトリネットで規定される処理系統の別のデータパスとの間でリソース競合を起こし得る回路エレメントが最大限にリソース競合を生じたとしたときの当該リソース競合対象とされる各々の回路エレメントのために導出されている実時間制約の合計時間である。【００１８】
本発明の更に別の一つの具体的な形態として、前記動作シナリオは、前記処理系統を形成する前記入力データの実行系列、実行系列の選択と統合の区別、実行系列間の逐次実行と並列実行の区別、回路コンポーネント間のバス転送時間、及びバス転送が専用バス転送か共通バス転送かの区別を表す情報を有する。【００１９】
本発明の更に別の一つの具体的な形態として、前記第１処理は、動作シナリオの各頂点をプレースに、頂点間を結ぶ経路をトランジッションに変換し、トランジッションの間にサブネットを逆並列に挿入し、リソース競合を生ずるそれぞれのプレースに共通のサブネットを逆並列に挿入して、前記１有界のタイムペトリネットに変換する。【００２０】
〔２〕所定間隔で順次データを入力し、バスに接続された複数の回路コンポーネントをパイプライン的に動作させる半導体集積回路の設計を支援するシステムは第１動作乃至第４動作を実行するプロセッサ部（１０）を有する。第１動作は、前記入力データに対する前記複数個の回路コンポーネントによる処理系統をモデル化して記述した動作シナリオを１有界のタイムペトリネットに変換して記憶部に格納する動作である。第２動作は、前記タイムペトリネットで規定される処理系統のデータパス毎に、データ転送に要する最大時間であるバス転送総時間を見積もり、当該データパス毎のデータ入力から出力までのレイテンシ制約時間から前記バス転送総時間を減算した全処理時間に対し、各回路コンポーネントによるデータ処理量の相違に応じた重みによる加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する動作である。第３動作は、前記タイムペトリネットで規定される処理系統のデータパス毎に、前記実時間制約の総和からリソース競合よる最大アクセス待ち時間を差し引き、差し引いた全処理時間に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する動作である。第４動作は、導出された実時間制約を前記タイムペトリネットに反映して当該タイムペトリネットにおける信号遷移を検証する動作である。【００２１】
第３動作及び第４動作を繰り返すことによってリソース競合を生じないために必要な各回路コンポーネントに実時間制約を得ることができるが、この実時間制約を緩和するには、更に前記プロセッサ部は第５動作を実行可能であればよい。第５動作は、前記第３動作によって導出された実時間制約により新たなリソース競合を発生しないときの実時間制約の総和である第１時間と、その一つ前の第３動作により得られた実時間制約の総和時間である第２時間との間で、所要のレイテンシ制約を満足し且つデータパス毎の各回路コンポーネントに割り当てられるデータ処理時間の総和が最大となる補完解を線形計画法により導出し、導出された補完解の時間に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する動作である。【００２２】
その実時間制約を更に緩和するには、前記プロセッサ部は第６動作を実行可能であればよい。第６動作は、前記導出された補完解と第１実時間制約の総和との間において、前記レイテンシ制約を満足する最大時間解を２分探索法によって取得し、取得した時間解に対し、前記加重平均を用いて各回路コンポーネントに割り当てられるデータ処理時間を回路コンポーネント毎の実時間制約として導出する動作である。【００２３】
〔３〕所定間隔で順次データを入力し、バスに接続された複数の回路コンポーネントをパイプライン的に動作させるデータ処理装置における前記回路コンポーネントに対するデータ処理時間の割り当てを検証する方法は、第１処理乃至第３処理を含む。第１処理は、前記入力データに対する前記複数個の回路コンポーネントによる処理系統をモデル化して記述した動作シナリオを１有界のタイムペトリネットに変換する処理である。第２処理は、前記タイムペトリネットで規定される処理系統のデータパス毎に、当該データパス毎のデータ入力から出力までのレイテンシ制約時間から、データ転送に要する最大時間であるバス転送総時間と、リソース競合よる最大アクセス待ち時間とを差し引き、差し引いた全処理時間に対し、各回路コンポーネントによるデータ処理量の相違に応じた重みによる加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する処理である。第３処理は、導出された実時間制約を前記タイムペトリネットに反映して当該タイムペトリネットにおける信号遷移を検証する処理である。【００２４】
第２動作及び第３動作を繰り返すことによってリソース競合を生じないために必要な各回路コンポーネントに実時間制約を得ることができるが、この実時間制約を緩和するには、前記第２処理によって導出された実時間制約により新たなリソース競合を発生しないときの実時間制約の総和である第１時間と、その一つ前の第２処理により得られた実時間制約の総和である第２時間との間で、所要のレイテンシ制約を満足し且つデータパス毎の各回路コンポーネントに割り当てられるデータ処理時間の総和が最大となる補完解を線形計画法により導出し、導出された補完解の時間に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第４処理を更に採用すればよい。【００２５】
その実時間制約を更に緩和するには、前記導出された補完解と第１実時間制約の総和との間において、前記レイテンシ制約を満足する最大時間解を２分探索法によって取得し、取得した時間解に対し、前記加重平均を用いて各回路コンポーネントに割り当てるデータ処理時間を実時間制約として導出する第５処理を採用すればよい。
【発明の効果】
【００２６】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記の通りである。【００２７】
すなわち、バスに接続された回路コンポーネントをパイプライン的に動作させるデータ処理システムにおける各回路コンポーネントの実時間制約を導出することができる。さらに、所要の性能を有するデータ処理システムのコスト低減に則した実時間制約の導出を可能にすることができる。
【図面の簡単な説明】
【００２８】
【図１】図１は本発明に係るデータ処理システムの設計方法を適用した設計支援装置を例示するブロック図である。
【図２】図２はバスシステムの一例を示すブロック図である。
【図３】図３は図２の動作シナリオを例示する説明図である。
【図４】図４は動作シナリオの記述内容に対する時間的遷移の状態を例示する説明図である。
【図５】図５はスループットとレイテンシ制約の説明図である。
【図６】図６は動作シナリオに対応させた実時間制約を示す説明図である。
【図７】図７は図６の動作シナリオにおける要素の変換形態を例示する説明図である。
【図８】図８は図６の動作シナリオにおける要素の別の変換形態を例示する説明図である。
【図９】図９は図６の動作シナリオをＴＰＮに変換した結果を例示する説明図である。
【図１０】図１０はＴＰＮの各要素に対する１−ｓａｆｅＴＰＮへの変換形態を例示する説明図である。
【図１１】図１１はＴＰＮの各要素に対する１−ｓａｆｅＴＰＮへの別の変換形態を例示する説明図である。
【図１２】図１２はＴＰＮの各要素に対する１−ｓａｆｅＴＰＮへの更に別の変換形態を例示する説明図である。
【図１３】図１３は図９のＴＰＮを１−ｓａｆｅＴＰＮに変換した変換結果を例示する説明図である。
【図１４】図１４はリソース競合を生ずるプレースに対する１−ｓａｆｅＴＰＮへの変換要素を例示する説明図である。
【図１５】図１５は図１３の変換結果に対してリソース競合を排除するよう変換した１−ｓａｆｅＴＰＮの変換結果図である。
【図１６】図１６はバス権調停を固定優先度によって行う場合における回路モジュールのバス転送最悪時間の見積もり手法を示す説明図である。
【図１７】図１７はバス権調停を時分割ラウンドロビンで行う場合における回路モジュールのバス転送最悪時間の見積もり手法を示す説明図である。
【図１８】図１８は動作シナリオにける一つのデータパスとそのデータパスにおけるレイテンシ制約に対するバス転送見積もり時間の総和（バスタイム）の位置付けを例示する説明図である。
【図１９】図１９はリソース競合を考慮して回路モジュールの実時間制約を見積もるときの基本的な手法を示す説明図である。
【図２０】図２０はリソース競合を考慮して回路モジュールの時間制約を見積も処理を複数回繰り返したちきの実時間制約の変化を例示する説明図である。
【図２１】図２１は２分探索法より導出解を緩和する基本的な手法を示す説明図である。
【図２２】図２２はスループット制約が満たされるか否かの検証に向けて修正されたＴＰＮを１−ｓａｆｅＴＰＮの説明図である。
【図２３】図２３はスループット制約が満たされるか否かの検証に向けて修正された別のＴＰＮを１−ｓａｆｅＴＰＮの説明図である。
【図２４】図２４は本発明を適用して開発対象とするＭＰＥＧデコーダシステムのブロック図である。
【図２５】図２５は図２４のＭＰＥＧデコーダシステムによる復号機能を例示するフローチャートである。
【図２６】図２６は図２４の各回路モジュールに対する実時間性制約を導出する処理を行なうために用いた動作ナリオの具体例を示す説明図である。
【図２７】図２７は図２４の各回路モジュールの処理に応じた重みを例示する説明図である。
【図２８】図２８は２分探索法によって最終的に得られた導出解を例示する説明図である。
【符号の説明】
【００２９】
１０  プロセッサ部
１１  １有界タイムペトリネット生成部
１２  バス転送時間見積もり部
１３実時間制約導出及び緩和部
１４  ２分探索判定部
２１  バス動作シナリオの格納領域
２２  モジュール排他情報の格納領域
２３  バス調停及びバス転送情報の格納領域
２４  スループット及びレイテンシ制約の格納領域
２５  １有界タイムペトリネット（１−ｓａｆｅＴＰＮ）の格納領域
２６  回路モジュールの実時間制約の格納領域
ＥＢＵＳ  専用バス
ＣＢＵＳ  共通バス
ＳＢＮ  サブネット
【発明を実施するための最良の形態】
【００３０】
《設計支援装置》
図１には本発明に係るデータ処理システムの設計方法を適用した設計支援装置が例示される。【００３１】
設計支援装置を用いて開発対象とされるデータ処理システムは、一定間隔のデータ投入を受けてパイプライン的な動作を行うバスシステムを対象とする。ここでは特に、バスシステム全体が仕様として与えられたレイテンシ及びスループット制約を満たすための各回路モジュール（回路エレメント）の実時間制約を自動導出する構成に着目する。設計支援装置が対象とするバスシステムは、さまざまな機能モジュールがバスで接続されたバスシステムである。ただし、画像や音声などのように、入力データが一定の時間間隔で到着し、システム内のある回路モジュールがそれを受け取り、何らかの加工を行い、その結果のデータを次の回路モジュールに渡していくというようにしながら、最終的なデータを出力するまで、パイプライン的にデータを次々と受け渡していくシステムを対象とする。また，一つの回路モジュールの実行終了後には必ず他の回路モジュールへのデータ転送があるものとする。そのとき、回路モジュール間が専用バスで接続されていればそれを用い、さもなければ、共有バスを用いてデータ転送を行うと仮定する。さらに、データ転送はブロッキング転送、すなわち、転送先モジュールの処理が終了していなければ、終了までデータ送信は待たされるものとする。【００３２】
設計支援装置は、例えばデータ処理システムの設計方法を実現するための設計支援プログラムを保有するエンジニアリングワークステーション等によって構成される。設計支援装置はプロセッサ部１０と記憶部に大別される。プロセッサ部１０は前記プログラムを実行しながら記憶部に格納されたパラメータや制御データを用いて実時間制約を導出するための演算処理を行なう。図１には記憶部として、動作シナリオ（バス動作シナリオ）、モジュール排他情報、バス調停及びバス転送情報、スループット及びレイテンシ制約、１有界タイムペトリネット（１−ｓａｆｅＴＰＮ）、並びに回路モジュールの実時間制約について、各情報を格納する領域２１〜２６が代表的に示される。プロセッサ部１０は１有界タイムペトリネット生成部１１、バス転送時間見積もり部１２、実時間制約導出及び緩和部１３及び２分探索判定部１４を有する。【００３３】
《動作シナリオ》
前記領域２１に格納される動作シナリオは、一つの入力に対するデータパスに配置された回路モジュールによるデータの実行系列（回路モジュールの動作実行系列）、実行系列の選択と統合の区別、実行系列間の逐次実行と並列実行の区別、回路モジュール間のバス転送時間、バス転送が専用バス転送か共通バス転送かの区別を記述したモデルとされる。図２のバスシステムを一例として考える。Ａ乃至Ｅは回路モジュールを意味する。ＣＢＵＳは共通バス、ＥＢＵＳは専用バス（専用信号線）を意味する。図３のグラフ表記が図２のバスシステムの動作シナリオを例示する。図３の動作シナリオにおいて実線矢印は共通バスによるバス転送であり、破線矢印は専用バスによるバス転送を意味する。各転送には転送時間を記述可能である。【００３４】
図３の動作シナリオはシナリオ１とシナリオ２の何れかを選択可能になっている。シナリオ１は、回路モジュールＥからデータをフェッチし加工後、回路モジュールＢか回路モジュールＣへ転送し、回路モジュールＣに転送された場合は、回路モジュールＣがそのデータを加工して、回路モジュールＤに転送する。シナリオ２は、回路モジュールＣが回路モジュールＥからデータをフェッチして加工し、加工したデータが回路モジュールＡとＤに転送され、回路モジュールＡは回路モジュールＣからデータを受け取り次第回路モジュールＢへデータを転送する。【００３５】
図４には動作シナリオの記述内容に対する時間的遷移が例示される。黒丸は入力データを意味する。図４の（ａ）で当該動作シナリオが選択され、回路モジュールＥに最初のデータが入力される。（ｂ）において回路モジュールＥとＡのパイプライン動作が行なわれる。（ｃ）では共通バスにおいてバス競合が起きている。（ｄ）では回路モジュールＣに関しリソース競合を生ずる。上記バス競合及びリソース競合に対してはそれらを回避するための調停に要する時間を考慮して各回路モジュールの実時間制約を導出することになる。【００３６】
《モジュール排他情報》
前記領域２２が保有するモジュール排他情報は、例えば、動作シナリオ上で同一名が付加された頂点の同時実行はないとすることである。例えば、回路モジュールCは唯一つしか存在しないため、高々一つの処理しか同時には実行できない。従って、図３のシナリオ１及びシナリオ２の配置された回路モジュールCは時分割で実行する必要がある。リソース競合を排除するというポリシーを明確化するものである。【００３７】
《バス調停及びバス転送情報》
前記領域２３が保有するバス調停及びバス転送情報は以下の通りである。バス転送情報は、共通バスＣＢＵＳにおけるバス競合が一切ないと仮定した場合の各回路モジュールからのバス転送時間を意味する。バス調停情報は、共通バスにおける優先制御方式として固定優先度又は時分割ラウンドロビン方式を指定し、固定優先度の場合は，各モジュールからのバス転送に対して優先度の指定を行い、時分割ラウンドロビンではバス権切り替えのタイムスロット数の指定を行う。バス調停及びバス転送情報はバス競合に対処するために用いることになる。【００３８】
《スループット及びレイテンシ制約》
領域２４が保有するスループット及びレイテンシ制約はバスシステム全体での制約となる。図５に例示されるように、レイテンシとはバスシステムのデータ入力からデータ出力までの時間を意味する。スループットとはデータ投入間隔を意味する。各回路モジュールの実時間制約の導出に当たっては、前記スループット及びレイテンシ制約を満足させることになる。【００３９】
《１−ｓａｆｅＴＰＮ生成》
前記動作シナリオはＴＰＮに変換され、更に１−ｓａｆｅＴＰＮに変換される。前記動作シナリオはＴＰＮのサブクラスで記述されているとみなすことができる。【００４０】
予めＴＰＮについて説明する。タイムペトリネットは、トランジッション、プレース及びトークン（マーク）によってモデルを表す。黒丸で表記されるトークンはモデル中を流れる信号とみなされる。丸印で表記されるプレースはトークンを蓄える。四角で表記されるトランジッションは信号遷移のような事象を表現し、前段の接続プレース全てに必要なトークンが溜まると発火可能にされ、発火可能にされたトランジッションは発火時間という時間制約を経過することにより発火し、発火することにより前段プレースからトークンを取り去り後段のプレースにトークンを配置することを表現する。ＴＰＮにおいては、信号遷移とみなされるトランジッションに発火時間という時間制約が付され、その時間制約に従ってトークンがモデル中を流れる。発火時間を変更することによってトークンに遷移状態を変更することができる。このトークンの流れの様子をシミュレーションによって検証することによって、パイプライン的に動作を行う回路モジュール群の動作の検証が可能になる。【００４１】
例えば図６の動作シナリオをＴＰＮに変換する例を説明する。図６において回路モジュールに併記された[ｔＥ]等の時間は発火時間、バスを示す矢印に併記された[ｔＥ１]等の時間はバス転送時間である。ｃｈｏｉｃは択一的選択、ｆｏｒは複数出力への分岐、ｊｏｉｎは複数入力の結合を意味する。Ｄｕｍｍｙはダミー回路モジュールを意味する。図７及び図８には図６の動作シナリオにおける各要素の変換形態が例示される。概略的には、動作シナリオの各頂点をプレースに、頂点間を結ぶ経路をトランジッションに変換し、Ｃｈｏｉｃｅ（選択）がある場合は時間制約０のトランジッションを必ず挿入する。図７及び図８におけるＡは回路モジュールを総称する。Ａが初期ノードの場合にはＡを記載しない。これはAをタイムペトリネットの初期トランジッションとして扱うためである。図９には図６の動作シナリオをＴＰＮに変換した例が示される。【００４２】
ＴＰＮにおいてはプレースに溜まるトークンの数は一般に１個に限定されない。バスシステム内において個々に回路モジュールは各々一つ存在することを前提にしていることと矛盾を生ずる虞がある。これを解消するために、ＴＰＮを１−ｓａｆｅＴＰＮに変換して、回路モジュールに対応する各プレースにはトークンが１個しか配置されないようにする。図１０乃至図１２にはＴＰＮの各要素に対する１−ｓａｆｅＴＰＮへの変換形態が例示される。概略的には、トランジッションの間にサブネットＳＢＮを逆並列に挿入する。図１３には図のＴＰＮを１−ｓａｆｅＴＰＮに変換した例が示される。【００４３】
ここで、リソース競合を生ずるプレースに対する変換例を併せて説明する。動作シナリオ上に同一回路モジュールが２度現れた場合、トークンを同時にそれら２個の回路モジュールに配置することはできない。この場合には図１４に例示するようにサブネットＳＢＮを追加する。要するに、リソース競合を生ずるそれぞれのプレースに共通のサブネットＳＢＮを逆並列に挿入して、前記１有界のタイムペトリネットに変換する。図１５には図１３の変換結果に対してリソース競合を排除するよう変換した１−ｓａｆｅＴＰＮの例が示される。【００４４】
《バス転送時間見積もり》
バス転送見積もり部１２によるバス転送最悪時間の見積もり処理について説明する。このバス転送最悪時間の見積もりは、バスアクセスが行われた場合，他の回路モジュールが必ずバスアクセスを行おうとしていると仮定することによって最悪実行時間を見積もることができる。【００４５】
共通バスにおけるバス権調停を固定優先度によって行う場合、各回路モジュールには固定の優先度が割り当てられている。この場合にける回路モジュールのバス転送最悪時間は、図１６に例示されるように、自身のアクセス時間に、自分より優先度の高い回路モジュールのアクセス時間の総和を加算した時間とすればよい。【００４６】
共通バスにおけるバス権調停を時分割ラウンドロビンで行う場合に、タイムスロット１単位当たりでバス権切換えを行うとすると、図１７に例示されるように、各回路モジュールにおけるバス転送最悪時間は、自身のアクセス時間（ｔ１）を共通バスアクセスに参加する回路モジュール数倍して見積もれば良い。バス切換えはタイムスロットN単位毎に行う場合であってもよい。その場合の見積もり値は、┌(バス競合が一切ないと仮定した場合のバス転送時間／N)┐×N×(共通バスアクセスに参加する回路モジュール数)となる。ここで、上記┌  ┐の意味は次の通りである。┌ｘ┐はｘを超えない整数を表す。【００４７】
《実時間制約の導出》
前記実時間制約導出及び緩和部１３における実時間制約導出処理の基本は、動作シナリオの各パス毎に、バス転送見積もり時間の総和を求め、これをレイテンシ制約値から差し引き、得られた値に対して各回路モジュールの処理の重みによる加重平均を取る事で、各モジュールの実時間制約を導出することである。例えば図１８に例示される動作シナリオを例に採れば、回路モジュールａ〜ｅを有するデータパスのレイテンシ制約をＴ１とする。前記バス転送見積もり時間の総和（バスタイム）をＴ２とする。回路モジュールａ〜ｅにはＴ１−Ｔ２の時間を各モジュールの処理の重みに応じて比例配分することによって実時間制約が割り当てられる。Ｔ３は全回路モジュールにおける実時間制約の合計時間である。【００４８】
更に前記実時間制約導出及び緩和部１３は、リソース競合を考慮して回路モジュールの実時間制約を見積もる。例えば図１９に例示される動作シナリオを例に採り、例えばデータパスＡｐｓ、Ｂｐｓ、Ｃｐｓに着目したときデータパスＡｐｓ，Ｂｐｓ，Ｃｐｓ上で回路モジュールＭｉが競合し得るものとする。各データパスＡｐｓ，Ｂｐｓ，Ｃｐｓにおいて競合する回路モジュールＭｉに割り当てられる実時間制約はデータパスＡｐｓではＡ１、データパスＢｐｓではＢ１、データパスＣｐｓではＣ１とされる。このとき、リソース競合を考慮して回路モジュールの時間制約を見積もるには、図２０の（Ｂ）に示されるように、データパスＡｐｓに対してはその実時間制約の合計時間から実時間制約Ｂ１とＣ１を差し引いた残り時間に対して前記処理の重みに応じて再度各回路モジュールに実時間制約の比例配分を行なう。データパスＢｐｓに対してはその実時間制約の合計時間から実時間制約Ａ１とＣ１を差し引いた残り時間に対して前記処理の重みに応じて再度各回路モジュールに実時間制約の比例配分を行なう。データパスＣｐｓに対してはその実時間制約の合計時間から実時間制約Ａ１とＢ１を差し引いた残り時間に対して前記処理の重みに応じて再度各回路モジュールに実時間制約の比例配分を行なう。この結果データパスＡｐｓにおけるモジュールＭｉの実時間制約はＡ１からＡ２に短縮され、データパスＢｐｓにおけるモジュールＭｉの実時間制約はＢ１からＢ２に短縮され、データパスＣｐｓにおけるモジュールＭｉの実時間制約はＣ１からＣ２に短縮される。このように再度導出された実時間制約を前記１−ｓａｆｅＴＰＮにける発火時間に代入して形式検証及びシミュレーションを行うことにより、レイテンシ制約等を満足するか否かを評価する。全ての制約を満足できないときは更にリソース競合の影響が残っていると考え、上記同様に再度各回路モジュールに実時間制約の比例配分を行なう。即ち、図２０の（Ｃ）に示されるように、データパスＡｐｓにおいてそのときの実時間制約の合計時間から実時間制約Ｂ２とＣ２を差し引いた残り時間に対して前記処理の重みに応じた実時間制約の比例配分を再度行ない、回路モジュールＭｉの実時間制約をＡ２からＡ３に短縮する。データパスＢｐｓ，Ｃｐｓについても同様である。この処理を所要の制約を全て満足するまで繰り返して行なえば良い。【００４９】
上述したリソース競合を考慮した時間制約の導出手法について整理すると、動作シナリオの各データパス毎に、リソース競合を起しうる回路モジュールがリソース競合した場合のリソース競合最悪時間を各々のデータパスにおける全回路モジュールの実行時間（実時間制約の合計時間）から差し引き、得られた値に対して各回路モジュールの処理の重みによる加重平均を取る事で、各モジュールの実時間制約を導出する操作を順次繰り返す。夫々で得られた実時間制約を１−ｓａｆｅＴＰＮに当てはめて形式検証及びシミュレーションを行うことによりＴＰＮがデッドロックを生ぜず、且つレイテン制約及びスルーアウト制約を満たすまで、上記操作を繰り返して回路モジュールの実時間制約を導出していけばよい。それら制約チェックの具体的な手法については後で説明する。以下の緩和処理の説明ではリソース競合を考慮した実時間制約導出処理をＪ回繰り返して所要の制約を満足する解に到達したものとする。【００５０】
上記手法によりバス競合及びリソース競合を考慮して得られた実時間制約は、バス競合とリソース競合を回避するのに最大限の時間だけ待つと仮定しているから、その制約は比較的厳しい制約、即ち、回路モジュールにとっては比較的高速動作しなければならないような制約になっている。したがって、其れによって得られた実時間制約をある程度緩和して長くしても不都合を生ぜず、逆にそのままでは性能的に無駄若しくは過剰になると考えられる。実時間制約の緩和は回路コンポーネントの動作速度低下を可能にし、所要の性能を維持してデータ処理システムのコスト低減に寄与する。【００５１】
これに対処するのが緩和処理であり、線形計画法による補完と、補完値を用いた２分探索による導出解の緩和である。線形計画法による補完は２分探索による導出解の緩和処理時間の短縮を考慮したものであるから、処理の信頼性と言う意味では線形計画法による補完は省略しても差し支えない。【００５２】
《線形計画法による補完処理》
線形計画法による補完処理は、直感的には動作シナリオの各パスに対して、J−１回目に求まった全回路モジュールの実行許容時間（データパス毎の各回路モジュールに導出された実時間制約の合計時間）を、リソース競合のオーバーヘッドを引いたものと一致するまで、各モジュールの実時間制約を引き伸ばした時間制約が求める解候補となる。そこで、各データパスに対して，下記不等式を構成し、各データパス上に対する全回路モジュールの実行許容時間の総和が最大となるよう線形計画法で解を求め、得られた値に対して各回路モジュールの処理の重みによる加重平均を取る事で、各モジュールの実時間制約を導出する。【００５３】
その具体的な処理手順は以下の通りである。各データパスに不等式（１）、（２）を適用する。
（Ｊ回目の値）≦線形計画補完解≦（Ｊ−１回目の値）…（１）
線形計画補完解≦（Ｊ−１回目の値）―（リソース競合のオーバーヘッド）…（２）
さらに、ここで、リソース競合のオーバーヘッドは、各モジュールの時間制約を変数として、その変数の和で表現するものとし、不等式（３）を適用する。
（Ｊ回目の値から加重平均で求めたモジュールの時間制約）≦モジュールの時間制約を表す変数≦（Ｊ−１回目の値から加重平均で求めたモジュールの時間制約）…（３）
そして、同じモジュールの異なるパス上での時間制約を表す変数が全て等しいという等式を用いて、補完値を得る。【００５４】
《２分探索法よる導出解緩和》
前記実時間制約の導出についてリソース競合を考慮した実時間制約導出処理をＪ回繰り返して所要の制約を満足する解に到達したとき、Ｊ−１回目で得られた値、線形計画補完解、Ｊ回目で得られた値、の間のどこかにより制約が緩い解が存在すると考えられるので、図２１に例示されるように、これら３点を２次元座標上で補完する。補完して得られた解候補集合の中から最も良い解を効率よく探索するために、線形計画補完解からスタートして、レイテンシ制約を変更しながら，活性でかつスループット及びレイテンシが満たされる範囲（判定手法は以下で説明）で、初期に与えたレイテンシ制約を満たす最大解を、二分探索法に従って探索する。【００５５】
《導出した時間制約が解となるかのチェック手法》
先ず、１−ｓａｆｅＴＰＮがデッドロックを生ぜず、且つレイテン制約及びスルーアウト制約を満たすか否かの解析手法について説明する。デッドロックがないかは、ＴＰＮ解析ツール（ＴＩＮＡ）を用いたシミュレーションにより到達可能性判定を行なえば良い。【００５６】
スループット制約が満たされるかは、初期トランジッションに付加した１有界とするためのプレースのトークン数を２個に変更して、変更したＴＰＮが１有界であるかを検証すればよい。即ち、動作シナリオから構成した１−ｓａｆｅＴＰＮには、バス転送見積もりで算出した時間制約、及びその他のトランジションへの時間制約を付加した図１５に例示されるようなＴＰＮとされる。図１５のＴＰＮがスループット制約を満たすか否かは確認しない限り定かでないため、仮にスループット制約が満たされていないとすると、図１５のＴＰＮのソーストランジションへの入力アークを持つプレースを除去した場合、ソーストランジションからの出力アークが入力されるプレースのトークン数が有界である保障はない。また，一般のＴＰＮに於いてネットが有界であるか否かの判定は決定不能問題である。また，もしスループット制約を満たさないならば、ソーストランジションからの出力アークを持つプレースに対して一有界の制限を解除すると、トークンが二つ以上蓄積するはずである。そうならないことを検証するためには、当該プレースにトークンを二つまで置くことができるようにし、さらに、トークンが二つ溜まると発火するような新たなトランジションを付加し、そのトランジションが発火するか否かを検証すればよい。そのために、ソーストランジションへの出力アークを持つプレースのトークン数を２に変更し、ソーストランジションからの入力アークを持つプレースに重み２の出力アークとそのアークを入力とするトランジションを付加した図２２に例示される新たなＴＰＮを構成し、ＴＰＮ解析ツールで図２２のＴＰＮの解析を行う。図２２に例示される新たなＴＰＮはその構成の仕方から有界なＴＰＮであることは明らかである。図２２に例示される新たなＴＰＮにおいて、全てのプレースと新たに付加したトランジション以外の全てトランジションが活性（トークンが詰まらずにその流れが阻害されないこと）であるならば、図１５のＴＰＮに於いてソーストランジションへの入力アークを持つプレースを除去した別のＴＰＮは一有界且つ活性となり、スループット制約を満たすことが保証される。【００５７】
特に、スループットの解析をシミュレーションで行う場合は、図２３に示すように、時間制約０の新たなトランジッションを設けて、そのトランジッションと初期トランジッションの後段のプレースを重み２のアークで結べば良い。シミュレーションを実施して、新たに追加したトランジッションが発火すれば、スループットが満たされなかった事となる。尚、図２３のＴＰＮに対して、ＴＰＮ解析ツールで到達可能性判定を行って、新たなトランジッションが発火しない事を確認する事でも、スループットが満たされているか否かの判定が可能である。発火しなければ、初期プレースに高々１つしかトークンが配置されない事がわかるため、スループットが満たされている事が確認できる。【００５８】
レイテンシ制約が満たされているかはＴＰＮ解析ツールでシミュレーションを実行し、トランジッションの発火列を取得して、初期トランジッションの発火から最終段トランジッションが発火するまでの時間を計測することによって行なうことができる。【００５９】
《ＭＰＥＧデコーダバスシステム》
本発明をＭＰＥＧデコーダバスシステムに適用した場合の具体例を説明する。ＭＰＥＧデコーダシステムは図２４に示される機能ブロックを備え、図２５に例示される復号処理を実現する。図２４及び図２５に示されえる技術的事項は公知である。ＣＶＩＦはビデオ入力インタフェース、ＤＶＩＦはビデオ出力インタフェース、ＦＩＦＯはＦＩＦＯバッファ、ＶＬＤは可変長符号化回路、ＲＺＤはジグザグデコーダ、ＲＩＳＣは縮小命令セットタイプのプロセッサ、ＤＭＥＭはデータメモリ、ＩＤＣＴは逆離散コサイン変換回路、ＩＱは量子化回路、ＲＭＥＭは参照画像を格納するためのデータメモリ、ＭＣは画像補間処理回路、ｅｘｔＤＲＡＭは外部メモリである。ＢＵＳは６４ビット共通バスである。図２４の各回路モジュールに対する実時間性制約を導出する処理を行なった。図２６にはそのときの動作シナリオの具体例が示される。図２７には各回路モジュールの処理に応じた重みが示される。図２８には２分探索法によって最終的に得られた導出解が例示される。制約充足解の内レイテンシが最大の値を解として採用することになる。【００６０】
以上説明したバスシステムの設計方法並びに設計支援装置によれば以下の効果を得ることができる。画像処理などのデータ入出力レートが一定のバスシステムに対して、バス構成するモジュールの実時間制約の導出が短期間で行える。各回路モジュールの負荷に応じた実時間制約導出が可能となり、公平な実時間割り当てが可能となる。手戻りのない設計が可能となる。専用処理を行うコプロセッサを設計する際、実装でのハード／ソフトの切り分けを、処理時間を考慮して行う事が可能となり、より低コストな性能改善の検討が容易となる。専用処理を行うコプロセッサの設計効率向上・設計期間短縮に寄与する。顧客要求で実時間制約が厳格なＡＳＩＣ（Application Specific Integrated Circuit）やＡＳＳＰ（Application Specific Standard Product）の開発での仕様検討が短期で可能となる。ＩＰ再利用設計での新規設計部分の実時間制約を導出でき、再利用ＩＰの消費時間の妥当性判定が可能となるため、変更設計量の最小化検討も可能となり、設計期間短縮が可能となる。専用処理を行うバスシステムの様々な実装方式の検討が早期に短期間で実施可能となり、より性能／コスト比の高い製品開発が可能となる。【００６１】
以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。本発明が開発対象とするデータ処理システムに要求される機能及び仕様は適宜変更可能である。
【産業上の利用可能性】
【００６２】
本発明は、ＭＰＥＧ２デコーダバスシステムに開発設計に適用する場合に限定されず、専用処理を行うバスシステムを搭載するＡＳＳＰ、画像処理などデータ処理システムであって実時間制約が厳しいＡＳＩＣなど、種々の半導体集積回路や電子機器の開発設計に広く適用することができる。
【図１】
2007099590.tif 000003
【図２】
2007099590.tif 000004
【図３】
2007099590.tif 000005
【図４】
2007099590.tif 000006
【図５】
2007099590.tif 000007
【図６】
2007099590.tif 000008
【図７】
2007099590.tif 000009
【図８】
2007099590.tif 000010
【図９】
2007099590.tif 000011
【図１０】
2007099590.tif 000012
【図１１】
2007099590.tif 000013
【図１２】
2007099590.tif 000014
【図１３】
2007099590.tif 000015
【図１４】
2007099590.tif 000016
【図１５】
2007099590.tif 000017
【図１６】
2007099590.tif 000018
【図１７】
2007099590.tif 000019
【図１８】
2007099590.tif 000020
【図１９】
2007099590.tif 000021
【図２０】
2007099590.tif 000022
【図２１】
2007099590.tif 000023
【図２２】
2007099590.tif 000024
【図２３】
2007099590.tif 000025
【図２４】
2007099590.tif 000026
【図２５】
2007099590.tif 000027
【図２６】
2007099590.tif 000028
【図２７】
2007099590.tif 000029
【図２８】
2007099590.tif 000030
【国際調査報告】
2007099590.tif 000031
2007099590.tif 000032
2007099590.tif 000033
2007099590.tif 000034