【手続補正書】
【提出日】平成20年4月4日(2008.4.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
マルチプロセッサシステムにおいてプロセッサタスクを管理する方法であって、
前記マルチプロセッサシステムを構成する複数の処理ユニットによってアクセス可能な共有メモリに前記プロセッサタスクを格納し、
前記プロセッサタスクのそれぞれと関連付けられたタスクテーブルエントリを含むタスクテーブルを前記共有メモリに格納し、
前記タスクテーブルエントリの少なくとも一部を互いにリンク付けして、階層的な順序で呼び出されるプロセッサタスクのリストを少なくともひとつ取得し、
前記リスト内のプロセッサタスクのうち最初のプロセッサタスクを表すヘッドポインタと、前記リスト内のプロセッサタスクのうち最後のプロセッサタスクを表すテイルポインタのうち、少なくともひとつを含むタスクキューを前記共有メモリに格納し、
前記タスクキューと前記タスクテーブルを前記共有メモリから前記処理ユニットにコピーし、
前記処理ユニットが、前記タスクテーブルと前記タスクキューを使用して、前記プロセッサタスクのリストにしたがっていずれのプロセッサタスクを実行すべきかを判定するのを許可することを含むプロセッサタスクの管理方法。
【請求項２】
前記複数の処理ユニットは、それぞれがローカルメモリを有している複数のサブ処理ユニットを含み、該サブ処理ユニットは前記共有メモリ内の前記プロセッサタスクにアクセスし、
前記タスクキューと前記タスクテーブルを、前記共有メモリから前記サブ処理ユニットのうちひとつのローカルメモリにコピーし、
呼び出しの準備ができているプロセッサタスクのうち所与のひとつへ向かうヘッドポインタを求めて前記タスクキューを検索し、
実行のために、所与のプロセッサタスクを前記共有メモリから所与のサブ処理ユニットのローカルメモリにコピーすることをさらに含む請求項１に記載のプロセッサタスクの管理方法。
【請求項３】
前記タスクテーブルエントリのそれぞれが、以下の(ｉ)から(ｉｖ)のうち少なくともひとつを含むことを特徴とする請求項１または２に記載のプロセッサタスクの管理方法：
(ｉ) 関連するプロセッサタスクが前記処理ユニットのひとつまたは複数によって実行される準備ができているか否かを示す表示、
(ｉｉ) 関連するプロセッサタスクの優先度レベルに関する表示、
(ｉｉｉ) タスクテーブルエントリのリスト内での前のタスクテーブルエントリへのポインタ、
(ｉｖ) タスクテーブルエントリのリスト内での次のタスクテーブルエントリへのポインタ。
【請求項４】
前記タスクテーブルエントリの各グループをリンク付けして、階層的な順序であるプロセッサタスクのリストを生成し、
前記プロセッサタスクのリストのそれぞれに対するヘッドポインタとテイルポインタのうち少なくともひとつを各エントリが有しているタスクキューエントリを備えるタスクキューを提供することをさらに含む請求項１または２に記載のプロセッサタスクの管理方法。
【請求項５】
前記リストは共通の優先度レベルのプロセッサタスクと関連付けられており、
前記タスクキューは、前記プロセッサタスクの複数の優先度レベルそれぞれに対するタスクキューエントリを含むことを特徴とする請求項４に記載のプロセッサタスクの管理方法。
【請求項６】
前記タスクキューを検索するステップは、呼び出しの準備ができているプロセッサタスクのうち最高の優先度レベルを持つプロセッサタスクへのヘッドポインタを検索することを含む請求項２に記載のプロセッサタスクの管理方法。
【請求項７】
前記リストから所与のプロセッサタスクを除去することをさらに含む請求項２に記載のプロセッサタスクの管理方法。
【請求項８】
前記タスクテーブルエントリが、それぞれ次のタスクテーブルエントリへのポインタを含み、
前記除去するステップは、所与のタスクテーブルエントリのＮＥＸＴポインタを使用して、次に呼び出しの準備ができている新たな最初のプロセッサタスクを識別するよう前記ヘッドポインタを変更することを含む請求項７に記載のプロセッサタスクの管理方法。
【請求項９】
前記タスクテーブルエントリのそれぞれが、前のタスクテーブルエントリへのポインタを備え、
当該方法は、前記リストの新たな最初のプロセッサタスクに関連付けられたタスクテーブルエントリをポイントするように、前記リストの最後のタスクテーブルエントリのＰＲＥＶポインタを修正することをさらに含む請求項７に記載のプロセッサタスクの管理方法。
【請求項１０】
前記タスクテーブルエントリがそれぞれ、関連するプロセッサタスクが実行の準備ができているか、または前記サブ処理ユニットのうちひとつまたは複数で実行中かについての表示を含み、
当該方法は、所与のプロセッサタスクが実行中であることを示すように、前記所与のタスクテーブルエントリを修正することをさらに含む請求項２に記載のプロセッサタスクの管理方法。
【請求項１１】
所与のサブ処理ユニットによる使用が完了したとき、前記所与のサブ処理ユニットのローカルメモリから前記共有メモリに前記タスクキューと前記タスクテーブルをコピーすることをさらに含む請求項２に記載のプロセッサタスクの管理方法。
【請求項１２】
所与のサブ処理ユニットによる使用が完了したとき、前記タスクキューと前記タスクテーブルを前記共有メモリからコピーすることを許可することをさらに含む請求項１１に記載のプロセッサタスクの管理方法。
【請求項１３】
マルチプロセッサシステムのプロセッサタスクを管理する方法であって、
前記マルチプロセッサシステムの複数の処理ユニットによってアクセス可能な共有メモリに前記プロセッサタスクを格納し、
前記プロセッサタスクのそれぞれと関連付けられるタスクテーブルエントリを含むタスクテーブルを前記共有メモリに格納し、
前記タスクテーブルエントリの少なくとも一部を互いにリンク付けして、階層的な順序のプロセッサタスクのリストを少なくともひとつ取得し、
前記処理ユニットのうち所与の処理ユニットの範囲内で、前記リストのプロセッサタスクのうち最初のタスクの実行を少なくとも開始するステップであって、前記プロセッサタスクのうち最初のタスクは、前記プロセッサタスクの別のタスクが実行可能となるように前記所与の処理ユニットに対して譲歩し、
前記リスト内のプロセッサタスクのうち新たな最初のタスクを表すヘッドポインタと、前記リスト内のプロセッサタスクのうち最後のひとつを表すテイルポインタのうち、少なくともひとつを含むタスクキューを前記共有メモリに格納し、
前記所与の処理ユニットが前記タスクテーブルと前記タスクキューとを使用することを許可することで、該所与の処理ユニット内でいずれのプロセッサタスクを次に実行すべきかを判定することをさらに含むプロセッサタスクの管理方法。
【請求項１４】
前記複数の処理ユニットは、それぞれがローカルメモリを有する複数のサブ処理ユニットを含み、
前記判定するステップが、
前記共有メモリから所与のサブ処理ユニットのローカルメモリに前記タスクキューと前記タスクテーブルとをコピーし、
呼び出しの準備ができている新たな最初のプロセッサタスクへのヘッドポインタを求めて前記タスクキューを検索することをさらに含む請求項１３に記載のプロセッサタスクの管理方法。
【請求項１５】
前記最初のプロセッサタスクを前記リストに加えることをさらに含む請求項１３に記載のプロセッサタスクの管理方法。
【請求項１６】
前記タスクテーブルエントリが、それぞれ次のタスクテーブルエントリへのポインタと前のタスクテーブルエントリへのポインタを含み、
前記加えるステップは、前記最初のプロセッサタスクに関連するタスクテーブルエントリへのリンクを含むように、前記タスクテーブルエントリのリンク付けを修正することを含む請求項１５に記載のプロセッサタスクの管理方法。
【請求項１７】
前記タスクテーブルエントリのリンク付けを修正するステップは、以前は互いにリンク付けされていた前のタスクテーブルエントリと後のタスクテーブルエントリとの間で、前記最初のプロセッサタスクに関連するタスクテーブルエントリをリンク付けすることを含む請求項１６に記載のプロセッサタスクの管理方法。
【請求項１８】
前記最初のプロセッサタスクに関連するタスクテーブルをポイントするように、前のタスクテーブルエントリのＮＥＸＴポインタを修正し、
前のタスクテーブルエントリをポイントするように、前記最初のプロセッサタスクに関連するタスクテーブルエントリのＰＲＥＶポインタを修正し、
後のタスクテーブルエントリをポイントするように、前記最初のプロセッサタスクに関連するタスクテーブルエントリのＮＥＸＴポインタを修正し、
前記最初のプロセッサタスクに関連するタスクテーブルエントリをポイントするように、後のタスクテーブルエントリのＰＲＥＶポインタを修正することをさらに含む請求項１７に記載のプロセッサタスクの管理方法。
【請求項１９】
プロセッサタスクを実行するためのローカルメモリをそれぞれが含む複数の処理ユニットと、
(ｉ) 実行の準備ができているプロセッサタスクと、(ｉｉ) 各プロセッサタスクに関連するタスクテーブルエントリを含むタスクテーブルと、を格納するよう動作可能な共有メモリと、を備え、
前記タスクテーブルエントリの少なくとも一部が互いにリンク付けされて、階層的な順序で呼び出されるプロセッサタスクの少なくともひとつのリストを取得し、
前記共有メモリは、前記リスト内のプロセッサタスクのうち最初のプロセッサタスクを表すヘッドポインタと、前記リスト内のプロセッサタスクのうち最後のプロセッサタスクを表すテイルポインタのうち、少なくともひとつを有するタスクキューを格納するよう動作可能であり、
前記処理ユニットは、前記タスクテーブルと前記タスクキューとを使用して、前記プロセッサタスクのリストにしたがっていずれのプロセッサタスクを前記共有メモリから自身のローカルメモリへとコピーして実行すべきかを判定するよう動作可能であることを特徴とするマルチプロセッサ装置。
【請求項２０】
前記複数の処理ユニットは、前記共有メモリ内のプロセッサタスクにアクセスする複数のサブ処理ユニットを備え、該複数のサブ処理ユニットは、それぞれがローカルメモリを有しており、
前記サブ処理ユニットは、
前記タスクキューと前記タスクテーブルとを前記共有メモリからそれぞれのローカルメモリにコピーし、
呼び出しの準備ができているプロセッサタスクのうち所与のプロセッサタスクへ向かうヘッドポインタを求めて前記タスクキューを検索し、
前記共有メモリから自身のローカルメモリへと前記所与のプロセッサタスクを実行のためにコピーするように動作可能であることを特徴とする請求項１９に記載のマルチプロセッサ装置。
【請求項２１】
前記タスクテーブルエントリのそれぞれが、以下の(ｉ)から(ｉv)のうち少なくともひとつを含むことを特徴とする請求項１９または２０に記載のマルチプロセッサ装置：
(ｉ) 関連するプロセッサタスクが前記処理ユニットのひとつまたは複数によって実行される準備ができているか否かを示す表示、
(ｉｉ) 関連するプロセッサタスクの優先度レベルに関する表示、
(ｉｉｉ) タスクテーブルエントリのリスト内での前のタスクテーブルエントリへのポインタ、
(ｉｖ) タスクテーブルエントリのリスト内での次のタスクテーブルエントリへのポインタ。
【請求項２２】
前記タスクテーブルエントリの各グループをリンク付けして、階層的な順序であるプロセッサタスクのリストを生成し、
前記タスクキューは、前記プロセッサタスクの各リスト用のヘッドポインタおよびテイルポインタのうち少なくともひとつを各エントリが有するタスクキューエントリを備えることを特徴とする請求項１９または２０に記載のマルチプロセッサ装置。
【請求項２３】
前記リストはそれぞれ共通の優先度レベルのプロセッサタスクと関連付けられており、
前記タスクキューは、前記プロセッサタスクの複数の優先度レベルの各々についてタスクキューエントリを備えることを特徴とする請求項２２に記載のマルチプロセッサ装置。
【請求項２４】
前記サブ処理ユニットは、呼び出しの準備ができているプロセッサタスクのうち最高の優先度レベルを持つプロセッサタスクへのヘッドポインタを求めて前記タスクキューを検索するよう動作可能であることを特徴とする請求項２０に記載のマルチプロセッサ装置。
【請求項２５】
前記サブ処理ユニットは、前記リストから所与のプロセッサタスクを除去するよう動作可能であることを特徴とする請求項２０に記載のマルチプロセッサ装置。
【請求項２６】
前記タスクテーブルエントリは、それぞれ次のタスクテーブルエントリへのポインタを含み、
前記サブ処理ユニットは、前記所与のタスクテーブルエントリのＮＥＸＴポインタを使用して、次に呼び出しの準備ができている新たな最初のプロセッサタスクを識別するように前記ヘッドポインタを修正するよう動作可能であることを特徴とする請求項２５に記載のマルチプロセッサ装置。
【請求項２７】
前記タスクテーブルエントリのそれぞれが、前のタスクテーブルエントリへのポインタを備え、
前記サブ処理ユニットは、前記リストの新たな最初のプロセッサタスクに関連付けられたタスクテーブルエントリをポイントするように、前記リストの最後のタスクテーブルエントリのＰＲＥＶポインタを修正するよう動作可能であることを特徴とする請求項２５に記載のマルチプロセッサ装置。
【請求項２８】
前記タスクテーブルエントリがそれぞれ、関連するプロセッサタスクが実行の準備ができているか、または前記サブ処理ユニットのうちひとつまたは複数で実行中かについての表示を含み、
前記サブ処理ユニットは、所与のプロセッサタスクが実行中であることを示すように、前記所与のタスクテーブルエントリを修正するよう動作可能であることを特徴とする請求項２０に記載のマルチプロセッサ装置。
【請求項２９】
前記サブ処理ユニットによる使用が完了したとき、該サブ処理ユニットは前記タスクキューと前記タスクテーブルとを自身のローカルメモリから前記共有メモリにコピーするよう動作可能であることを特徴とする請求項２０に記載のマルチプロセッサ装置。
【請求項３０】
プロセッサタスクを実行するためのローカルメモリをそれぞれ備える複数のサブ処理ユニットと、
(ｉ) 実行の準備ができているプロセッサタスクと、(ｉｉ)各プロセッサタスクに関連付けられるタスクテーブルエントリを含むタスクテーブルと、を格納するよう動作可能な共有メモリと、を備え、
タスクテーブルエントリの少なくとも一部を互いにリンク付けして、階層的な順序のプロセッサタスクのリストを少なくともひとつ取得し、
前記サブ処理ユニットは、最初のプロセッサタスクの実行を開始し、前記プロセッサタスクのうち別のタスクが実行可能になるように譲歩するよう少なくとも動作可能であり、
前記共有メモリは、前記リスト内のプロセッサタスクのうち新たな最初のプロセッサタスクを表すヘッドポインタと、前記リスト内のプロセッサタスクのうち最後のプロセッサタスクを表すテイルポインタのうち、少なくともひとつを含むタスクキューを格納するよう動作可能であり、
前記処理ユニットは、前記タスクテーブルと前記タスクキューを使用して、次にいずれのプロセッサタスクを実行すべきかを判定するよう動作可能であることを特徴とするマルチプロセッサ装置。
【請求項３１】
前記サブ処理ユニットは、
前記タスクキューと前記タスクテーブルを前記共有メモリから自身のローカルメモリにコピーし、
呼び出しの準備ができている新たな最初のプロセッサタスクへのヘッドポインタを求めて前記タスクキューを検索するよう動作可能であることを特徴とする請求項３０に記載のマルチプロセッサ装置。
【請求項３２】
前記サブ処理ユニットは、前記最初のプロセッサタスクを前記リストに加えるよう動作可能であることを特徴とする請求項３０に記載のマルチプロセッサ装置。
【請求項３３】
前記タスクテーブルエントリが、それぞれ次のタスクテーブルエントリへのポインタと前のタスクテーブルエントリへのポインタとを含み、
前記サブ処理ユニットは、前記最初のプロセッサタスクに関連するタスクテーブルエントリへのリンクを含むように、前記タスクテーブルエントリのリンク付けを修正するよう動作可能であることを特徴とする請求項３２に記載のマルチプロセッサ装置。
【請求項３４】
前記サブ処理ユニットは、以前は互いにリンク付けされていた前のタスクテーブルエントリと後のタスクテーブルエントリとの間で、前記最初のプロセッサタスクに関連するタスクテーブルエントリをリンク付けすることによって、前記タスクテーブルエントリのリンク付けを修正するよう動作可能であることを特徴とする請求項３３に記載のマルチプロセッサ装置。
【請求項３５】
前記サブ処理ユニットは、
前記最初のプロセッサタスクに関連するタスクテーブルをポイントするように、前のタスクテーブルエントリのＮＥＸＴポインタを修正し、
前のタスクテーブルエントリをポイントするように、前記最初のプロセッサタスクに関連するタスクテーブルエントリのＰＲＥＶポインタを修正し、
後のタスクテーブルエントリをポイントするように、前記最初のプロセッサタスクに関連するタスクテーブルエントリのＮＥＸＴポインタを修正し、
前記最初のプロセッサタスクに関連するタスクテーブルエントリをポイントするように、後のタスクテーブルエントリのＰＲＥＶポインタを修正するよう動作可能であることを特徴とする請求項３４に記載のマルチプロセッサ装置。