(57)【要約】  各態様は、軽量カーネルのスケジューリングおよび実行を、タスク構造を確立せずにシンプルタスクとしてスレッドによって直ちに実施するためのコンピューティングデバイス、システム、および方法を含む。コンピューティングデバイスは、タスクキューにおけるタスクポインタが軽量カーネルに関するシンプルタスクポインタであるかどうかを判定してもよい。コンピューティングデバイスは、軽量カーネルに関する第1のシンプルタスクをスレッドによって実行されるようにスケジュールしてもよい。コンピューティングデバイスは、シンプルタスクテーブルのエントリから軽量カーネルに関するカーネルポインタを取り出してもよい。シンプルタスクテーブル内のエントリは、シンプルタスクポインタに関連付けられてもよい。コンピューティングデバイスは、軽量カーネルをシンプルタスクとして直ちに実行してもよい。
2018528515.tif 000002
【特許請求の範囲】
【請求項１】
コンピューティングデバイスにおいて軽量カーネルをスケジュールし実行する方法であって、
タスクキューにおける第1のタスクポインタが軽量カーネルに関するシンプルタスクポインタであるかどうかを判定するステップと、
前記第1のタスクポインタがシンプルタスクポインタであると判定したことに応じて、前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールするステップと、
シンプルタスクテーブルのエントリから前記軽量カーネルに関するカーネルポインタを取り出すステップであって、前記エントリが前記シンプルタスクポインタに関連する、ステップと、
前記軽量カーネルを前記第1のシンプルタスクとして直ちに実行するステップとを含む方法。
【請求項２】
前記第1のシンプルタスクの実行を完了するステップと、
前記シンプルタスクテーブルの前記エントリのカーネルイテレーションカウンタのデータを更新するステップとをさらに含む、請求項1に記載の方法。
【請求項３】
前記軽量カーネルのカーネルイテレーションが分割可能であるかどうかを判定するステップと、
前記軽量カーネルの前記カーネルイテレーションが分割可能であると判定したことに応じて前記軽量カーネルの前記カーネルイテレーションをイテレーション部分に分割するステップとをさらに含み、
前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールするステップは、前記第1のシンプルタスクに少なくとも1つのイテレーション部分を割り当てるステップを含み、
前記第1のシンプルタスクの実行を完了するステップは、前記第1のシンプルタスクに割り当てられた前記少なくとも1つのイテレーション部分のイテレーションの回数と等しい回数の前記第1のシンプルタスクの実行を完了するステップを含み、
前記シンプルタスクテーブルの前記エントリのカーネルイテレーションカウンタのデータを更新するステップは、前記第1のシンプルタスクに割り当てられた前記少なくとも1つのイテレーション部分の前記回数のイテレーションを完了したことを反映するように前記カーネルイテレーションカウンタの前記データを更新するステップを含む、請求項2に記載の方法。
【請求項４】
前記第1のシンプルタスクのすべてのイテレーションが完了したかどうかを、前記カーネルイテレーションカウンタの前記データから判定するステップと、
前記第1のシンプルタスクの前記イテレーションのすべてが完了したと判定したことに応じて前記シンプルタスクテーブルの前記エントリを削除するステップとをさらに含む、請求項2に記載の方法。
【請求項５】
前記軽量カーネルの実行に関する制限を特定するステップであって、前記制限が、メインスレッド、クリティカルスレッド、および非クリティカルスレッドを含む、前記軽量カーネルを実行するための指定されたスレッド、前記軽量カーネルを実行するためのレイテンシ要件、ならびに前記軽量カーネルを記憶するメモリに対する前記第1のスレッドを実行するプロセッサの近接度のうちの1つを含む、ステップをさらに含み、
前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールするステップは、前記軽量カーネルの実行に関する前記制限に基づいて前記第1のスレッドを選択するステップを含む、請求項1に記載の方法。
【請求項６】
前記タスクキューにおける第2のタスクポインタが前記軽量カーネルに関する前記シンプルタスクポインタであるかどうかを判定するステップと、
前記第2のタスクポインタが前記シンプルタスクポインタであると判定したことに応じて、前記軽量カーネルに関する第2のシンプルタスクを第2のスレッドによって実行されるようにスケジュールするステップと、
前記シンプルタスクテーブルの前記エントリから前記軽量カーネルに関する前記カーネルポインタを取り出すステップであって、前記エントリが前記シンプルタスクポインタに関連付けられる、ステップと、
前記軽量カーネルを前記第2のシンプルタスクとして直ちに実行するステップとをさらに含む、請求項1に記載の方法。
【請求項７】
前記第1のシンプルタスクの第1の出力と前記第2のシンプルタスクの第2の出力を組み合わせるステップをさらに含む、請求項6に記載の方法。
【請求項８】
要求されたプロセスが前記軽量カーネルを含むかどうかを判定するステップと、
前記要求されたプロセスが前記軽量カーネルを含むと判定したことに応じて、前記シンプルタスクテーブルが満杯であるかどうかを判定するステップと、
前記シンプルタスクテーブルが満杯ではないと判定したことに応じて、前記シンプルタスクテーブル内に前記軽量カーネルに関する前記エントリを作成するステップと、
前記エントリに関連する前記シンプルタスクポインタを前記タスクキューに追加するステップと、
前記シンプルタスクテーブルが満杯であると判定したことに応じて、前記軽量カーネルに関連するノーマルタスクポインタを前記タスクキューに追加するステップとをさらに含む、請求項1に記載の方法。
【請求項９】
コンピューティングデバイスであって、
動作を実行するためのプロセッサ実行可能命令を有するように構成された第1のプロセッサを備え、前記動作は、
タスクキューにおける第1のタスクポインタが軽量カーネルに関するシンプルタスクポインタであるかどうかを判定する動作と、
前記第1のタスクポインタがシンプルタスクポインタであると判定したことに応じて、前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールする動作と、
シンプルタスクテーブルのエントリから前記軽量カーネルに関するカーネルポインタを取り出す動作であって、前記エントリが前記シンプルタスクポインタに関連する、動作と、
前記軽量カーネルを前記第1のシンプルタスクとして直ちに実行する動作とを含むコンピューティングデバイス。
【請求項１０】
前記第1のプロセッサは、動作を実行するためのプロセッサ実行可能命令を有するように構成され、前記動作は、
前記第1のシンプルタスクの実行を完了する動作と、
前記シンプルタスクテーブルの前記エントリのカーネルイテレーションカウンタのデータを更新する動作とをさらに含む、請求項9に記載のコンピューティングデバイス。
【請求項１１】
前記第1のプロセッサは、動作を実行するためのプロセッサ実行可能命令を有するように構成され、前記動作は、
前記軽量カーネルのカーネルイテレーションが分割可能であるかどうかを判定する動作と、
前記軽量カーネルの前記カーネルイテレーションが分割可能であると判定したことに応じて前記軽量カーネルの前記カーネルイテレーションをイテレーション部分に分割する動作とをさらに含み、
前記第1のプロセッサは、
前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールする動作が、前記第1のシンプルタスクに少なくとも1つのイテレーション部分を割り当てる動作を含み、
前記第1のシンプルタスクの実行を完了する動作が、前記第1のシンプルタスクに割り当てられた前記少なくとも1つのイテレーション部分のイテレーションの回数に等しい回数の前記第1のシンプルタスクの実行を完了する動作を含み、
前記シンプルタスクテーブルの前記エントリのカーネルイテレーションカウンタのデータを更新する動作が、前記第1のシンプルタスクに割り当てられた前記少なくとも1つのイテレーション部分の前記回数のイテレーションを完了したことを反映するように前記カーネルイテレーションカウンタの前記データを更新する動作を含むように動作を実行するためのプロセッサ実行可能命令を有するように構成される、請求項10に記載のコンピューティングデバイス。
【請求項１２】
前記第1のプロセッサは、動作を実行するためのプロセッサ実行可能命令を有するように構成され、前記動作は、
前記第1のシンプルタスクのすべてのイテレーションが完了したかどうかを、前記カーネルイテレーションカウンタの前記データから判定する動作と、
前記第1のシンプルタスクの前記イテレーションのすべてが完了したと判定したことに応じて前記シンプルタスクテーブルの前記エントリを削除する動作とをさらに含む、請求項10に記載のコンピューティングデバイス。
【請求項１３】
前記第1のプロセッサに通信可能に接続されたメモリと、
前記第1のプロセッサに通信可能に接続された第2のプロセッサとをさらに備え、
前記第1のプロセッサは、前記軽量カーネルの実行に関する制限を特定する動作をさらに含む動作を実行するためのプロセッサ実行可能命令を有するように構成され、前記制限は、メインスレッド、クリティカルスレッド、および非クリティカルスレッドを含む、前記軽量カーネルを実行するための指定されたスレッド、前記軽量カーネルを実行するためのレイテンシ要件、ならびに前記軽量カーネルを記憶する前記メモリに対する前記第1のスレッドを実行する前記第2のプロセッサの近接度のうちの1つを含み、
前記第1のプロセッサは、前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールする動作が、前記軽量カーネルの実行に関する前記制限に基づいて前記第1のスレッドを選択する動作を含むように動作を実行するためのプロセッサ実行可能命令を有するように構成される、請求項9に記載のコンピューティングデバイス。
【請求項１４】
前記第1のプロセッサは、動作を実行するためのプロセッサ実行可能命令を有するように構成され、前記動作は、
前記タスクキューにおける第2のタスクポインタが前記軽量カーネルに関する前記シンプルタスクポインタであるかどうかを判定する動作と、
前記第2のタスクポインタが前記シンプルタスクポインタであると判定したことに応じて、前記軽量カーネルに関する第2のシンプルタスクを第2のスレッドによって実行されるようにスケジュールする動作と、
前記シンプルタスクテーブルの前記エントリから前記軽量カーネルに関する前記カーネルポインタを取り出す動作であって、前記エントリが前記シンプルタスクポインタに関連付けられる、動作と、
前記軽量カーネルを前記第2のシンプルタスクとして直ちに実行する動作とをさらに含む、請求項9に記載のコンピューティングデバイス。
【請求項１５】
前記第1のプロセッサは、動作を実行するためのプロセッサ実行可能命令を有するように構成され、前記動作は、
前記第1のシンプルタスクの第1の出力と前記第2のシンプルタスクの第2の出力を組み合わせる動作をさらに含む、請求項14に記載のコンピューティングデバイス。
【請求項１６】
前記第1のプロセッサは、動作を実行するためのプロセッサ実行可能命令を有するように構成され、前記動作は、
要求されたプロセスが前記軽量カーネルを含むかどうかを判定する動作と、
前記要求されたプロセスが前記軽量カーネルを含むと判定したことに応じて、前記シンプルタスクテーブルが満杯であるかどうかを判定する動作と、
前記シンプルタスクテーブルが満杯ではないと判定したことに応じて、前記シンプルタスクテーブル内に前記軽量カーネルに関する前記エントリを作成する動作と、
前記エントリに関連する前記シンプルタスクポインタを前記タスクキューに追加する動作と、
前記シンプルタスクテーブルが満杯であると判定したことに応じて、前記軽量カーネルに関連するノーマルタスクポインタを前記タスクキューに追加する動作とをさらに含む、請求項9に記載のコンピューティングデバイス。
【請求項１７】
コンピューティングデバイスであって、
タスクキューにおける第1のタスクポインタが軽量カーネルに関するシンプルタスクポインタであるかどうかを判定するための手段と、
前記第1のタスクポインタがシンプルタスクポインタであると判定したことに応じて、前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールするための手段と、
シンプルタスクテーブルのエントリから前記軽量カーネルに関するカーネルポインタを取り出すための手段であって、前記エントリが前記シンプルタスクポインタに関連する、手段と、
前記軽量カーネルを前記第1のシンプルタスクとして直ちに実行するための手段とを備えるコンピューティングデバイス。
【請求項１８】
前記第1のシンプルタスクの実行を完了するための手段と、
前記シンプルタスクテーブルの前記エントリのカーネルイテレーションカウンタのデータを更新するための手段とをさらに備える、請求項17に記載のコンピューティングデバイス。
【請求項１９】
前記軽量カーネルのカーネルイテレーションが分割可能であるかどうかを判定するための手段と、
前記軽量カーネルの前記カーネルイテレーションが分割可能であると判定したことに応じて前記軽量カーネルの前記カーネルイテレーションをイテレーション部分に分割するための手段とをさらに備え、
前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールするための手段は、前記第1のシンプルタスクに少なくとも1つのイテレーション部分を割り当てるための手段を備え、
前記第1のシンプルタスクの実行を完了するための手段は、前記第1のシンプルタスクに割り当てられた前記少なくとも1つのイテレーション部分のイテレーションの回数と等しい回数の前記第1のシンプルタスクの実行を完了するための手段を備え、
前記シンプルタスクテーブルの前記エントリのカーネルイテレーションカウンタのデータを更新するための手段は、前記第1のシンプルタスクに割り当てられた前記少なくとも1つのイテレーション部分の前記回数のイテレーションを完了したことを反映するように前記カーネルイテレーションカウンタのデータを更新するための手段を備える、請求項18に記載のコンピューティングデバイス。
【請求項２０】
前記第1のシンプルタスクのすべてのイテレーションが完了したかどうかを、前記カーネルイテレーションカウンタのデータから判定するための手段と、
前記第1のシンプルタスクの前記イテレーションのすべてが完了したと判定したことに応じて前記シンプルタスクテーブルの前記エントリを削除するための手段とをさらに備える、請求項18に記載のコンピューティングデバイス。
【請求項２１】
前記軽量カーネルの実行に関する制限を特定するための手段であって、前記制限が、メインスレッド、クリティカルスレッド、および非クリティカルスレッドを含む、前記軽量カーネルを実行するための指定されたスレッド、前記軽量カーネルを実行するためのレイテンシ要件、ならびに前記軽量カーネルを記憶するメモリに対する前記第1のスレッドを実行するプロセッサの近接度のうちの1つを含む手段をさらに備え、
前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールするための手段は、前記軽量カーネルの実行に関する前記制限に基づいて前記第1のスレッドを選択するための手段を備える、請求項17に記載のコンピューティングデバイス。
【請求項２２】
前記タスクキューにおける第2のタスクポインタが前記軽量カーネルに関する前記シンプルタスクポインタであるかどうかを判定するための手段と、
前記第2のタスクポインタが前記シンプルタスクポインタであると判定したことに応じて、前記軽量カーネルに関する第2のシンプルタスクを第2のスレッドによって実行されるようにスケジュールするための手段と、
前記シンプルタスクテーブルの前記エントリから前記軽量カーネルに関する前記カーネルポインタを取り出すための手段であって、前記エントリが前記シンプルタスクポインタに関連付けられる、手段と、
前記軽量カーネルを前記第2のシンプルタスクとして直ちに実行するための手段と、
前記第1のシンプルタスクの第1の出力と前記第2のシンプルタスクの第2の出力を組み合わせるための手段とをさらに備える、請求項17に記載のコンピューティングデバイス。
【請求項２３】
要求されたプロセスが前記軽量カーネルを含むかどうかを判定するための手段と、
前記要求されたプロセスが前記軽量カーネルを含むと判定したことに応じて、前記シンプルタスクテーブルが満杯であるかどうかを判定するための手段と、
前記シンプルタスクテーブルが満杯ではないと判定したことに応じて、前記シンプルタスクテーブル内に前記軽量カーネルに関する前記エントリを作成するための手段と、
前記エントリに関連する前記シンプルタスクポインタを前記タスクキューに追加するための手段と、
前記シンプルタスクテーブルが満杯であると判定したことに応じて、前記軽量カーネルに関連するノーマルタスクポインタを前記タスクキューに追加するための手段とをさらに備える、請求項17に記載のコンピューティングデバイス。
【請求項２４】
コンピューティングデバイスの第1のプロセッサに動作を実行させるように構成されたプロセッサ実行可能命令を記憶した非一時的プロセッサ可読記憶媒体であって、前記動作は、
タスクキューにおける第1のタスクポインタが軽量カーネルに関するシンプルタスクポインタであるかどうかを判定する動作と、
前記第1のタスクポインタがシンプルタスクポインタであると判定したことに応じて、前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールする動作と、
シンプルタスクテーブルのエントリから前記軽量カーネルに関するカーネルポインタを取り出す動作であって、前記エントリが前記シンプルタスクポインタに関連する、動作と、
前記軽量カーネルを前記第1のシンプルタスクとして直ちに実行する動作とを含む非一時的プロセッサ可読記憶媒体。
【請求項２５】
前記記憶されたプロセッサ実行可能命令は、前記第1のプロセッサに動作を実行させるように構成され、前記動作は、
前記第1のシンプルタスクの実行を完了する動作と、
前記シンプルタスクテーブルの前記エントリのカーネルイテレーションカウンタのデータを更新する動作とをさらに含む、請求項24に記載の非一時的プロセッサ可読記憶媒体。
【請求項２６】
前記記憶されたプロセッサ実行可能命令は、前記第1のプロセッサに動作を実行させるように構成され、前記動作は、
前記軽量カーネルのカーネルイテレーションが分割可能であるかどうかを判定する動作と、
前記軽量カーネルの前記カーネルイテレーションが分割可能であると判定したことに応じて前記軽量カーネルの前記カーネルイテレーションをイテレーション部分に分割する動作とをさらに含み、
前記記憶されたプロセッサ実行可能命令は、
前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールする動作が、前記第1のシンプルタスクに少なくとも1つのイテレーション部分を割り当てる動作を含み、
前記第1のシンプルタスクの実行を完了する動作が、前記第1のシンプルタスクに割り当てられた前記少なくとも1つのイテレーション部分のイテレーションの回数と等しい回数の前記第1のシンプルタスクの実行を完了する動作を含み、
前記シンプルタスクテーブルの前記エントリのカーネルイテレーションカウンタのデータを更新する動作が、前記第1のシンプルタスクに割り当てられた前記少なくとも1つのイテレーション部分の前記回数のイテレーションを完了したことを反映するように前記カーネルイテレーションカウンタのデータを更新する動作を含むように前記第1のプロセッサに動作を実行させるように構成される、請求項25に記載の非一時的プロセッサ可読記憶媒体。
【請求項２７】
前記記憶されたプロセッサ実行可能命令は、前記第1のプロセッサに動作を実行させるように構成され、前記動作は、
前記第1のシンプルタスクのすべてのイテレーションが完了したかどうかを、前記カーネルイテレーションカウンタの前記データから判定する動作と、
前記第1のシンプルタスクの前記イテレーションのすべてが完了したと判定したことに応じて前記シンプルタスクテーブルの前記エントリを削除する動作とをさらに含む、請求項25に記載の非一時的プロセッサ可読記憶媒体。
【請求項２８】
前記記憶されたプロセッサ実行可能命令は、前記第1のプロセッサに、前記軽量カーネルの実行に関する制限を特定する動作をさらに含む動作を実行させるように構成され、
前記記憶されたプロセッサ実行可能命令は、
前記制限が、メインスレッド、クリティカルスレッド、および非クリティカルスレッドを含む、前記軽量カーネルを実行するための指定されたスレッド、前記軽量カーネルを実行するためのレイテンシ要件、ならびに前記軽量カーネルを記憶するメモリに対する前記第1のスレッドを実行する第2のプロセッサの近接度のうちの1つを含み、
前記軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールする動作が、前記軽量カーネルの実行に関する前記制限に基づいて前記第1のスレッドを選択する動作を含むように前記第1のプロセッサに動作を実行させるように構成される、請求項24に記載の非一時的プロセッサ可読記憶媒体。
【請求項２９】
前記記憶されたプロセッサ実行可能命令は、前記第1のプロセッサに動作を実行させるように構成され、前記動作は、
前記タスクキューにおける第2のタスクポインタが前記軽量カーネルに関する前記シンプルタスクポインタであるかどうかを判定する動作と、
前記第2のタスクポインタが前記シンプルタスクポインタであると判定したことに応じて、前記軽量カーネルに関する第2のシンプルタスクを第2のスレッドによって実行されるようにスケジュールする動作と、
前記シンプルタスクテーブルの前記エントリから前記軽量カーネルに関する前記カーネルポインタを取り出す動作であって、前記エントリが前記シンプルタスクポインタに関連付けられる、動作と、
前記軽量カーネルを前記第2のシンプルタスクとして直ちに実行する動作と、
前記第1のシンプルタスクの第1の出力と前記第2のシンプルタスクの第2の出力を組み合わせる動作とをさらに含む、請求項24に記載の非一時的プロセッサ可読記憶媒体。
【請求項３０】
前記記憶されたプロセッサ実行可能命令は、前記第1のプロセッサに動作を実行させるように構成され、前記動作は、
要求されたプロセスが前記軽量カーネルを含むかどうかを判定する動作と、
前記要求されたプロセスが前記軽量カーネルを含むと判定したことに応じて、前記シンプルタスクテーブルが満杯であるかどうかを判定する動作と、
前記シンプルタスクテーブルが満杯ではないと判定したことに応じて、前記シンプルタスクテーブル内に前記軽量カーネルに関する前記エントリを作成する動作と、
前記エントリに関連する前記シンプルタスクポインタを前記タスクキューに追加する動作と、
前記シンプルタスクテーブルが満杯であると判定したことに応じて、前記軽量カーネルに関連するノーマルタスクポインタを前記タスクキューに追加する動作とをさらに含む、請求項24に記載の非一時的プロセッサ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願は、その内容全体が参照により本明細書に組み込まれる、2015年7月30日に出願した「Method For Simplified Task-based Runtime For Efficient Parallel Computing」と題する米国仮出願第62/198,830号の米国特許法第119条(e)に基づく優先権の利益を主張するものである。
【背景技術】
【０００２】
タスク並列処理は、複数のプロセッサにわたって計算コードが並列化される並列化の一形態である。計算タスクは、並列コンピューティング環境において基本的なスケジュール可能単位として働き、いくつかの入力および出力を有する場合も有さない場合もある計算手順(以下では「カーネル」と呼ぶ)を具現化する。タスクベース並列プログラミングランタイムは、プログラマーがアルゴリズムをタスクの形で表すのを可能にし、スケジューラを使用して複数のプロセッサにわたってタスクを分散させ、同期および負荷分散などの維持機能を実現する。タスクベースランタイムシステムが多くの機能を高度化し実現するにつれて、タスク抽象化がますます複雑になり、タスクの作成、管理、および破壊に顕著なオーバーヘッドが課される。たとえば、タスクベースランタイムシステムでは、タスクの確立、タスクが異種デバイス実行経路に属するかどうかの判定、タスクのライフサイクルを追跡するためのタスク参照および非参照、ならびにスケジューラに対する排他的所有権の要求においてオーバーヘッドが生じる。
【０００３】
タスクを作成し、ディスパッチし、管理するオーバーヘッドが実際の計算と同等であることに起因して、従来のタスクベースランタイムシステムは軽量カーネルに顕著なオーバーヘッドを課す。タスク管理に関連する不可避のオーバーヘッドに起因して性能とエネルギー効率の両方が損なわれる。完全なタスクベースランタイムシステムは、複雑な依存性および同期要件を有する重量カーネルに適している。その理由は、これらの制限に起因して並列化がより低い周波数で行われるからである。
【発明の概要】
【課題を解決するための手段】
【０００４】
様々な実施形態の方法および装置は、コンピューティングデバイスにおいて軽量カーネルをスケジュールし実行するための回路および方法を提供する。様々な実施形態は、タスクキューにおける第1のタスクポインタが軽量カーネルに関するシンプルタスクポインタであるかどうかを判定することと、第1のタスクポインタはシンプルタスクポインタであると判定したことに応じて、軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールすることと、シンプルタスクポインタにあるエントリが関連付けられたシンプルタスクテーブルのこのエントリから軽量カーネルに関するカーネルポインタを取り出すことと、軽量カーネルを第1のシンプルタスクとして直ちに実行することとを含んでもよい。
【０００５】
いくつかの実施形態は、第1のシンプルタスクの実行を完了することと、シンプルタスクテーブルのエントリのカーネルイテレーションカウンタのデータを更新することとをさらに含んでもよい。
【０００６】
いくつかの実施形態は、軽量カーネルのカーネルイテレーションが分割可能であるかどうかを判定することと、軽量カーネルのカーネルイテレーションが分割可能であるという判定に応じて軽量カーネルのカーネルイテレーションをイテレーション部分に分割することとをさらに含んでもよい。そのような実施形態では、軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールすることは、第1のシンプルタスクに軽量カーネルの少なくとも1つのイテレーション部分を割り当てることを含んでもよく、第1のシンプルタスクの実行を完了することは、第1のシンプルタスクに割り当てられた少なくとも1つのイテレーション部分のイテレーションの回数と等しい回数の第1のシンプルタスクの実行を完了することを含んでもよく、シンプルタスクテーブルのエントリのカーネルポインタイテレーションカウンタのデータを更新することは、カーネルイテレーションカウンタのデータを、第1のシンプルタスクに割り当てられた少なくとも1つのイテレーション部分の上記の回数のイテレーションを完了したことを反映するように更新することを含んでもよい。
【０００７】
いくつかの実施形態は、カーネルイテレーションカウンタのデータから第1のシンプルタスクのすべてのイテレーションが完了したかどうかを判定することと、第1のシンプルタスクのイテレーションのすべてが完了したと判定したことに応じてシンプルタスクテーブルのエントリをクリアすることとをさらに含んでもよい。
【０００８】
いくつかの実施形態は、軽量カーネルの実行に関する制限を特定することをさらに含んでもよい。そのような実施形態において、制限には、メインスレッド、クリティカルスレッド、および非クリティカルスレッドを含む、軽量カーネルを実行するための指定されたスレッド、軽量カーネルを実行するためのレイテンシ要件、ならびに軽量カーネルを記憶するメモリに対する第1のスレッドを実行するプロセッサの近接度のうちの1つを含めてもよい。そのような実施形態では、軽量カーネルに関する第1のシンプルタスクを第1のスレッドによって実行されるようにスケジュールすることは、軽量カーネルの実行に関する制限に基づいて第1のスレッドを選択することを含んでもよい。
【０００９】
いくつかの実施形態は、タスクキューにおける第2のタスクポインタが軽量カーネルに関するシンプルタスクポインタであるかどうかを判定することと、第2のタスクポインタはシンプルタスクポインタであると判定したことに応じて、軽量カーネルに関する第2のシンプルタスクを第2のスレッドによって実行されるようにスケジュールすることと、シンプルタスクポインタにあるエントリが関連付けられたシンプルタスクテーブルのこのエントリから軽量カーネルに関するカーネルポインタを取り出すことと、軽量カーネルを第2のシンプルタスクとして直ちに実行することとをさらに含んでもよい。
【００１０】
いくつかの実施形態は、第1のシンプルタスクの第1の出力と第2のシンプルタスクの第2の出力を組み合わせることをさらに含んでもよい。
【００１１】
いくつかの実施形態は、要求されたプロセスが、軽量カーネルを含むかどうかを判定することと、要求されたプロセスが軽量カーネルを含むと判定したことに応じてシンプルタスクテーブルが満杯であるかどうかを判定することと、シンプルタスクテーブルが満杯ではないと判定したことに応じてシンプルタスクテーブルにおける軽量カーネルに関するエントリを作成することと、エントリに関連するシンプルタスクポインタをタスクキューに追加することと、シンプルタスクテーブルが満杯であると判定したことに応じて軽量カーネルに関連するノーマルタスクポインタをタスクキューに追加することとをさらに含んでもよい。
【００１２】
様々な実施形態は、上述の実施形態方法のうちの1つまたは複数の実施形態方法の動作を実行するためのプロセッサ実行可能命令で構成されたプロセッサを含むコンピューティングデバイスを含んでもよい。
【００１３】
様々な実施形態は、上述の実施形態方法のうちの1つまたは複数の実施形態方法の機能を実行するための手段を有するコンピューティングデバイスを含んでもよい。
【００１４】
様々な実施形態は、上述の実施形態方法のうちの1つまたは複数の実施形態方法の動作をコンピューティングデバイスのプロセッサに実行させるように構成された、プロセッサ実行可能命令を記憶している、非一時的プロセッサ可読記憶媒体を含んでもよい。
【００１５】
本明細書に組み込まれ、本明細書の一部を構成する添付の図面は、本発明の例示的な態様を示し、上記の概略的な説明および下記の詳細な説明とともに、本発明の特徴を説明するのに役立つ。
【図面の簡単な説明】
【００１６】
【図１】様々な実施形態を実装するのに適したコンピューティングデバイスを示す構成要素ブロック図である。
【図２】様々な実施形態を実装するのに適した例示的なマルチコアプロセッサを示す構成要素ブロック図である。
【図３】様々な実施形態を実装するのに適した例示的なシステムオンチップ(SoC)を示す構成要素ブロック図である。
【図４】様々な実施形態による例示的なタスクキューの図である。
【図５】様々な実施形態による例示的なシンプルタスクテーブルの図である。
【図６】様々な実施形態によるランタイムシンプルタスクスケジューリングおよび実行を示すプロセスフロー図である。
【図７】シンプルタスクをキューに入れるための一実施形態方法を示すプロセスフロー図である。
【図８】シンプルタスクをスケジュールするための一実施形態方法を示すプロセスフロー図である。
【図９】シンプルタスクを実行するための実施形態方法を示すプロセスフロー図である。
【図１０】様々な実施形態とともに使用するのに適した例示的なモバイルコンピューティングデバイスを示す構成要素ブロック図である。
【図１１】様々な実施形態とともに使用するのに適した例示的なモバイルコンピューティングデバイスを示す構成要素ブロック図である。
【図１２】様々な実施形態とともに使用するのに適した例示的なサーバを示す構成要素ブロック図である。
【発明を実施するための形態】
【００１７】
添付の図面を参照しながら、様々な態様について詳細に説明する。可能な場合はいつでも、同じまたは同様の部分を指すために、図面全体にわたって同じ参照番号が使用される。特定の例および実装形態への言及は例示のためであり、本発明の範囲または特許請求の範囲を限定するものではない。
【００１８】
「コンピューティングデバイス」および「モバイルコンピューティングデバイス」という用語は、セルラー電話、スマートフォン、パーソナルまたはモバイルマルチメディアプレーヤ、携帯情報端末(PDA)、ラップトップコンピュータ、タブレットコンピュータ、スマートブック、ウルトラブック、パームトップコンピュータ、ワイヤレス電子メール受信機、マルチメディアインターネット対応セルラー電話、ワイヤレスゲームコントローラ、ならびに、メモリおよびマルチコアプログラマブルプロセッサを含む同様のパーソナル電子デバイスのうちのいずれか1つまたはすべてを指すために本明細書で互換的に使用される。様々な態様は、限られたメモリおよびバッテリリソースを有するスマートフォンなどのモバイルコンピューティングデバイスに特に有用であるが、本態様は一般に、複数のメモリデバイスおよび限られた電力バジェットを実装する任意の電子デバイスにおいて有用であり、この場合、プロセッサの電力消費を低減することで、モバイルコンピューティングデバイスのバッテリ動作時間を延ばすことができる。
【００１９】
「システムオンチップ」(SoC)という用語は、通常、限定はしないが、ハードウェアコア、メモリ、および通信インターフェースを含む相互接続された電子回路のセットを指すために本明細書で使用される。ハードウェアコアは、汎用プロセッサ、中央処理ユニット(CPU)、デジタル信号プロセッサ(DSP)、グラフィックス処理ユニット(GPU)、加速処理ユニット(APU)、補助プロセッサ、シングルコアプロセッサ、およびマルチコアプロセッサなどの様々な異なるタイプのプロセッサを含んでもよい。ハードウェアコアは、フィールドプログラマブルゲートアレイ(FPGA)、特定用途向け集積回路(ASIC)、他のプログラマブル論理デバイス、個別ゲート論理、トランジスタ論理、性能監視ハードウェア、ウォッチドッグハードウェア、および時間基準などの、他のハードウェアおよびハードウェアの組合せをさらに具現化してもよい。集積回路は、集積回路の構成要素がシリコンなどの単体の半導体材料上に存在するように構成されてもよい。
【００２０】
現代のコンピューティングデバイス上で実行されるように構成された多くのアプリケーションは、依存性および同期要件が容易に満たされる、高度に並列化可能な軽量計算手順(以下では「カーネル」と呼ぶ)を必要とする。たとえば、いくつかのアプリケーションは、各イテレーションの計算量が非常に少ないバックツーバックループの実行を含む。従来のタスクベースランタイムシステムにおけるタスクを作成しディスパッチし管理するオーバーヘッドは、そのような軽量カーネルの並列化に顕著なオーバーヘッドを課す。その理由は、このオーバーヘッドが実際の計算と同等であり、かつ並列化が高速に行われる場合があるからである。
【００２１】
様々な実施形態は、ランタイムにおける通常のタスク管理段階を省略し、通常のタスク管理に関連するオーバーヘッドを低減させるシンプルタスク管理方法を含む。ランタイム管理シンプルタスクテーブルによって簡略化されたタスク管理が実現されてもよい。シンプルタスクテーブルの各エントリは、軽量カーネルに対するポインタを記憶してもよい。シンプルタスクテーブル内のエントリへのシンプルタスクポインタによってシンプルタスクが表されてもよい。この機構は、既存のスケジューリング論理を侵害せずにランタイムスケジューラのジョブを簡略化してもよい。スケジューラが、任意のノーマルタスクの場合と同様にタスクキューからタスクポインタを取り込んでもよい。タスクポインタは、ノーマルタスクにキャストされるノーマルタスクポインタであってもよく、スケジューラはノーマル手順を使用してノーマルタスクをスケジュールしてもよい。タスクポインタは、軽量カーネルに関するカーネルポインタのシンプルタスクテーブル内のエントリにキャストされるシンプルタスクポインタであってもよい。シンプルタスクポインタについては、スケジューラは、プロセッサまたはプロセッサコアによってシンプルタスクとして直ちに実行されるように軽量カーネルをスレッドに割り当ててもよい。シンプルタスクは、スケジューラが、タスクを、シンプルタスクがノーマルタスクであるかのようにスレッドによって実行されるようにスケジュールするのを可能にしてもよいが、シンプルタスクを実行する場合、スレッドは、タスク構造をインスタンス化し、タスクの実行を管理し、タスク構造をディスパッチすることなしに軽量カーネルを直ちに実行してもよい。
【００２２】
図1は、様々な実施形態とともに使用するのに適したリモートコンピューティングデバイス50と通信中のコンピューティングデバイス10を含むシステムを示す。コンピューティングデバイス10は、プロセッサ14、メモリ16、通信インターフェース18、およびストレージメモリインターフェース20を含むSoC12を含んでもよい。コンピューティングデバイス10は、ワイヤードモデムまたはワイヤレスモデムなどの通信構成要素22、ストレージメモリ24、ワイヤレスネットワーク30へのワイヤレス接続32を確立するためのアンテナ26、および/またはインターネット40へのワイヤード接続44に接続するためのネットワークインターフェース28をさらに含んでもよい。プロセッサ14は、様々なハードウェアコアのいずれか、ならびにいくつかのプロセッサコアを含んでもよい。SoC12は、1つまたは複数のプロセッサ14を含んでもよい。コンピューティングデバイス10は、2つ以上のSoC12を含み、それによって、プロセッサ14およびプロセッサコアの数を増加させてもよい。コンピューティングデバイス10はまた、SoC12に関連付けられていない1つまたは複数のプロセッサ14を含んでもよい。個々のプロセッサ14は、図2を参照しながら以下で説明するようなマルチコアプロセッサであってもよい。プロセッサ14は各々、コンピューティングデバイス10の他のプロセッサ14と同じであっても異なっていてもよい特定の目的のために構成されてもよい。同じまたは異なる構成のプロセッサ14およびプロセッサコアのうちの1つまたは複数は、一緒にグループ化されてもよい。プロセッサ14またはプロセッサコアのグループは、マルチプロセッサクラスタと呼ばれてもよい。
【００２３】
SoC12のメモリ16は、プロセッサ14によるアクセスのためにデータおよびプロセッサ実行可能コードを記憶するように構成された、揮発性または不揮発性メモリであってもよい。コンピューティングデバイス10および/またはSoC12は、様々な目的のために構成された1つまたは複数のメモリ16を含んでもよい。様々な実施形態では、1つまたは複数のメモリ16は、ランダムアクセスメモリ(RAM)もしくはメインメモリ、またはキャッシュメモリなど、揮発性メモリを含んでもよい。これらのメモリ16は、不揮発性メモリに対して要求され、様々な因子に基づいて将来アクセスされることを予期して不揮発性メモリからメモリ16にロードされる限られた量のデータおよび/またはプロセッサ実行可能コード命令、ならびに/あるいはプロセッサ14によって生成され、不揮発性メモリには記憶されずに将来迅速にアクセスできるように一時的に記憶される中間処理データおよび/またはプロセッサ実行可能コード命令を一時的に保持するように構成されてもよい。
【００２４】
メモリ16は、プロセッサ14のうちの1つまたは複数によるアクセスのために、別のメモリ16またはストレージメモリ24など、別のメモリデバイスからメモリ16にロードされるプロセッサ実行可能コードを、少なくとも一時的に記憶するように構成されてもよい。メモリ16にロードされたプロセッサ実行可能コードは、プロセッサ14による機能の実行に応答してロードされてもよい。機能の実行に応答してプロセッサ実行可能コードをメモリ16にロードすることは、要求されたプロセッサ実行可能コードがメモリ16内にないために、不成功またはミスであるメモリ16へのメモリアクセス要求から生じる場合がある。ミスに応答して、要求されたプロセッサ実行可能コードを他のメモリデバイスからメモリデバイス16にロードするために、別のメモリデバイスへのメモリアクセス要求が行われてもよい。機能の実行に応答してプロセッサ実行可能コードをメモリ16にロードすることは、別のメモリデバイスへのメモリアクセス要求から生じる場合があり、プロセッサ実行可能コードは、後のアクセスのためにメモリ16にロードされてもよい。
【００２５】
通信インターフェース18、通信構成要素22、アンテナ26、および/またはネットワークインターフェース28は、コンピューティングデバイス10がワイヤレス接続32を介してワイヤレスネットワーク30上でおよび/またはワイヤードネットワーク44上でリモートコンピューティングデバイス50と通信することが可能になるように、調和して動作してもよい。コンピューティングデバイス10が、リモートコンピューティングデバイス50とデータを交換できるようにするためのインターネット40に接続するのを可能にするために、ワイヤレスネットワーク30は、たとえば、ワイヤレス通信用に使用される無線周波数スペクトルを含む様々なワイヤレス通信技術を使用して実装されてもよい。
【００２６】
ストレージメモリインターフェース20およびストレージメモリ24は、コンピューティングデバイス10が不揮発性記憶媒体上にデータとプロセッサ実行可能コードとを記憶することが可能になるように、調和して動作してもよい。ストレージメモリ24は、ストレージメモリ24がプロセッサ14のうちの1つまたは複数によってアクセスするためのデータおよび/またはプロセッサ実行可能コードを記憶してもよいメモリ16の様々な実施形態とほとんど同じに構成されてもよい。不揮発性であるストレージメモリ24は、コンピューティングデバイス10の電源が切断された後でも情報を保持してもよい。電源が再び投入され、コンピューティングデバイス10が再起動すると、コンピューティングデバイス10がストレージメモリ24上に記憶された情報を利用できるようになる。ストレージメモリインターフェース20は、ストレージメモリ24へのアクセスを制御し、プロセッサ14がストレージメモリ24からデータを読み取り、ストレージメモリ24にデータを書き込むことを可能にしてもよい。
【００２７】
コンピューティングデバイス10の構成要素の一部または全部が、異なるように構成され、および/または組み合わされ、しかも必要な機能を果たしてもよい。その上、コンピューティングデバイス10は、構成要素の各々のうちの1つに限定されなくてよく、各構成要素の複数のインスタンスがコンピューティングデバイス10の様々な構成の中に含まれてもよい。
【００２８】
図2は、様々な実施形態を実装するのに適したマルチコアプロセッサ14を示す。図1を参照するとわかるように、マルチコアプロセッサ14は、複数の同種または異種のプロセッサコア200、201、202、203を有してもよい。単一のプロセッサ14のプロセッサコア200、201、202、203が同じ目的のために構成され、同じまたは同様の性能特性を有してもよいという点で、プロセッサコア200、201、202、203は同種であってもよい。たとえば、プロセッサ14は汎用プロセッサであってもよく、プロセッサコア200、201、202、203は同種の汎用プロセッサコアであってもよい。代替的に、プロセッサ14はグラフィックス処理ユニットまたはデジタル信号プロセッサであってもよく、プロセッサコア200、201、202、203はそれぞれ、同種のグラフィックスプロセッサコアまたはデジタル信号プロセッサコアであってもよい。参照しやすいように、「プロセッサ」および「プロセッサコア」という用語は、本明細書で互換的に使用される場合がある。
【００２９】
単一のプロセッサ14のプロセッサコア200、201、202、203が異なる目的のために構成され、ならびに/あるいは異なる性能特性を有してもよいという点で、プロセッサコア200、201、202、203は異種であってもよい。そのような異種のプロセッサコアの例は、より低速で低電力のプロセッサコアがより強力で電力を大量に消費するプロセッサコアと結合される場合がある「big.LITTLE」アーキテクチャとして知られているものを含んでもよい。そのような異種プロセッサコアの異種性には、異なる命令セットアーキテクチャ、パイプライン、動作周波数などを含めてもよい。
【００３０】
図2に示す例では、マルチコアプロセッサ14は、4つのプロセッサコア200、201、202、203(すなわち、プロセッサコア0、プロセッサコア1、プロセッサコア2、およびプロセッサコア3)を含む。説明を簡単にするために、本明細書の例では、図2に示す4つのプロセッサコア200、201、202、203を参照する場合がある。しかしながら、図2に示し、本明細書で説明する4つのプロセッサコア200、201、202、203は単に一例として提示されており、様々な態様を4コアプロセッサシステムに限定するものではない。コンピューティングデバイス10、SoC12、またはマルチコアプロセッサ14は、図示し本明細書で説明する4つのプロセッサコア200、201、202、203よりも少数またはより多数のプロセッサコアを個々にまたは組み合わせて含む場合がある。
【００３１】
さらに、マルチコアプロセッサ14は、プロセッサキャッシュメモリコントローラ204とプロセッサキャッシュメモリ206とを含んでもよい。プロセッサキャッシュメモリ206は、メモリ16と同様に構成されてもよい(図1参照)。プロセッサキャッシュメモリコントローラ204とプロセッサキャッシュメモリ206は、プロセッサコア200、201、202、203が限られた量のデータおよび/またはプロセッサ実行可能コードにアクセスしそれを揮発性記憶媒体上に一時的に保持するのを可能にするように、調和して動作してもよい。プロセッサキャッシュメモリコントローラ204は、プロセッサキャッシュメモリ206へのアクセスを制御し、プロセッサコア200、201、202、203がプロセッサキャッシュメモリ206に対して読取りおよび書込みを行うのを可能にしてもよい。プロセッサコア200、201、202、203は、プロセッサキャッシュメモリ206を共有してもよく、ならびに/あるいは個々のプロセッサコア200、201、202、203は、専用プロセッサキャッシュメモリ206に関連付けられてもよい。プロセッサキャッシュメモリコントローラ204とプロセッサキャッシュメモリ206の単一の対は、説明しやすいように使用されており、マルチコアプロセッサ14上に含まれる場合があるプロセッサキャッシュメモリコントローラ204およびプロセッサキャッシュメモリ206の数を制限するものではない。
【００３２】
図3は、様々な実施形態を実装するのに適した例示的なSoC12を示す。図1、図2、および図3を参照するとわかるように、SoC12は、プロセッサ14と、SoCキャッシュメモリコントローラ300と、SoCキャッシュメモリ302と、メインメモリコントローラ304と、メインメモリ306と、上述のSoC12の構成要素などの他の構成要素とを含んでもよい。SoC12はまた、ストレージメモリコントローラ308およびストレージメモリ24を含むか、またはそれらに通信可能に接続されてもよい。SoC12の構成要素とSoC12に接続された構成要素は、通信バス310を介して互いに接続されてもよい。SoCキャッシュメモリ302、メインメモリ306、およびストレージメモリ24の各々は、データおよび/またはプロセッサ実行可能コードなどのメモリコンテンツを記憶するように構成されてもよい。これらのメモリコンテンツは、SoCキャッシュメモリ302、メインメモリ306、およびストレージメモリ24の物理アドレスによって特定される特定のロケーションに記憶されてもよい。
【００３３】
一態様では、メモリアクセス要求の要求されたメモリコンテンツを取り出すために、それぞれのメモリ24、302、306の物理アドレスに変換される場合がある仮想アドレスを使用して、メモリ24、302、306へのメモリアクセス要求が行われる場合がある。データおよび/またはプロセッサ実行可能コードのいずれかの記憶位置は、時間とともに変化する場合がある。データおよび/またはプロセッサ実行可能コードに関連する物理アドレスは、プロセッサ14によってアクセスできるようにデータおよび/またはプロセッサ実行可能コードのロケーションをマップするデータ構造において更新されてもよい。
【００３４】
SoCキャッシュメモリ302は、メインメモリ306またはストレージメモリ24にアクセスする際に実現可能なアクセスよりも迅速なアクセスが可能になるように、データおよび/またはプロセッサ実行可能コードを一時的に記憶するように構成されてもよい。SoCキャッシュメモリ302は、SoC12における、CPU14a、GPU14b、またはAPU14cなどの単一のプロセッサ14によって使用できるように専用のメモリであってもよく、あるいはCPU14a、GPU14b、およびAPU14cの任意の組合せなどの複数のプロセッサ14、ならびに/あるいはサブシステム(図示せず)間で共有されてもよい。SoCキャッシュメモリ302は、メモリ16(図1参照)およびプロセッサキャッシュメモリ206(図2参照)と同様に構成されてもよい。SoCキャッシュメモリコントローラ300は、SoC12の様々なプロセッサ14a〜14cおよびサブシステム(図示せず)によるSoCキャッシュメモリ302へのアクセスを管理してもよい。SoCキャッシュメモリコントローラ300はまた、プロセッサ14a〜14cによってSoCキャッシュメモリ302に対して要求されるが、SoCキャッシュメモリ302内に見つからず、キャッシュミスになる場合があるメモリコンテンツを取り出すための、SoCキャッシュメモリコントローラ300からメインメモリ306およびストレージメモリ24へのアクセスを求めるメモリアクセス要求を管理してもよい。
【００３５】
メインメモリ306は、ストレージメモリ24にアクセスするときよりも迅速にアクセスできるように、データおよび/またはプロセッサ実行可能コードを一時的に記憶するように構成されてもよい。メインメモリ306は、1つまたは複数のSoC12のプロセッサ14a〜14cおよび/またはSoC12のサブシステム(図示せず)によるアクセスのために利用可能であってもよい。メインメモリコントローラ304は、SoC12およびコンピューティングデバイスの様々なプロセッサ14a〜14cおよびサブシステム(図示せず)によるメインメモリ306へのアクセスを管理してもよい。メインメモリコントローラ304はまた、プロセッサ14a〜14cまたはSoCキャッシュメモリコントローラ300によってメインメモリ306に対して要求されるが、メインメモリ306内に見つからず、メインメモリミスを生じさせる場合があるメモリコンテンツを取り出すための、メインメモリコントローラ304によるストレージメモリ24へのアクセスを求めるメモリアクセス要求を管理してもよい。
【００３６】
ストレージメモリ24は、データおよび/またはプロセッサ実行可能コードを、コンピューティングデバイスが電源投入されていないときに保持されるように永続的記憶するように構成されてもよい。ストレージメモリ24は、SoCキャッシュメモリ302およびメインメモリ306よりも多くの量のデータおよび/またはプロセッサ実行可能コードを記憶し、SoC12のプロセッサ14a〜14cまたはサブシステム(図示せず)によって使用されていないか、または近い将来に使用されることが予測されていないデータおよび/またはプロセッサ実行可能コードを記憶するための容量を有してもよい。ストレージメモリ24は、1つまたは複数のSoC12のプロセッサ14a〜14cおよび/またはSoC12のサブシステム(図示せず)によるアクセスのために利用可能であってもよい。ストレージメモリコントローラ308は、SoC12およびコンピューティングデバイスの様々なプロセッサ14a〜14cおよびサブシステム(図示せず)によるストレージメモリ24へのアクセスを管理してもよい。ストレージメモリコントローラ308はまた、プロセッサ14a〜14cによってSoCキャッシュメモリ302またはメインメモリ306に対して要求されるが、SoCキャッシュメモリ302内にもメインメモリ306内にも見つからず、キャッシュメモリミスまたはメインメモリミスが生じる場合があるメモリコンテンツを取り出すための、SoCキャッシュメモリコントローラ300およびメインメモリコントローラ304からストレージメモリ24へのアクセスを求めるメモリアクセス要求を管理してもよい。
【００３７】
SoC12の構成要素の一部または全部が、異なるように構成されならびに/あるいは組み合わされ、しかも必要な機能を果たしてもよい。その上、SoC12は、構成要素の各々の1つに限定されなくてもよく、各構成要素の複数のインスタンスが、SoC12の様々な構成に含まれてもよい。SoC12の様々な実施形態構成は、SoC12から分離されるが、通信バス310を介してSoC12に接続された、CPU14a、GPU14b、APU14c、メインメモリコントローラ304、およびメインメモリ306などの構成要素を含んでもよい。様々な実施形態構成は、任意の単一のプロセッサ14、またはプロセッサ14の同種もしくは異種の組合せを含むプロセッサ14の組合せを含んでもよい。同様に、コンピューティングデバイス10(図1)は、任意のSoC12、またはSoC12の同種もしくは異種の組合せを含むSoC12の組合せを含んでもよい。
【００３８】
図4は、様々な実施形態によるタスクキュー400の一例を示す。図1〜図4を参照するとわかるように、タスクキュー400は、プロセッサによって実行されるようにスケジュールすべき様々なプロセスのタスクをスケジューラに示すためのタスクポインタの集合およびまとまりを含んでもよい。タスクキュー400は、プロセッサ14によって実行されるスケジューラによってアクセスすることのできる、様々な形のメモリ16、24、206、306、またはレジスタなどの専用ハードウェアとして実装されてもよい。様々な実施形態では、1つまたは複数のスケジューラおよびタスクキュー400は、プロセッサおよびSoCのグループのためのコンピューティングデバイス10上に実装されてもよい。タスクキュー400は、ノーマルタスクポインタとシンプルタスクポインタとを含む、様々なタスクポインタを記憶するように構成されたスロット402、404、406、408、410を含んでもよい。シンプルタスクポインタは、図5を参照してさらに説明するように軽量カーネルに関するデータエントリにキャストされるように構成されてもよい。ノーマルタスクポインタは、軽量カーネル以外の任意のカーネルに関するメモリ16、24、206、306内のロケーションにキャストされるように構成されてもよい。様々な実施形態では、シンプルタスクポインタおよびノーマルタスクポインタは、他の種類のタスクポインタの値と重複しない値にキャストされてもよい。したがって、スケジューラは、図5を参照しながらさらに説明するように、タスクポインタがシンプルタスクポインタであるかそれともノーマルタスクポインタであるかをそれらのキャストされた値によって確認してもよい。
【００３９】
図4に示す例では、タスクキュースロット404はノーマルタスクポインタ(ノーマルタスクポインタ1)を含み、タスクキュースロット402、406、408、および410はシンプルタスクポインタを含む(スロット402がシンプルタスクポインタ1を含み、スロット406および408がシンプルタスクポインタ3を含み、スロット410がシンプルタスクポインタ2を含む)。タスクキュー400は、図示の例における5つのスロット402〜410よりも多いかまたは少ない任意の数のスロットを含んでもよい。
【００４０】
様々な実施形態では、タスクキュー400は、先入れ先出し(FIFO)方式で管理されてもよい。したがって、スケジューラは、最も古いタスクポインタを有する1番上のスロット、この例ではスロット402を読み取ってもよく、1番上のスロットが除去されてもよく、あるいは残りのタスクポインタがタスクキュー400においてそのそれぞれの次のスロットにシフトされるように古いタスクポインタが削除されるかまたは上書きされてもよい。タスクポインタを、それに関連するタスクがスケジュールされるまで除去することも置換することもないポリシーなどの他のタスクキュー管理ポリシーが実装されてもよく、タスクをスケジュールできない場合、実行できないタスクポインタがタスクキュー400内の別のスロット402〜410に移動させられ、またはスケジューラがタスクキュー400内の別のスロット402〜410に一時的にスキップするように、タスクキュー400がシャッフルされる。タスクキュー管理ポリシーは優先順位ベースであってもよく、その場合、優先順位は、タスクの衝突および依存性に基づく場合があるタスクのクリティカリティを含む様々な因子によって決定されてもよい。優先順位は、タスクキュー内の各タスクに割り当てられ、次に読み取られるスロットであるスロットに影響を与える場合があり、あるいは優先順位は、タスクがタスクキュー内で順序付けられる順位に影響を与える場合がある。
【００４１】
図5は、様々な実施形態によるシンプルタスクテーブル500の一例を示す。シンプルタスクテーブル500は、様々な形態のメモリ16、24、206、306内に記憶されたデータの集合およびまとまりを含んでもよい。図5に示し本明細書で説明するシンプルタスクテーブル500のテーブルフォーマットは、データを記憶しまとめるためのフォーマットの例であり、他のデータ構造を使用してデータを記憶しまとめるための他の実施形態に関して制限するものではない。
【００４２】
図5に示す例では、シンプルタスクテーブル500は、たとえば、エントリごとの列502、504、506、または軽量カーネルに関するタスク、すなわちシンプルタスクの行508、510、512、516において、カーネル識別子(ID)、カーネルポインタ、およびカーネルイテレーションカウンタ間の関係をまとめ維持してもよい。カーネル識別子列502は、シンプルタスクテーブル500内のシンプルタスクに関するエントリ508〜516をスケジューラに示すように構成されたカーネル識別子を含んでもよい。スケジューラは、エントリ508〜516のカーネル識別子を使用して、ある軽量カーネルを実行されるようにスケジュールすべきかどうか、どの軽量カーネルを実行されるようにスケジュールすべきか、および軽量カーネルがスケジューラを関連するエントリ508〜516に導くことによって実行を完了したかどうかを確認するのを助けてもよい。シンプルタスクポインタは、最大値がカーネルテーブル内のエントリの数である場合がある整数値にキャストされてもよく、ノーマルタスクポインタは、シンプルタスクの整数値と重複しない16進ポインタ値にキャストされてもよい。スケジューラは、それぞれに異なるポインタにキャストされる様々な値に基づいて、タスクポインタがシンプルタスクポインタであるかそれともノーマルタスクポインタであるかを確認してもよい。図5に示す例では、シンプルタスクポインタにキャストされる値は、シンプルタスクテーブル500内のカーネル識別子であってもよく、たとえば、整数値であってもよく、ノーマルタスクポインタは、物理メモリアドレスまたは仮想メモリアドレスにキャストされてもよく、このアドレスはたとえば、16進値であってもよい。スケジューラは、タスクポインタにキャストされる値に基づいて、タスクポインタがシンプルタスクに関するシンプルタスクポインタであるか、それともノーマルタスクに関するノーマルタスクポインタであるかを判定してもよい。
【００４３】
スケジューラは、カーネル識別子に関連するエントリ508〜516を確認した後、エントリ508〜516について、カーネルポインタ列504からカーネルポインタを読み取り、カーネルイテレーションカウンタ列506からカーネルイテレーションカウンタを読み取ってもよい。カーネルポインタは、シンプルタスクとして実装すべき軽量カーネルを取り込むための物理メモリアドレスまたは仮想メモリアドレスをスケジューラに提示してもよい。カーネルイテレーションカウンタは、シンプルタスクに関して実行すべきカーネル実行イテレーションの総数をスケジューラに提示してもよい。
【００４４】
図5における例では、カーネルイテレーションカウンタ列506は、シンプルタスクに関して実行すべきカーネル実行イテレーションの総数を表す整数値として示されるカーネルイテレーションカウンタ値を含む。様々な実施形態では、カーネルイテレーションカウンタ列506のカーネルイテレーションカウンタ値は、ストリング内の様々な位置が軽量カーネルのそれぞれに異なる特性を表す様々な記号表現のストリングを含んでもよい。たとえば、ストリング内のそれぞれに異なる位置は、シンプルタスクに関して実行すべきカーネル実行イテレーションの総数、シンプルタスクに関して実行すべきカーネル実行イテレーションの総数の除数(たとえば、定数値またはスレッドの利用可能性に依存する値)、シンプルタスクに関して実行されるカーネル実行イテレーションの総数、および軽量カーネルの実行に関する制限を表してもよい。様々な実施形態において、軽量カーネルの実行に関する制限には、メインスレッド、クリティカルスレッド、および非クリティカルスレッドを含む、軽量カーネルを実行するためのスレッドの指定、軽量カーネルを実行するためのレイテンシ要件、ならびに軽量カーネルを記憶するメモリに対するスレッドを実行するプロセッサの近接度を含めてもよい。軽量カーネルに関して実行されるシンプルタスクは、軽量カーネルを実行する前後にカーネルイテレーションカウンタ値を読み取り更新してもよい。
【００４５】
様々な実施形態では、シンプルタスクテーブル500は、グローバルにアクセス可能な集中型シンプルタスクテーブル500またはグローバルであっても、あるいはローカルにアクセス可能な分散型シンプルタスクテーブル500であってもよい。分散型シンプルタスクテーブル500は、軽量カーネルを実行するように指定されたプロセッサ14のメモリ16、24、206、306上などの軽量カーネルの実行デバイスに近接して配置されてもよい。たとえば、GPU14bは、それ自体のメモリ16、24、206、306内の別個のシンプルタスクテーブル500を使用して専用計算タスクを処理してもよい。
【００４６】
様々な実施形態では、シンプルタスクテーブル500は、シンプルタスクに関する単純同期機能を実現してもよい。たとえば、バックツーバックループを実行する場合、複数のシンプルタスクが同じ軽量カーネルを実行してもよい。複数のシンプルタスクに、その完了のために数回のイテレーションが割り当てられてもよく、ループの実行は、すべてのシンプルタスクがその割り当てられたイテレーションを完了した時点で完了してもよい。シンプルタスクがその割り当てられたイテレーションの実行を完了したことに応じてカーネルイテレーションカウンタ内のデータを更新することによって、シンプルタスクテーブル500内のブックキーピングを介してループに関してフォーク-ジョイン同期パターンが実装されてもよい。
【００４７】
図5に示す例は、シンプルタスクテーブル500内のN個のエントリ508〜516を含む。様々な実施形態では、Nの値は様々な数に制限されてもよい。シンプルタスクテーブル500は、シンプルタスクテーブル500内にN個のエントリ508〜516があるときに満杯になる場合があり、既存のエントリ508〜516に関連する軽量カーネルに関するイテレーションの総数の実行が完了することに基づいて既存のエントリ508〜516が無効化または除去されるまでシンプルタスクテーブルにさらなるエントリが追加されることがなくなる場合がある。その結果、利用可能な空間がなくなることに起因して軽量カーネルがシンプルタスクテーブル500に入力されなくなる場合があり、これらの入力されない軽量カーネルはノーマルタスクとして実行されてもよい。
【００４８】
図6は、様々な実施形態によるランタイムシンプルタスクスケジューリングおよび実行のプロセスフローの図である。スケジューラ600およびスレッド602は、コンピューティングデバイスにおける任意のプロセッサまたはプロセッサ14の組合せによって実行されてもよい。いくつかの実施形態では、スケジューラ600は、専用ハードウェアにおいて実装されてもよい。参照しやすいように、スケジューラモジュールならびに専用スケジューラハードウェアを実行するプロセッサを総称的にスケジューラ600と呼ぶ。さらに、タスクキュー400、シンプルタスクテーブル500、および軽量カーネル604は、コンピューティングデバイスのメモリ16、24、206、306の任意の組合せ上に記憶されてもよい。様々な実施形態では、タスクキュー400、シンプルタスクテーブル500、および軽量カーネル604は、レイテンシを短縮し、軽量カーネル604を実行するためのリソース要件を軽減するために、スケジューラ600およびスレッド602を実行するプロセッサ14の組合せに近接してメモリ16、24、206、306の任意の組合せ上に記憶されてもよい。様々な実施形態では、複数のスケジューラ600、スレッド602、タスクキュー400、シンプルタスクテーブル500、および軽量カーネル604はコンピューティングデバイス上に実装されてもよい。
【００４９】
図6に示す例示的な実施形態では、スケジューラ600は、タスクキュー400にアクセスし、タスクキュー606のスロットを読み取ってシンプルタスクポインタ608を取り込んでもよい。スケジューラ600は、シンプルタスクポインタの方向に従って、シンプルタスクテーブル500にアクセスし、シンプルタスクポインタ610によって指定されたエントリを読み取り、エントリ612のデータを取り込んでもよく、エントリ612のデータは、カーネルポインタとカーネルイテレーションカウンタ値とを含んでもよい。スケジューラ600は、シンプルタスクを実行するための利用可能なスレッド602を特定し、シンプルタスク614を実行するための命令をスレッド602に渡してもよい。これらの命令には、軽量カーネル604を(ノーマルタスクではなく)シンプルタスクとして実行するための命令、カーネルポインタ、およびシンプルタスクに関して実行すべきカーネル実行イテレーションの回数を含んでもよい。スケジューラ600は、軽量カーネルを実行するためのスレッドを選択する際に、カーネルイテレーションカウンタデータに示される場合がある、軽量カーネルの実行に対して課される制限を考慮に入れてもよい。スレッド602は、受信された命令から得た情報を使用してメモリにアクセスし、カーネルポインタによって指定されたメモリロケーション616を読み取り、メモリロケーション618から軽量カーネル604を取り出してもよい。スレッド602は、軽量カーネルをシンプルタスク620として直ちに実行してもよい。スレッド602は、シンプルタスクテーブル500にアクセスし、実行されたシンプルタスク622に関するエントリを更新してもよく、この更新は、カーネルイテレーションカウンタ値のデータを更新するか、またはエントリを無効化または削除することを含んでもよい。
【００５０】
図7は、シンプルタスクをキューに入れるための実施形態方法700を示す。方法700は、プロセッサまたはプロセッサコアなどの汎用ハードウェアにおいて実行されるソフトウェアを使用するコンピューティングデバイス、専用ハードウェア、あるいはプロセッサにおいて実行されるソフトウェアと専用ハードウェアとの組合せにおいて実行されてもよい。
【００５１】
ブロック702において、コンピューティングデバイスは、プロセスの実行を求める要求を受信してもよい。この要求は、コンピューティングデバイス上で実行されるオペレーティングシステムまたはプログラムからの呼出しを含むか、あるいはコンピューティングデバイス上でトリガされるハードウェア信号から解釈されてもよい。
【００５２】
判定ブロック704において、コンピューティングデバイスは、プロセスの計算手順がシンプルタスクとして実行することができる軽量カーネルであるかどうかを判定してもよい。様々な実施形態では、軽量カーネルであるプロセスの要素は、軽量カーネルとして識別可能であるように事前プログラムされてもよく、コンピューティングデバイスは、実行することを要求されたプロセスの軽量カーネルについて通知されてもよい。様々な実施形態では、コンピューティングデバイスは、計算手順のタイプを軽量カーネルとして特定するように事前プログラムされてもよく、コンピューティングデバイスは、実行することを要求されたプロセスの要素を検査して、要素のいずれかが軽量カーネルを示すタイプであるかどうかを判定してもよい。
【００５３】
コンピューティングデバイスは、実行することを要求されたプロセスが、シンプルタスクとして実行することができる軽量カーネルを含まないと判定した(すなわち、判定ブロック704=「No」)ことに応じて、ブロック718において、カーネルが実行されるようにタスクキューにノーマルタスクポインタを追加してもよい。
【００５４】
コンピューティングデバイスは、実行することを要求されたプロセスが、シンプルタスクとして実行することができる軽量カーネルを含むと判定した(すなわち、判定ブロック704=「Yes」)ことに応じて、判定ブロック706において、軽量カーネルに関するエントリがシンプルタスクテーブル内に存在するかどうかを判定してもよい。シンプルタスクテーブル内に軽量カーネルに関するエントリがあるかどうかを検査することは、シンプルタスクテーブル内のカーネルポインタにキャストされたメモリロケーションを軽量カーネルのメモリロケーションと比較することを含んでもよい。
【００５５】
コンピューティングデバイスは、軽量カーネルに関するエントリがシンプルタスクテーブル内に存在すると判定した(すなわち、判定ブロック706=「Yes」)ことに応じて、判定ブロック708において、既存のエントリが軽量カーネルの要求された実行に適しているかどうかを判定してもよい。様々な実施形態では、カーネルイテレーションカウンタ内に表される関連するデータによって示される軽量カーネルの実行に関する様々な特性に基づいて、軽量カーネルのいくつかの実行が軽量カーネルの他の実行とは異なってもよい。コンピューティングデバイスは、軽量カーネルの一致するカーネルポインタに関連するカーネルイテレーションカウンタ内に表される軽量カーネルの実行に関する特性を使用して、軽量カーネルに関するエントリが、軽量カーネルの要求された実行に関するシンプルタスクポインタにキャストされるのに適しているかどうかを判定してもよい。
【００５６】
コンピューティングデバイスは、既存のエントリが軽量カーネルの要求された実行に適していると判定した(すなわち、判定ブロック708=「Yes」)ことに応じて、ブロック710においてシンプルタスクテーブル内の軽量カーネルに関する既存のエントリを更新してもよい。既存のエントリを更新することは、軽量カーネルの実行のイテレーション回数など、カーネルイテレーションカウンタ内に表される関連するデータによって示される軽量カーネルを実行するための特性データを更新することを含んでもよい。
【００５７】
コンピューティングデバイスは、シンプルタスクテーブル内には軽量カーネルに関するエントリが存在しないと判定した(すなわち、判定ブロック706=「No」)ことに応答するか、あるいはあるエントリが軽量カーネルの実行に適していないと判定した(すなわち、判定ブロック708=「No」)ことに応じて、判定ブロック714において、シンプルタスクテーブルが満杯であるかどうかを判定してもよい。シンプルタスクテーブルは、N個のエントリを保持することができる制限されたサイズを有してもよい。コンピューティングデバイスは、既存のエントリの数をシンプルタスクテーブルの容量と比較して、シンプルタスクテーブルにさらなるエントリが追加されてもよいかどうかを判定してもよい。
【００５８】
コンピューティングデバイスは、シンプルタスクテーブルが満杯であると判定した(すなわち、判定ブロック714=「Yes」)ことに応じて、ブロック718において、軽量カーネルに関するタスクキューにノーマルタスクポインタを追加してもよい。
【００５９】
コンピューティングデバイスは、シンプルタスクテーブルが満杯ではないと判定した(すなわち、判定ブロック714=「No」)ことに応じて、ブロック716において、シンプルタスクテーブル内に軽量カーネルに関するエントリを作成してもよい。コンピューティングデバイスは、シンプルタスクとして実行される軽量カーネルを示す一意のカーネル識別子を含む新しいエントリおよびシンプルタスクテーブル内のこのエントリのロケーション、軽量カーネルに関する物理メモリロケーションまたは仮想メモリロケーションへのカーネルポインタ、ならびに軽量カーネルの実行に関する特性を指定するカーネルイテレーションカウンタデータを作成してもよい。
【００６０】
ブロック712において、コンピューティングデバイスは、ブロック710において更新されるかあるいはブロック716において作成されたシンプルタスクポインタを、軽量カーネルに関するシンプルタスクテーブル内の既存のエントリに関するタスクキューに追加してもよい。シンプルタスクポインタは、既存のエントリに関するカーネル識別子にキャストされてもよい。
【００６１】
図8は、シンプルタスクをスケジュールするための実施形態方法800を示す。方法800は、プロセッサまたはプロセッサコアなどの汎用ハードウェアにおいて実行されるソフトウェアを使用するコンピューティングデバイス、専用ハードウェア、あるいはプロセッサにおいて実行されるソフトウェアと専用ハードウェアとの組合せにおいて実行されてもよい。
【００６２】
ブロック802において、コンピューティングデバイスは、タスクキューからポインタを取り出してもよい。取り出されるポインタは、本明細書において説明するような先入れ先出しタスクキュー管理ポリシー、利用可能性ベースのタスクキュー管理ポリシー、優先順位ベースのタスクキュー管理ポリシー、またはこれらのタスクキュー管理ポリシーの組合せを含む場合があるタスクキュー管理ポリシーによって規定されてもよい。
【００６３】
判定ブロック804において、コンピューティングデバイスは、取り出されたポインタがシンプルタスクポインタであるかどうかを判定してもよい。シンプルタスクポインタおよびノーマルタスクポインタは、他の種類のタスクポインタの値と重複しない値にキャストされてもよく、それによって、タスクポインタがシンプルタスクポインタであるかそれともノーマルタスクポインタであるかをそのキャストされた値によって確認することが可能になる。様々な実施形態では、シンプルタスクポインタにキャストされる値は、シンプルタスクテーブル内のカーネル識別子であってもよく、たとえば、整数値であってもよく、ノーマルタスクポインタは、物理メモリアドレスまたは仮想メモリアドレスにキャストされてもよく、このアドレスはたとえば、16進値であってもよい。コンピューティングデバイスは、タスクポインタにキャストされる値に基づいて、タスクポインタがシンプルタスクに関するシンプルタスクポインタであるか、それともノーマルタスクに関するノーマルタスクポインタであるかを判定してもよい。
【００６４】
コンピューティングデバイスは、取り出されたポインタがシンプルタスクポインタではないと判定した(すなわち、判定ブロック804=「No」)ことに応じて、ブロック818において、ノーマルタスクを作成し、そのノーマルタスクを実行されるようにスレッドに割り当ててもよい。
【００６５】
コンピューティングデバイスは、取り出されたポインタがシンプルタスクポインタであると判定した(すなわち、判定ブロック804=「Yes」)ことに応じて、ブロック806において、シンプルタスクテーブルからシンプルタスクポインタに関連するエントリを取り出してもよい。本明細書で説明するように、シンプルタスクポインタは、シンプルタスクテーブル内のエントリのカーネル識別子にキャストされてもよく、したがって、コンピューティングデバイスは、取り出されたシンプルタスクポインタにキャストされた値と一致するカーネル識別子を有するシンプルタスクテーブルのエントリを取り出してもよい。エントリを取り出すことはまた、カーネルポインタおよびそのエントリのカーネルイテレーションカウンタのデータを取り出すことを含んでもよい。
【００６６】
ブロック808において、コンピューティングデバイスは、シンプルタスクポインタに関連するエントリの軽量カーネルの実行に関する制限を特定してもよい。説明したように、軽量カーネルの実行に関する制限は、総カーネルイテレーションのデータに含められてもよい。コンピューティングデバイスは、総カーネルイテレーションのデータにおける指定されたロケーションを制限の記号表現に関して調べてもよい。このような制限には、メインスレッド、クリティカルスレッド、および非クリティカルスレッドを含む、軽量カーネルを実行するためのスレッドの指定、軽量カーネルを実行するためのレイテンシ要件、ならびに軽量カーネルを記憶するメモリに対するスレッドを実行するプロセッサの近接度を含めてもよい。
【００６７】
ブロック810において、コンピューティングデバイスは、軽量カーネルをシンプルタスクとして実行し、ノーマルタスクを作成せずに軽量カーネルを直ちに実行するための利用可能なスレッドを特定してもよい。利用可能なスレッドを特定する場合、利用可能なスレッドが、軽量カーネルの実行に関する何らかの制限を満たすかどうかを考慮に入れてもよい。
【００６８】
判定ブロック812において、シンプルタスクとして実行すべきカーネルイテレーションが分割可能であるかどうかを判定してもよい。説明したように、シンプルタスクに関して実行すべきカーネル実行イテレーションの総数、およびシンプルタスクに関して実行すべきカーネル実行イテレーションの総数の除数は、総カーネルイテレーションのデータに含められてもよい。コンピューティングデバイスは、カーネル実行イテレーションの総数およびカーネル実行イテレーションの総数の除数に関する総カーネルイテレーションのデータにおける指定されたロケーションを調べて、カーネルイテレーションが分割可能であるか、およびカーネルイテレーションを利用可能なスレッドに割り当てるにはカーネルイテレーションをどのように分割すべきかを判定してもよい。
【００６９】
コンピューティングデバイスは、シンプルタスクとして実行すべきカーネルイテレーションが分割可能であると判定した(すなわち、判定ブロック812=「Yes」)ことに応じて、ブロック814においてシンプルタスクとして実行される総イテレーションをカーネルイテレーション部分に分割してもよい。様々な実施形態では、カーネルイテレーション部分は、カーネルイテレーションを利用可能なスレッドにわたって対称的または非対称的に拡散させるような部分であってもよい。様々な実施形態では、カーネルイテレーション部分は、利用可能なスレッドの数よりも多いか、またはその数に等しいか、またはその数よりも少ないいくつかのカーネルイテレーション部分における総イテレーションのすべてを考慮に入れるような部分であってもよい。
【００７０】
コンピューティングデバイスは、シンプルタスクとして実行すべきカーネルイテレーションが分割可能ではないと判定した(すなわち、判定ブロック812=「No」)ことに応じて、あるいはシンプルタスクとして実行される総イテレーションをカーネルイテレーション部分に分割した後、ブロック816において、シンプルタスクとして実行すべきカーネルイテレーション部分のうちのいくつかまたはすべてを1つまたは複数の利用可能なスレッドに割り当ててもよい。実行されるカーネルイテレーション部分を割り当てる場合、利用可能なスレッドが、軽量カーネルの実行に関する何らかの制限を満たすかどうかを考慮に入れてもよい。
【００７１】
図9は、シンプルタスクを実行するための実施形態方法900を示す。方法900は、プロセッサまたはプロセッサコアなどの汎用ハードウェアにおいて実行されるソフトウェアを使用するコンピューティングデバイス、専用ハードウェア、あるいはプロセッサにおいて実行されるソフトウェアと専用ハードウェアとの組合せにおいて実行されてもよい。
【００７２】
ブロック902において、コンピューティングデバイスは、軽量カーネルを取り出してもよい。コンピューティングデバイスは、シンプルタスクポインタに関連するエントリのカーネルポインタを使用して、カーネルポインタにキャストされたメモリロケーションから軽量カーネルを取り出してもよい。
【００７３】
ブロック904において、コンピューティングデバイスは、軽量カーネルをシンプルタスクとして実行してもよい。コンピューティングデバイスは、取り出された軽量カーネルを使用してもよく、最初にノーマルタスクの構成を作成することなしに軽量カーネルを直ちに実行し、それによって、実行時にノーマルタスクの衝突および依存性を管理する必要をなくし、完了時にノーマルタスクをディスパッチするのを回避することによって、スレッドへのシンプルタスクの割当てに対応してもよい。したがって、軽量カーネルの実行はタスクと同様にスケジュールされてもよく、具体的にはシンプルタスクを使用してスケジュールされてもよいが、軽量カーネルをシンプルタスクとして実行するとノーマルタスクをスケジュールし実行するのに必要なリソース消費におけるオーバーヘッドが回避される。
【００７４】
ブロック906において、コンピューティングデバイスは、ローカルイテレーションカウンタをカーネルイテレーション部分が実行されるように更新してもよい。ローカルイテレーションカウンタを更新することは、増分すること、減分すること、またはカーネルイテレーション部分において実行されたカーネルイテレーションもしくはまだ実行されていないカーネルイテレーションの回数を示すアルゴリズムを使用することを含んでもよい。
【００７５】
判定ブロック908において、コンピューティングデバイスは、カーネルイテレーション部分が完了したかどうかを判定してもよい。様々な実施形態では、コンピューティングデバイスは、ローカルイテレーションカウンタにおけるシンプルタスクにおいて実行されたイテレーションの回数をカーネルイテレーション部分のイテレーションの回数と比較してもよく、あるいはローカルイテレーションカウンタがゼロなどの所与の値と等しいかどうかを調べてもよい。コンピューティングデバイスは、カーネルイテレーション部分が完了してないと判定した(すなわち、判定ブロック908=「No」)ことに応じて、説明したように、ブロック904において軽量カーネルをシンプルタスクとして実行し、ブロック906においてローカルイテレーションカウンタをカーネルイテレーション部分が実行されるように更新してもよい。
【００７６】
コンピューティングデバイスは、カーネルイテレーション部分が完了したと判定した(すなわち、判定ブロック908=「Yes」)ことに応じて、ブロック910において、シンプルタスクテーブル内のシンプルタスクに関するエントリの総イテレーションカウンタを更新してもよい。様々な実施形態では、総イテレーションカウンタを更新することは、総イテレーションカウンタのデータにおいて表される完了したカーネルイテレーションの回数に完了したカーネルイテレーション部分のイテレーション回数を追加すること、または総イテレーションカウンタのデータにおける完了すべきカーネルイテレーションの回数から完了したカーネルイテレーション部分のイテレーションの回数を差し引くことを含んでもよい。様々な実施形態では、完了したカーネルイテレーションの回数または完了すべきカーネルイテレーションの回数は、カーネルイテレーションの回数、カーネルイテレーション部分の数、またはカーネルイテレーションもしくはカーネルイテレーション部分を表す記号値によって表されてもよい。
【００７７】
判定ブロック912において、コンピューティングデバイスは、実行すべきカーネルイテレーション部分が残っているかどうかを判定してもよい。実行されないカーネルイテレーション部分は、特定のスレッドに割り当てられるかまたはスレッドのグループに割り当てられてもよい。コンピューティングデバイスは、実行すべきカーネルイテレーション部分が残っていると判定した(すなわち、判定ブロック912=「Yes」)ことに応じて、説明したように、ブロック904において軽量カーネルをシンプルタスクとして実行してもよい。
【００７８】
コンピューティングデバイスは、実行すべきカーネルイテレーション部分は残っていないと判定した(すなわち、判定ブロック912=「No」)ことに応じて、判定ブロック914において、あるカーネルイテレーション部分に関して出力されるあるシンプルタスクが別のカーネルイテレーション部分に対して出力される別のシンプルタスクから独立しているかどうかを判定してもよい。このようにして、コンピューティングデバイスは、軽量カーネル実行の単純な同期を管理してもよい。たとえば、コンピューティングデバイスは、単一の出力をもたらす軽量カーネル実行が並列に実行され、それらの出力が実行の完了後に互いに結合され得るように、フォーク-ジョインパラダイムを実装してもよい。
【００７９】
コンピューティングデバイスは、あるカーネルイテレーション部分に関して出力されるあるシンプルタスクが別のカーネルイテレーション部分に関して出力される別のシンプルタスクから独立していないと判定した(すなわち、判定ブロック914=「No」)ことに応じて、ブロック916において、互いに依存するシンプルタスク出力を組み合わせてもよい。
【００８０】
コンピューティングデバイスは、あるカーネルイテレーション部分に関して出力されるあるシンプルタスクが別のカーネルイテレーション部分に関して出力される別のシンプルタスクから独立していると判定した(すなわち、判定ブロック914=「Yes」)ことに応じて、またはブロック916において、互いに依存するシンプルタスク出力を組み合わせた後、ブロック918において、組み合わされたシンプルタスク出力を出力してもよい。ブロック920において、コンピューティングデバイスは、取り出された軽量カーネルに関連するシンプルタスクに関するエントリを、シンプルタスクテーブルにおいて無効化するかまたはシンプルタスクテーブルから消去してもよい。
【００８１】
(限定はしないが、図1〜図9を参照して上記で説明した態様を含む)様々な態様は、図10に示す様々な態様とともに使用するのに適した例示的なモバイルコンピューティングデバイスを含んでもよい多種多様なコンピューティングシステムにおいて実装されてもよい。モバイルコンピューティングデバイス1000は、タッチスクリーンコントローラ1004および内部メモリ1006に結合されたプロセッサ1002を含む場合がある。プロセッサ1002は、汎用または特定の処理タスクに指定された1つまたは複数のマルチコア集積回路であってもよい。内部メモリ1006は、揮発性メモリまたは不揮発性メモリであってもよく、また、セキュアなメモリおよび/もしくは暗号化されたメモリ、またはセキュアでないメモリおよび/もしくは暗号化されていないメモリ、またはそれらの任意の組合せであってもよい。活用されてもよいメモリタイプの例には、限定はしないが、DDR、LPDDR、GDDR、WIDEIO、RAM、SRAM、DRAM、P-RAM、R-RAM、M-RAM、STT-RAM、および埋め込みDRAMが含まれる。タッチスクリーンコントローラ1004およびプロセッサ1002はまた、抵抗感知タッチスクリーン、容量感知タッチスクリーン、赤外線感知タッチスクリーンなどの、タッチスクリーンパネル1012に結合される場合もある。加えて、コンピューティングデバイス1000のディスプレイは、タッチスクリーン機能を有する必要はない。
【００８２】
モバイルコンピューティングデバイス1000は、互いに結合され、かつ/またはプロセッサ1002に結合された、通信を送信および受信するための1つまたは複数の無線信号トランシーバ1008(たとえば、Peanut、Bluetooth(登録商標)、Zigbee、Wi-Fi、RF無線など)と、アンテナ1010とを有する場合がある。トランシーバ1008およびアンテナ1010は、様々なワイヤレス伝送プロトコルスタックおよびインターフェースを実装するために、上述の回路構成とともに使用されてもよい。モバイルコンピューティングデバイス1000は、セルラーネットワークを介する通信を可能にし、かつプロセッサに結合されたセルラーネットワークワイヤレスモデムチップ1016を含む場合がある。
【００８３】
モバイルコンピューティングデバイス1000は、プロセッサ1002に結合された周辺デバイス接続インターフェース1018を含む場合がある。周辺デバイス接続インターフェース1018は、1つのタイプの接続を受け入れるように単独で構成される場合があるか、または、USB、FireWire、Thunderbolt、もしくはPCIeなどの様々なタイプの物理接続および通信接続を共通もしくはプロプライエタリに受け入れるように、構成される場合がある。周辺デバイス接続インターフェース1018は、同様に構成された周辺デバイス接続ポート(図示せず)に結合される場合もある。
【００８４】
モバイルコンピューティングデバイス1000は、オーディオ出力を生成するためのスピーカー1014を含む場合もある。モバイルコンピューティングデバイス1000は、本明細書で説明した構成要素のすべてまたはいくつかを収容するための、プラスチック、金属、または材料の組合せから構築されたハウジング1020を含む場合もある。モバイルコンピューティングデバイス1000は、使い捨てまたは充電可能なバッテリなどの、プロセッサ1002に結合された電源1022を含む場合がある。充電可能なバッテリは、モバイルコンピューティングデバイス1000の外部にある電源から充電電流を受けるために、周辺デバイス接続ポートに結合される場合もある。モバイルコンピューティングデバイス1000は、ユーザ入力を受け取るための物理ボタン1024を含む場合もある。モバイルコンピューティングデバイス1000は、モバイルコンピューティングデバイス1000をオンオフするための電源ボタン1026を含む場合もある。
【００８５】
(限定はしないが、図1〜図9を参照して上記で説明した態様を含む)様々な態様は、図11に示すラップトップコンピュータ1100など、様々なモバイルコンピューティングデバイスを含んでもよい多種多様なコンピューティングシステムにおいて実装されてもよい。多くのラップトップコンピュータは、コンピュータのポインティングデバイスとして働くタッチパッドのタッチ面1117を含み、したがって、タッチスクリーンディスプレイを装備した上述のコンピューティングデバイス上で実装されるものと同様のドラッグジェスチャ、スクロールジェスチャ、およびフリックジェスチャを受信してもよい。ラップトップコンピュータ1100は通常、揮発性メモリ1112、およびフラッシュメモリのディスクドライブ1113などの大容量不揮発性メモリに結合されたプロセッサ1111を含む。加えて、コンピュータ1100は、プロセッサ1111に結合されたワイヤレスデータリンクおよび/または携帯電話トランシーバ1116に接続される場合がある、電磁放射を送受信するための1つまたは複数のアンテナ1108を有する場合がある。コンピュータ1100は、プロセッサ1111に結合されたフロッピーディスクドライブ1114およびコンパクトディスク(CD)ドライブ1115を含む場合もある。ノートブック構成では、コンピュータのハウジングは、すべてがプロセッサ1111に結合された、タッチパッド1117、キーボード1118、およびディスプレイ1119を含む。コンピューティングデバイスの他の構成は、よく知られているように、(たとえば、ユニバーサルシリアルバス(USB)入力を介して)プロセッサに結合されたコンピュータマウスまたはトラックボールを含んでもよく、それらはまた、様々な態様とともに使用されてもよい。
【００８６】
(限定はしないが、図1〜図9を参照して上記で説明した態様を含む)様々な態様は、サーバキャッシュメモリ内にデータを圧縮するための様々な市販のサーバのうちのいずれかを含んでもよい多種多様なコンピューティングシステムにおいて実装されてもよい。例示的なサーバ1200が、図12に示されている。そのようなサーバ1200は通常、揮発性メモリ1202と、ディスクドライブ1204などの大容量不揮発性メモリとに結合された、1つまたは複数のマルチコアプロセッサアセンブリ1201を含む。図12に示すように、マルチコアプロセッサアセンブリ1201は、それらをアセンブリのラックに挿入することによって、サーバ1200に付加されてもよい。サーバ1200はまた、プロセッサアセンブリ1201に結合されたフロッピーディスクドライブ、コンパクトディスク(CD)またはDVDディスクドライブ1206を含んでもよい。サーバ1200はまた、他のブロードキャストシステムコンピュータおよびサーバに結合されたローカルエリアネットワーク、インターネット、公衆交換電話網、ならびに/またはセルラーデータネットワーク(たとえば、CDMA、TDMA、GSM(登録商標)、PCS、3G、4G、LTE、もしくは任意の他のタイプのセルラーデータネットワーク)など、ネットワーク1205とのネットワークインターフェース接続を確立するための、マルチコアプロセッサアセンブリ1201に結合されたネットワークアクセスポート1203を含んでもよい。
【００８７】
様々な態様の動作を実行するためにプログラマブルプロセッサ上で実行するためのコンピュータプログラムコードまたは「プログラムコード」は、C、C++、C#、Smalltalk、Java(登録商標)、JavaScript(登録商標)、Visual Basic、構造化照会言語(たとえば、Transact-SQL)、Perlなどの高水準プログラミング言語、または様々な他のプログラミング言語で書かれてもよい。本出願で使用されるようにコンピュータ可読記憶媒体上に記憶されるプログラムコードまたはプログラムは、そのフォーマットがプロセッサによって理解可能である(オブジェクトコードなどの)機械言語コードを指すことがある。
【００８８】
多くのコンピューティングデバイスのオペレーティングシステムカーネルは、(非特権コードが動作する)ユーザ空間と(特権コードが動作する)カーネル空間とに編成される。この分離は、カーネル空間の一部であるコードが一般公有使用許諾(GPL)を受けなければならない一方で、ユーザ空間内で動作するコードがGPLを受けなくてもよい、Androidおよび他のGPL環境において特に重要である。本明細書で説明する様々なソフトウェア構成要素/モジュールが、明示的に別段の記載がない限り、カーネル空間またはユーザ空間のいずれに実装されてもよいことを理解されたい。
【００８９】
上記の方法説明およびプロセスフロー図は、単に例示的な例として提供され、様々な態様の動作が提示された順序で実行されなければならないことを要求または暗示するものではない。当業者によって諒解されるように、上記の態様における動作の順序は、任意の順序で実行されてもよい。「その後」、「次いで」、「次に」などの単語は、動作の順序を限定するものではなく、これらの単語は、方法の説明を通して読者を導くために使用されるにすぎない。さらに、たとえば、冠詞「a」、「an」、または「the」を使用する単数形での請求項の要素へのいかなる言及も、その要素を単数形に限定するものとして解釈すべきではない。
【００９０】
様々な態様に関して説明した様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズム動作は、電子ハードウェア、コンピュータソフトウェア、または両方の組合せとして実装されてもよい。ハードウェアとソフトウェアとのこの互換性を明確に示すために、様々な例示的な構成要素、ブロック、モジュール、回路、および動作が、概してそれらの機能の観点から上記で説明された。そのような機能がハードウェアとして実装されるのか、それともソフトウェアとして実装されるのかは、特定の適用例および全体的なシステムに課される設計制約で決まる。当業者は説明した機能を特定の用途ごとに様々な方法で実装してもよいが、そのような実装決定は本発明の範囲からの逸脱を引き起こすものと解釈されるべきではない。
【００９１】
本明細書で開示する態様に関して説明した様々な例示的な論理、論理ブロック、モジュール、および回路を実装するために使用されるハードウェアは、汎用プロセッサ、デジタル信号プロセッサ(DSP)、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)もしくは他のプログラマブル論理デバイス、個別ゲートもしくはトランジスタ論理、個別ハードウェア構成要素、または本明細書で説明した機能を実行するように設計されたそれらの任意の組合せを用いて実施または実行されてもよい。汎用プロセッサはマイクロプロセッサであってもよいが、代替として、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、またはステートマシンであってもよい。プロセッサは、コンピューティングデバイスの組合せ(たとえば、DSPとマイクロプロセッサとの組合せ、複数のマイクロプロセッサ、DSPコアと連携した1つもしくは複数のマイクロプロセッサ、または任意の他のそのような構成)として実装される場合もある。代替的に、いくつかの動作または方法は、所与の機能に固有の回路構成によって実行されてもよい。
【００９２】
1つまたは複数の態様では、説明した機能は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組合せで実装されてもよい。ソフトウェアで実装される場合、機能は、非一時的コンピュータ可読媒体または非一時的プロセッサ可読媒体上の1つまたは複数の命令またはコードとして記憶されてもよい。本明細書で開示する方法またはアルゴリズムの動作は、非一時的コンピュータ可読またはプロセッサ可読記憶媒体上に存在してよいプロセッサ実行可能ソフトウェアモジュールで具現化されてもよい。非一時的コンピュータ可読またはプロセッサ可読記憶媒体は、コンピュータまたはプロセッサによってアクセスされることがある任意の記憶媒体であってもよい。限定ではなく例として、そのような非一時的コンピュータ可読またはプロセッサ可読媒体は、RAM、ROM、EEPROM、FLASHメモリ、CD-ROMもしくは他の光ディスクストレージ、磁気ディスクストレージもしくは他の磁気ストレージデバイス、または命令もしくはデータ構造の形態で所望のプログラムコードを記憶するために使用されてもよく、コンピュータによってアクセスされてもよい任意の他の媒体を含んでもよい。本明細書で使用するディスク(disk)およびディスク(disc)は、コンパクトディスク(disc)(CD)、レーザーディスク(登録商標)(disc)、光ディスク(disc)、デジタル多用途ディスク(disc)(DVD)、フロッピーディスク(disk)、およびブルーレイディスク(disc)を含み、ディスク(disk)は、通常、データを磁気的に再生し、ディスク(disc)は、レーザーを用いてデータを光学的に再生する。上記の組合せも、非一時的コンピュータ可読およびプロセッサ可読媒体の範囲に含まれる。追加として、方法またはアルゴリズムの動作は、コンピュータプログラム製品に組み込まれてもよい、非一時的プロセッサ可読媒体および/またはコンピュータ可読媒体上のコードおよび/または命令の1つまたは任意の組合せまたはセットとして存在してもよい。
【００９３】
開示した態様の上述の説明は、いかなる当業者も本発明を作成または使用することができるように提供される。これらの態様に対する様々な修正は当業者に容易に明らかになり、本明細書で定義する一般原理は、本発明の趣旨または範囲から逸脱することなく、他の態様に適用されてもよい。したがって、本発明は、本明細書に示す態様に限定されるものではなく、以下の特許請求の範囲、ならびに、本明細書で開示する原理および新規の特徴と一致する最も広い範囲を与えられるべきである。
【符号の説明】
【００９４】
10  コンピューティングデバイス
12  SoC
14  プロセッサ
14a  CPU
14b  GPU
14c  APU
16  メモリデバイス
18  通信インターフェース
20  ストレージメモリインターフェース
22  通信構成要素
24  ストレージメモリ
26  アンテナ
28  ネットワークインターフェース
30  ワイヤレスネットワーク
32  ワイヤレス接続
40  インターネット
44  ワイヤード接続
50  リモートコンピューティングデバイス
200  プロセッサコア
204  プロセッサキャッシュメモリコントローラ
206  プロセッサキャッシュメモリ
300  SoCキャッシュメモリコントローラ
302  SoCキャッシュメモリ
304  メインメモリコントローラ
306  メインメモリ
308  ストレージメモリコントローラ
310  通信バス
400  タスクキュー
402  タスクキュースロット
404  タスクキュースロット
500  シンプルタスクテーブル
502  カーネル識別子列
504  カーネルポインタ列
506  カーネルイテレーションカウンタ列
508  エントリ
600  スケジューラ
602  スレッド
604  軽量カーネル
606  タスクキュー
608  シンプルタスクポインタ
610  シンプルタスクポインタ
612  エントリ
614  シンプルタスク
616  メモリロケーション
618  メモリロケーション
620  シンプルタスク
622  シンプルタスク
1000  コンピューティングデバイス
1002  プロセッサ
1004  タッチスクリーンコントローラ
1006  内部メモリ
1008  トランシーバ
1012  タッチスクリーンパネル
1016  セルラーネットワークワイヤレスモデムチップ
1018  周辺デバイス接続インターフェース
1020  ハウジング
1022  電源
1024  物理ボタン
1026  電源ボタン
1100  コンピュータ
1111  プロセッサ
1112  揮発性メモリ
1113  ディスクドライブ
1114  フロッピーディスクドライブ
1115  コンパクトディスクドライブ
1116  ワイヤレスデータリンクおよび/または携帯電話トランシーバ
1117  タッチパッド
1118  キーボード
1119  ディスプレイ
1200  サーバ
1201  プロセッサ、マルチコアプロセッサアセンブリ
1202  揮発性メモリ
1203  ネットワークアクセスポート
1204  ディスクドライブ
1205  ネットワーク
1206  DVDディスクドライブ
【図１】
2018528515.tif 000003
【図２】
2018528515.tif 000004
【図３】
2018528515.tif 000005
【図４】
2018528515.tif 000006
【図５】
2018528515.tif 000007
【図６】
2018528515.tif 000008
【図７】
2018528515.tif 000009
【図８】
2018528515.tif 000010
【図９】
2018528515.tif 000011
【図１０】
2018528515.tif 000012
【図１１】
2018528515.tif 000013
【図１２】
2018528515.tif 000014
【国際調査報告】
2018528515.tif 000015
2018528515.tif 000016