JP5544856B2 - 調停装置、調停方法及びプログラム - Google Patents

Description

本発明は、調停装置、調停方法及びプログラムに関する。

半導体技術の進歩により、集積率の高いＬＳＩ（Ｌａｒｇｅ Ｓｃａｌｅ Ｉｎｔｅｇｒａｔｉｏｎ）が開発されてきた。しかし、消費電力の増加により、集積率のさらなる向上によってＬＳＩの性能を向上させることが困難になってきている。そこで、ＬＳＩのプロセッサコア数を増やし、動作周波数を低く抑えることで消費電力の増加を抑え、複数のプロセッサコアの並列度によってスループットを向上させるマルチコア構成が用いられている。

マルチコア構成によるＬＳＩにおいてコア同士を接続するルータとしては、プロセッサコアをリング状に接続するリングバス方式のルータや、プロセッサコア間にクロスバを設けてそれぞれのプロセッサコアを接続するクロスバ方式のルータが用いられている。このようなオンチップのルータ（特にクロスバ方式のルータ）の処理は、リクエストパケットからの情報の取得、出力ポートの設定、クロスバ調停の実施、及び出力ポートへの転送を行う必要があり、これらの処理は、３段乃至４段のパイプライン処理によって行われる。

クロスバの調停方法として、競合したリクエストパケットをランダムに選択するランダム選択方式、競合したリクエストパケットを順に選択するラウンドロビン選択方式、予め決められた優先順位の順に競合したリクエストパケットを選択する優先選択方式が用いられている。
なお、特許文献１には、競合したリクエストパケットの調停履歴に基づいてバス調停を行う方法が開示されている。
また、特許文献２には、特定の転送処理に関与するプロセッサコアによるリクエストパケットの出力順序を記録したテーブルを用い、現在資源を使用しているプロセッサコアの次にリクエストパケットを出力するプロセッサコアに対して、優先的に資源を使用させる調停方法が開示されている。

特開２００１−１６７０４９号公報 特開２００８−２９９６２４号公報

上述したランダム選択方式、ラウンドロビン選択方式による調停方法は、各プロセッサコアが均等にリクエストパケットを出力すると仮定してプロセッサコアを選択する方法である。そのため、プロセッサコアごとにリクエストパケットの出力が均等でないアプリケーションを実行した場合、効率的なリクエストパケットの選択ができなくなるという問題がある。また、優先選択方式による調停方法は、予めプロセッサコアの優先順位が決められているため、優先順位の低いプロセッサコアによるリクエストパケットの出力が多いアプリケーションを実行した場合、効率的なリクエストパケットの選択ができなくなるという問題がある。

また、特許文献１、特許文献２に記載の調停方法は、リクエストパケットの調停履歴に基づいて調停を行うが、調停処理の１サイクルあたりに実行する処理内容が多くなるため、調停装置の動作周波数を上げることができず、通信遅延が発生する惧れがある。
本発明は、上記の問題に鑑みてなされたものであり、調停処理の１サイクルあたりの実行処理内容を増加させず、かつ効率的なリクエストパケットの選択を行う調停装置、調停方法及びプログラムを提供することを課題とする。

本発明は上記の課題を解決するためになされたものであり、複数の資源要求装置から発行される、当該資源要求装置による計算資源の使用の要求を示す資源要求の調停を行い、前記資源要求装置と前記計算資源とを接続するクロスバを制御する調停装置であって、複数の前記資源要求装置から資源要求の入力を受け付ける入力部と、前記入力部が同一の前記計算資源に対する資源要求の中から１つを選択し、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する調停部と、前記調停部による処理を実行する前に、前記調停部によって選択される資源要求を予測し、当該資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する予測部と、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、前記クロスバに対して前記予測部による接続命令の実行を中断させる中断命令を出力する中断部と、過去の処理において前記調停部が選択した資源要求を選択した順に調停履歴記憶部に登録する履歴登録部とを備え、前記調停部は、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが同一である場合に、前記クロスバに対する前記接続命令の出力を行わず、前記予測部は、前記調停部による最後の所定の個数の資源要求を選択した順と同じ順に、前記調停履歴記憶部に記憶されている資源要求の直後に登録された資源要求を、前記調停部によって選択される資源要求として予測することを特徴とする。
また、本発明は、複数の資源要求装置から発行される、当該資源要求装置による計算資源の使用の要求を示す資源要求の調停を行い、前記資源要求装置と前記計算資源とを接続するクロスバを制御する調停装置であって、複数の前記資源要求装置から資源要求の入力を受け付ける入力部と、前記入力部が同一の前記計算資源に対する資源要求の中から１つを選択し、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する調停部と、前記調停部による処理を実行する前に、前記調停部によって選択される資源要求を予測し、当該資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する予測部と、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、前記クロスバに対して前記予測部による接続命令の実行を中断させる中断命令を出力する中断部と、前記資源要求装置ごとに、過去の処理において、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが同一となる度合いを示す強度情報を算出する強度情報算出部とを備え、前記調停部は、前記強度情報算出部が算出した強度情報に基づいて、選択する資源要求を決定し、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが同一である場合に、前記クロスバに対する前記接続命令の出力を行わないことを特徴とする。

また、本発明は、複数の資源要求装置から発行される、当該資源要求装置による計算資源の使用の要求を示す資源要求の調停を行い、前記資源要求装置と前記計算資源とを接続するクロスバを制御する調停装置を用いた調停方法であって、入力部は、複数の前記資源要求装置から資源要求の入力を受け付け、調停部は、前記入力部が同一の前記計算資源に対する資源要求の中から１つを選択し、予測部は、前記調停部による処理を実行する前に、前記調停部によって選択される資源要求を予測し、当該資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力し、中断部は、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、前記クロスバに対して前記予測部による接続命令の実行を中断させる中断命令を出力し、履歴登録部は、過去の処理において前記調停部が選択した資源要求を選択した順に調停履歴記憶部に登録し、前記調停部は、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力し、前記予測部は、前記調停部による最後の所定の個数の資源要求を選択した順と同じ順に、前記調停履歴記憶部に記憶されている資源要求の直後に登録された資源要求を、前記調停部によって選択される資源要求として予測することを特徴とする。
また、本発明は、複数の資源要求装置から発行される、当該資源要求装置による計算資源の使用の要求を示す資源要求の調停を行い、前記資源要求装置と前記計算資源とを接続するクロスバを制御する調停装置を用いた調停方法であって、入力部は、複数の前記資源要求装置から資源要求の入力を受け付け、調停部は、前記入力部が同一の前記計算資源に対する資源要求の中から１つを選択し、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力し、予測部は、前記調停部による処理を実行する前に、前記調停部によって選択される資源要求を予測し、当該資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力し、中断部は、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、前記クロスバに対して前記予測部による接続命令の実行を中断させる中断命令を出力し、強度情報算出部は、前記資源要求装置ごとに、過去の処理において、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが同一となる度合いを示す強度情報を算出し、前記調停部は、前記強度情報算出部が算出した強度情報に基づいて、選択する資源要求を決定し、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力することを特徴とする。

また、本発明は、複数の資源要求装置から発行される、当該資源要求装置による計算資源の使用の要求を示す資源要求の調停を行い、前記資源要求装置と前記計算資源とを接続するクロスバを制御する調停装置を、複数の前記資源要求装置から資源要求の入力を受け付ける入力部、前記入力部が同一の前記計算資源に対する資源要求の中から１つを選択し、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する調停部、前記調停部による処理を実行する前に、前記調停部によって選択される資源要求を予測し、当該資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する予測部、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、前記クロスバに対して前記予測部による接続命令の実行を中断させる中断命令を出力する中断部、過去の処理において前記調停部が選択した資源要求を選択した順に調停履歴記憶部に登録する履歴登録部として機能させ、前記調停部は、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが同一である場合に、前記クロスバに対する前記接続命令の出力を行わず、前記予測部は、前記調停部による最後の所定の個数の資源要求を選択した順と同じ順に、前記調停履歴記憶部に記憶されている資源要求の直後に登録された資源要求を、前記調停部によって選択される資源要求として予測することを特徴とする。

本発明によれば、調停部による調停の実行の前に、予測部が、選択される資源要求を予測し、クロスバに当該資源要求を出力させる接続命令を出力する。これにより、調停装置は、調停処理の１サイクルあたりの実行処理内容を増加させずに、効率的な資源要求の選択を行うことができる。

本発明の一実施形態によるクロスバ調停装置の構成を示す概略ブロック図である。 予測回路の構成を示す概略ブロック図である。 調停回路のパイプライン処理の流れを示す図である。 調停装置の動作を示す第１のフローチャートである。 調停装置の動作を示す第２のフローチャートである。 リクエストパケットの調停方法を示す図である。 強度情報の更新方法を示す図である。

以下、図面を参照しながら本発明の実施形態について詳しく説明する。
図１は、本発明の一実施形態によるクロスバ調停装置の構成を示す概略ブロック図である。
クロスバ調停装置は、プロセッサコア及び入出力装置を相互に接続するルータであって、入力ポート１−１〜１−５（以下、入力ポート１−１〜１−５を総称する場合は入力ポート１と表記する）、入力側バッファ部２−１〜２−５（以下、入力側バッファ部２−１〜２−５を総称する場合は入力側バッファ部２と表記する）、調停装置３、クロスバ４、出力側バッファ部５−１〜５−５（以下、出力側バッファ部５−１〜５−５を総称する場合は出力側バッファ部５と表記する）、出力ポート６−１〜６−５（以下、出力ポート６−１〜６−５を総称する場合は出力ポート６と表記する）を備える。

入力ポート１は、それぞれ接続されたプロセッサコアまたは入出力装置（以下、資源要求装置とよぶ）からリクエストパケットを入力し、当該リクエストパケット（資源要求）を、接続された入力側バッファ部２に出力する。なお、本実施形態においては、入力ポート１が資源要求装置から入力するリクエストパケットには、出力先を示す情報及び調停の優先度を示す強度情報が含まれる。
入力側バッファ部２は、接続された入力ポート１からリクエストパケットを入力し、当該リクエストパケットを一時的に蓄えて、リクエストパケットに含まれる強度情報を調停装置３に出力し、リクエストパケット本体をクロスバ４に出力する。

調停装置３は、入力側バッファ部２から入力した強度情報に基づいてリクエストパケットの調停を行い、調停によって選択されたリクエストパケットを出力ポート６に転送させる接続命令をクロスバ４に出力する。また、各プロセッサコアに関連付けられた強度情報を更新し、出力ポート６に出力する。
クロスバ４は、調停装置３から接続命令を入力し、当該接続命令に基づいて入力側バッファ部２から入力したリクエストパケットを出力側バッファ部５に出力する。
出力側バッファ部５は、クロスバ４からリクエストパケットを入力し、当該リクエストパケットを一時的に蓄えて、接続された出力ポート６に出力する。
出力ポート６は、接続された出力側バッファ部５からリクエストパケットを、調停装置３から強度情報を入力し、当該強度情報を含むリクエストパケットを、接続されたプロセッサコアまたは入出力装置（以下、計算資源と呼ぶ）に出力する。

なお、入力ポート１及び出力ポート６に接続されたプロセッサコア及び入出力装置は、共有のメモリ（図示せず）と接続されている。そして、プロセッサコア及び入出力装置は、当該メモリから自装置に関連付けられた強度情報を読み出す。また、プロセッサコア及び入出力装置は、出力ポート６から出力された強度情報を当該メモリに上書きして記録する。これにより、プロセッサコア及び入出力装置は、調停装置３が更新した強度情報を次回の入力に反映させることができる。

入力側バッファ部２は、入力バッファ２１、入力側ＦＩＦＯバッファ制御回路２２、ＦＩＦＯバッファ２３、出力側ＦＩＦＯバッファ制御回路２４、出力バッファ２５から構成される。
入力バッファ２１は、入力ポート１から入力したリクエストパケットを一時的に記憶する。
入力側ＦＩＦＯバッファ制御回路２２は、入力バッファ２１が記憶するリクエストパケットを取り出し、ＦＩＦＯバッファ２３に登録する。
ＦＩＦＯバッファ２３は、入力側ＦＩＦＯバッファ制御回路２２によって記録されたリクエストパケットを一時的に記憶する。
出力側ＦＩＦＯバッファ制御回路２４は、ＦＩＦＯバッファ２３に最初に登録されたリクエストパケットを取り出し、出力バッファ２５に登録する。ここで、「取り出す」とは、ＦＩＦＯバッファ２３からリクエストパケットを読み出し、読み出したリクエストパケットをＦＩＦＯバッファ２３から削除することを示す。
出力バッファ２５は、調停装置３及びクロスバ４に出力するリクエストパケットを一時的に記憶する。

調停装置３は、強度入力バッファ３１−１〜３１−５（以下、強度入力バッファ３１−１〜３１−５を総称する場合は強度入力バッファ３１と表記する）、リクエスト入力バッファ３２、バッファ登録回路３３、調停バッファ回路３４、予測回路３５、調停回路３６、強度更新回路３７、強度出力バッファ３８−１〜３８−５（以下、強度出力バッファ３８−１〜３８−５を総称する場合は強度出力バッファ３８と表記する）を備える。
強度入力バッファ３１は、それぞれ対応する入力側バッファ部２からリクエストパケットに含まれる強度情報を入力し、一時的に記憶する。
リクエスト入力バッファ３２は、入力側バッファ部２からリクエストパケット本体を入力し、一時的に記憶する。

バッファ登録回路３３は、強度入力バッファ３１が記憶する強度情報を取り出し、入力元の入力ポート１の識別情報に関連付けて調停バッファ回路３４に登録する。
調停バッファ回路３４は、調停対象となるリクエストパケットの入力元の入力ポート１の識別情報とリクエストパケットの強度情報とを関連付けて記憶する。
予測回路３５は、調停バッファ回路３４が記憶する調停対象となるリクエストパケットの情報と、調停回路３６による過去の調停結果とに基づいて調停回路３６がどのリクエストパケットを選択するかを予測し、予測結果を示す選択制御情報を調停回路３６に出力する。ここで、選択制御情報とは、予測回路３５が予測したリクエストパケットとその強度情報を示す。

調停回路３６は、強度入力バッファ３１が記憶する強度情報を取り出し、当該強度情報に基づいてリクエストパケットの調停を行い、リクエストパケットを出力ポート６に転送させる接続命令をクロスバ４に出力する。また、調停回路３６は、予測回路３５から選択制御情報を入力し、当該選択制御情報が示すリクエストパケットを出力ポート６に転送させる接続命令をクロスバ４に出力する。そして、調停回路３６は、調停結果を予測回路３５に出力する。ここで、調停結果とは、調停回路３６が接続命令を出力したリクエストパケットとその強度情報を示す。なお、調停結果は、調停回路３６による接続命令の出力毎に予測回路３５及び強度更新回路３７に出力される。また、調停回路３６は、予測回路３５から入力した選択制御情報が示す予測結果が誤っているか否かを判定し、誤っている場合は、クロスバ４に対し、選択制御情報に基づいて出力した接続命令の実行を中断させる中断命令を出力する。

強度更新回路３７は、予測回路３５から入力した選択制御情報が示すリクエストパケットと調停回路３６から入力した調停結果が示すリクエストパケットとが一致する場合に強度情報を更新し、強度出力バッファ３８に出力する。
強度出力バッファ３８は、強度更新回路３７から強度情報を入力し、当該強度情報を一時的に蓄えて、接続された出力ポート６に出力する。

図２は、予測回路の構成を示す概略ブロック図である。
予測回路３５は、一時リクエスト記憶部３５１、履歴登録部３５２、調停履歴記憶部３５３、履歴検索用バッファ３５４、検索部３５５、予測部３５６を備える。

一時リクエスト記憶部３５１は、調停回路３６から調停結果を入力し、当該調停結果を記憶する。なお、一時リクエスト記憶部３５１は、調停結果の入力順を記憶しており、新たな調停結果の入力によって一時リクエスト記憶部３５１の残り記憶容量が所定量に達する場合、一時リクエスト記憶部３５１は、最初に登録された調停結果を削除し、新たに入力した調停結果を記憶する。なお、本実施形態において、一時リクエスト記憶部３５１の記憶容量は、少なくとも３つの調停結果を記憶することができるだけあればよい。

履歴登録部３５２は、一時リクエスト記憶部３５１に新たに記憶された調停結果を読み出し、当該調停結果を調停履歴記憶部３５３に記録する。
調停履歴記憶部３５３は、履歴登録部３５２から調停結果を入力し、当該調停結果と調停結果の入力順を示すインデックス番号とを関連付けて記憶する。なお、調停履歴記憶部３５３は、調停結果の入力順を記憶しており、新たな調停結果の入力によって調停履歴記憶部３５３の残り記憶容量が所定量に達する場合、調停履歴記憶部３５３は、最初に登録された調停結果を削除し、新たに入力した調停結果を記憶する。なお、調停履歴記憶部３５３の記憶容量は、一時リクエスト記憶部３５１の記憶容量より大きいことが望ましい。

履歴検索用バッファ３５４は、一時リクエスト記憶部３５１から最後に登録された３つの調停結果を読み出し、検索部３５５による検索が完了するまで一時的に記憶する。
検索部３５５は、調停履歴記憶部３５３が記憶する調停結果の中から、履歴検索用バッファ３５４が記憶する３つの調停結果と同じ組み合わせの調停結果を検索する。
予測部３５６は、検索部３５５による検索結果と、調停バッファ回路３４に新たに登録された強度情報とに基づいて、調停回路３６の調停により何れのリクエストパケットが出力されるかを予測し、予測したリクエストパケットを示す選択制御情報を、調停回路３６及び強度更新回路３７に出力する。

そして、本実施形態による調停装置３において、強度入力バッファ３１は、複数のプロセッサコア及び入出力装置から強度情報の入力を受け付ける。次に、調停回路３６は、強度入力バッファ３１が同一の計算資源に対するリクエストパケットに関連付けられた強度情報の中から１つを選択し、選択された強度情報に関連付けられたリクエストパケットを当該リクエストパケットの発行先の計算資源へ出力させる接続命令をクロスバ４に出力する。

他方、予測回路３５は、調停回路３６による処理を実行する前に、調停回路３６によって選択されるリクエストパケットを予測し、当該リクエストパケットを当該リクエストパケットの発行先の計算資源へ出力させる接続命令をクロスバ４に出力する。
そして、調停回路３６は、選択したリクエストパケットと予測回路３５が予測したリクエストパケットとが異なる場合に、クロスバ４に対して予測回路３５による接続命令の実行を中断させる中断命令を出力する。
また、調停回路３６は、選択したリクエストパケットと予測回路３５が予測したリクエストパケットとが同一である場合に、クロスバ４に対する接続命令の出力を行わない。

これにより、調停処理の１サイクルあたりの実行処理内容を増加させず、かつ効率的なリクエストパケットの選択を行うことができる。以下に、本実施形態による調停装置によって調停処理を高速化することができる理由を説明する。

図３は、調停回路のパイプライン処理の流れを示す図である。
調停回路３６は、４段のパイプライン処理により、リクエストパケットの調停を行う。すなわち調停回路３６は、リクエストパケットから出力先の出力ポート６の識別情報を読み取るポート情報読み取りステージＸ０、読み取った識別情報に従ってリクエストパケットを出力ポート６に設定する出力ポート設定ステージＸ１、強度情報に基づいて調停を行うクロスバ設定前処理ステージＸ２及びクロスバ設定後処理ステージＸ３を順次実行することで調停処理を行う。そして、調停回路は４段のパイプライン処理による調停の後、調停により選択されたリクエストパケットを出力させる接続命令をクロスバ４に出力するパケット送出ステージＸＴを実行する。そのため、調停回路３６は、５サイクルで調停処理を実行する。これは、従来の調停方法に要するサイクル数と等しい。

他方、予測回路３５は、選択制御情報を予め生成するため、調停回路３６は、予測回路３５が生成した選択制御情報から選択するリクエストパケットを読み取る制御情報読み取りステージＰ０を実行し、読み取ったリクエストパケットを出力させる接続命令をクロスバ４に出力するパケット送出ステージＸＴを実行する。これにより、調停回路３６は、２サイクルで調停処理を実行することができる。したがって、予測回路３５によって予測されたリクエストパケットと調停回路３６による調停で選択されたリクエストパケットとが一致する場合、すなわち予測回路３５による予測が的中した場合、３サイクル分高速に調停処理を行うことができる。
つまり、予測回路３５による予測が的中するほど調停装置による調停処理が高速化されることとなる。

なお、予測回路３５によって予測されたリクエストパケットと調停回路３６による調停で選択されたリクエストパケットとが一致しない場合、すなわち予測回路３５による予測が外れた場合、調停回路３６が、予測回路３５が生成した選択制御情報に基づいて出力した接続命令の実行を中断させる中断命令をクロスバ４に出力し、改めて接続命令の出力を行う。このとき、調停回路３６は、中断命令の出力と接続命令の出力とを平行して実行するため、５サイクルで調停処理がなされる。そのため、予測回路３５による予測が外れた場合にも、従来の調停処理と比較して遅延が発生することはない。

次に、本実施形態による調停装置の動作を説明する。
図４は、調停装置の動作を示す第１のフローチャートである。
図５は、調停装置の動作を示す第２のフローチャートである。
まず、資源要求装置が同一の計算資源に対するリクエストパケットを発行すると、リクエストパケットを発行した資源要求装置に接続された入力ポート１を介して、入力側バッファ部２にリクエストパケットが登録される。そして、入力ポート１に登録されたリクエストパケットに含まれる強度情報は、調停装置３の強度入力バッファ３１に入力され、リクエストパケットの本体は、調停装置３のリクエスト入力バッファ３２に入力される（ステップＳ１）。そして、バッファ登録回路３３は、リクエスト入力バッファ３２から強度情報を取り出し、調停バッファ回路３４に登録する。

次に、予測回路３５は、自回路の一時リクエスト記憶部３５１が記憶する過去の調停結果のうち最後に登録された３つの調停結果を読み出し、履歴検索用バッファ３５４に記録する（ステップＳ２）。ここで、最後に登録された３つの調停結果の読み出しは、一時リクエスト記憶部３５１が記憶する入力順が最も新しい調停結果を３つ読み出すことで行う。次に、予測回路３５の検索部３５５は、調停履歴記憶部３５３が記憶する過去の調停結果の中から、履歴検索用バッファ３５４が記憶する調停結果の組み合わせを検索する（ステップＳ３）。具体的には、一時リクエスト記憶部３５１に最後に登録された３つの調停結果が、登録された順に「入力ポート１−４」「入力ポート１−５」「入力ポート１−１」からの入力であることを示す場合、履歴検索用バッファ３５４にはこれらの情報が登録され、検索部３５５は、調停履歴記憶部３５３が「入力ポート１−４」「入力ポート１−５」「入力ポート１−１」の順番に記憶された調停結果を検索する。

次に、検索部３５５は、ステップＳ３で実行した検索の結果、履歴検索用バッファ３５４が記憶する調停結果と同じ組み合わせが調停履歴記憶部３５３に記憶されているか否かを判定する（ステップＳ４）。但し、調停履歴記憶部３５３の末尾に記憶された調停結果は、必ず履歴検索用バッファ３５４が記憶する調停結果と一致するが、当該調停結果は検索結果から除外するものとする。

検索部３５５が、履歴検索用バッファ３５４が記憶する調停結果と同じ組み合わせが調停履歴記憶部３５３に記憶されていると判定した場合（ステップＳ４：ＹＥＳ）、予測部３５６は、検索部３５５が検索した調停結果の直後に調停履歴記憶部３５３に登録された調停結果を読み出す（ステップＳ５）。具体的には、予測部３５６は、検索部３５５が検索した調停結果に関連付けられた入力順を示すインデックス番号を読み出し、当該インデックス番号の次のインデックス番号に関連付けられた調停結果を、調停履歴記憶部３５３から読み出す。なお、検索部３５５によって複数の調停結果が検索された場合、予測部３５６は、それぞれの調停結果の直後に登録された調停結果をすべて読み出す。

次に、予測部３５６は、調停バッファ回路３４から強度情報を読み出し、読み出した強度情報の発行元と、ステップＳ５で読み出した調停結果の発行元とが一致するものがあるか否かを判定する（ステップＳ６）。予測部３５６は、発行元が一致するものがあると判定した場合（ステップＳ６：ＹＥＳ）、調停回路３６によって一致したリクエストパケットが選択されると予測する（ステップＳ７）。なお、発行元が一致するものが複数存在する場合、検索部３５５による検索結果のうち最も頻出する発行元からのリクエストパケットが選択されると予測し、当該予測したリクエストパケットを示す選択制御情報を生成する。

他方、ステップＳ４で検索部３５５が、履歴検索用バッファ３５４が記憶する調停結果と同じ組み合わせが調停履歴記憶部３５３に記憶されていないと判定した場合（ステップＳ４：ＮＯ）、または、ステップＳ６で予測部３５６が、読み出した強度情報と発行元が一致するリクエストパケットがないと判定した場合（ステップＳ６：ＮＯ）、予測部３５６は、ラウンドロビンアルゴリズムに基づいて、調停回路３６によって選択されるリクエストパケットを予測し、当該予測したリクエストパケットを示す選択制御情報を生成する（ステップＳ８）。

ステップＳ７、またはステップＳ８で予測部３５６が選択制御情報を生成すると、調停回路３６は、予測部３５６が生成した選択制御情報を読み取り（ステップＳ９）、選択制御情報が示すリクエストパケットを出力ポート６に転送させる接続命令をクロスバ４に出力する（ステップＳ１０）。すなわち、図３に示すＰ０ステージとＸＴステージの処理を実行する。

また、ステップＳ９、Ｓ１０の処理に平行して、調停回路３６は、リクエスト入力バッファ３２からリクエストパケット本体を読み出し、リクエストパケットに含まれる出力ポートのポート情報を読み取り（ステップＳ１１）、読み取った出力ポートのポート情報に従って出力ポートを設定し（ステップＳ１２）、リクエストパケットの調停処理を実行する（ステップＳ１３）。すなわち、図３に示すＸ０ステージ、Ｘ１ステージ、Ｘ２ステージ、Ｘ３ステージを実行する。

ここで、調停回路３６によるリクエストパケットの調停方法について説明する。
調停回路３６は、リクエスト入力バッファ３２に格納されているリクエストパケットに関連付けられた強度情報を、強度入力バッファ３１から読み出す。そして、調停回路３６は、強度情報が示す値が最も大きいリクエストパケットを選択する。また、最大の値を有する強度情報に関連付けられたリクエストパケットが複数ある場合、調停回路３６は、ラウンドロビンアルゴリズムに基づいて、何れのリクエストパケットを選択するかを決定する。

図６は、リクエストパケットの調停方法を示す図である。
ここで、具体的にリクエストパケットの調停方法を説明する。図６に示すように、リクエスト入力バッファ３２は、入力ポート１−１〜１−５から入力したそれぞれのリクエストパケットを記憶している。
入力ポート１−１から入力したリクエストパケット、及び入力ポート１−２から入力したリクエストパケットに関連付けられた強度情報は、「３」である。入力ポート１−３から入力したリクエストパケットに関連付けられた強度情報は、「５」である。入力ポート１−４から入力したリクエストパケットに関連付けられた強度情報は、「４」である。入力ポート１−５から入力したリクエストパケットに関連付けられた強度情報は、「１」である。

この場合、調停回路３６は、各強度情報の中から値が最大のものを抽出する。ここでは、入力ポート１−３から入力したリクエストパケットに関連付けられた強度情報「５」が最大である。したがって、調停回路３６は、リクエスト入力バッファ３２から、入力ポート１−３から入力したリクエストパケットを取り出し、当該リクエストパケットを調停結果として選択する。

次の調停実行時には、入力ポート１−３から入力したリクエストパケットが既に取り出されているため、入力ポート１−４から入力したリクエストパケットに関連付けられた強度情報「４」が最大である。したがって、調停回路３６は、リクエスト入力バッファ３２から、入力ポート１−４から入力したリクエストパケットを取り出し、当該リクエストパケットを調停結果として選択する。

次の調停実行時には、入力ポート１−３及び入力ポート１−４から入力したリクエストパケットが既に取り出されているため、入力ポート１−１及び入力ポート１−２から入力したリクエストパケットに関連付けられた強度情報「３」が最大である。したがって、調停回路３６は、ラウンドロビンアルゴリズムに基づいて、入力ポート１−１または入力ポート１−２から入力したリクエストパケットの何れかを取り出し、当該リクエストパケットを調停結果として選択する。図６では、入力ポート１−１から入力したリクエストパケットを選択している。

調停回路３６は、ステップＳ１３で調停処理を実行すると、予測回路３５から入力した選択制御情報が示すリクエストパケットと調停処理によって選択されたリクエストパケットとが一致するか否かを判定する（ステップＳ１４）。
調停回路３６は、リクエストパケットが一致しないと判定した場合（ステップＳ１４：ＮＯ）、ステップＳ１０で出力した接続命令の実行を中断させる中断命令、及びステップＳ１３の調停処理によって選択されたリクエストパケットを出力ポート６に転送させる接続命令をクロスバ４に出力する（ステップＳ１５）。

他方、ステップＳ１４で調停回路３６が、リクエストパケットが一致すると判定した場合（ステップＳ１４：ＹＥＳ）、強度更新回路３７は、各リクエストパケットに関連付けられた強度情報を更新し、強度出力バッファ３８に記録する（ステップＳ１６）。

以下に、強度更新回路３７による強度情報の更新方法を説明する。
図７は、強度情報の更新方法を示す図である。
強度更新回路３７は、内部メモリに、入力ポート１のそれぞれに関連付けて、当該入力ポート１から入力したリクエストパケットが選択されると予測したときに予測が的中する度合いを示す的中度を記憶する。
次に、強度更新回路３７は、調停回路３６から、予測回路３５が出力した選択制御情報が示すリクエストパケットと調停処理によって選択されたリクエストパケットとが一致するか否かを示す情報を入力する。強度更新回路３７は、リクエストパケットが一致すると判定した場合、選択されたリクエストパケットに関連付けられた的中度を増加させ、それ以外の的中度を減少させて、内部メモリに上書きして記録する。図７に示す例によれば、選択されたリクエストパケットの的中度を「４」増加させ、それ以外のリクエストパケットの的中度を「１」減少させている。
他方、強度更新回路３７は、リクエストパケットが一致しないと判定した場合、的中度の増減処理を行わない。

そして、強度更新回路３７は、的中度の増減処理の後、当該的中度に基づいて強度情報の値を決定する。図７に示す例によれば、的中度が２０未満の場合、強度情報が示す値を「１」とし、的中度が２０以上４０未満の場合、強度情報が示す値を「２」とし、的中度が４０以上６０未満の場合、強度情報が示す値を「３」とし、的中度が６０以上８０未満の場合、強度情報が示す値を「４」とし、的中度が８０以上の場合、強度情報が示す値を「５」としている。
つまり、予測回路３５による予測が的中した場合にのみ、強度情報の値が増加することとなる。そのため、調停回路３６は、より予測が的中しやすいリクエストパケットを優先的に選択することとなる。したがって、予測回路３５による予測が的中する確率が上昇し、調停装置３による調停処理を高速化することができる。

また、的中度をそのまま強度情報として用いず、的中度に対して丸め処理を行って強度情報を生成するため、調停回路３６による選択にランダム性を持たせることができる。これにより、実行するアプリケーションを、的中度の低い資源要求装置によるリクエストパケットの出力が多いアプリケーションに変更した場合にも、的中度の低い資源要求装置によるリクエストパケットの選択がなされる。そのため、調停処理が繰り返されることにより、当該資源要求装置の的中度が向上するため、効率的な選択ができるようになる。

ここで、具体的に強度情報の更新方法を説明する。図７に示すように、強度更新回路３７の内部メモリは、入力ポート１−１〜１−５のそれぞれに関連付けて的中度を記憶している。
入力ポート１−１の的中度は、「１９」である。入力ポート１−２の的中度は、「１１」である。入力ポート１−３の的中度は、「１３」である。入力ポート１−４の的中度は、「４３」である。入力ポート１−５の的中度は、「１４」である。

そして、強度更新回路３７は、調停回路３６から、入力ポート１−４から入力したリクエストパケットを選択し、当該リクエストパケットが、予測回路３５が出力した選択制御情報が示すリクエストパケットと一致することを示す情報を入力する。これにより、強度更新回路３７は、入力ポート１−４に関連付けられた的中度を「４」増加させることで「４７」に更新し、他の的中度を「１」ずつ減少させる。
次に、強度更新回路３７は、的中度の値に応じて選択されたリクエストパケットに関連付けられた強度情報を更新する。つまり、強度更新回路３７は、入力ポート１−４の的中度が「１８」、すなわち２０未満であるため、入力ポート１−４から入力したリクエストパケットの強度情報を「１」に更新する。

次に、強度更新回路３７は、調停回路３６から、入力ポート１−１から入力したリクエストパケットを選択し、当該リクエストパケットが、予測回路３５が出力した選択制御情報が示すリクエストパケットと一致することを示す情報を入力する。これにより、強度更新回路３７は、入力ポート１−１に関連付けられた的中度を「４」増加させることで「２２」に更新し、他の的中度を「１」ずつ減少させる。
次に、強度更新回路３７は、入力ポート１−１の的中度が「２２」、すなわち２０以上４０未満であるため、入力ポート１−４から入力したリクエストパケットの強度情報を「２」に更新する。

次に、強度更新回路３７は、調停回路３６から、入力ポート１−３から入力したリクエストパケットを選択し、当該リクエストパケットが、予測回路３５が出力した選択制御情報が示すリクエストパケットと一致しなかったことを示す情報を入力する。この場合、強度更新回路３７は、的中度及び強度情報の更新を行わない。

次に、強度更新回路３７は、調停回路３６から、入力ポート１−５から入力したリクエストパケットを選択し、当該リクエストパケットが、予測回路３５が出力した選択制御情報が示すリクエストパケットと一致することを示す情報を入力する。これにより、強度更新回路３７は、入力ポート１−５に関連付けられた的中度を「４」増加させることで「１６」に更新し、他の的中度を「１」ずつ減少させる。
次に、強度更新回路３７は、入力ポート１−１の的中度が「１６」、すなわち２０未満であるため、入力ポート１−４から入力したリクエストパケットの強度情報を「１」に更新する。
このような処理を繰り返すことで、調停回路３６は、より予測が的中しやすいリクエストパケットを優先的に選択することとなり、調停装置３は高速に調停処理を行うことができる。

ステップＳ１５で、調停回路３６が中断命令及び接続命令を出力した場合、またはステップＳ１６で強度更新回路３７が強度情報を更新した場合、調停回路３６は、予測回路３５の一時リクエスト記憶部３５１の末尾に調停結果を記録する（ステップＳ１７）。次に、履歴登録部３５２は、一時リクエスト記憶部３５１に新たに記録された調停結果を、調停履歴記憶部３５３の末尾に記録する（ステップＳ１８）。

そして、予測回路３５は、調停回路３６が全てのリクエストパケットの調停を終了したか否かを判定する（ステップＳ１９）。調停が終了したか否かの判定は、例えば、調停回路３６が、リクエスト入力バッファ３２にリクエストパケットが記憶されているか否かを判定することで実行することができる。ステップＳ１３で、調停処理により選択されたリクエストパケットは、順次、リクエスト入力バッファ３２から取り出されるため、調停が終了していないリクエストパケットが存在する場合、リクエスト入力バッファ３２にはリクエストパケットが記憶されていることとなる。したがって、予測回路３５は、リクエスト入力バッファ３２にリクエストパケットが記憶されている場合に、リクエストパケットの調停を終了していないと判定する。

予測回路３５が、調停が終了していないリクエストパケットが存在すると判定した場合（ステップＳ１９：ＮＯ）、ステップＳ２に戻り、次のリクエストパケットの調停を行う。他方、予測回路３５が、全てのリクエストパケットに対する調停が終了していると判定した場合（ステップＳ１９：ＹＥＳ）、処理を終了する。

このように、本実施形態によれば、調停回路３６による調停の実行の前に、予測回路３５が、選択されるリクエストパケットの予測を行い、クロスバ４に当該リクエストパケットを出力させる接続命令を出力する。これにより、調停装置３は、調停処理の１サイクルあたりの実行処理内容を増加させずに、効率的なリクエストパケットの選択を行うことができる。

以上、図面を参照してこの発明の一実施形態について詳しく説明してきたが、具体的な構成は上述のものに限られることはなく、この発明の要旨を逸脱しない範囲内において様々な設計変更等をすることが可能である。
例えば、本実施形態では、ステップＳ４で検索部３５５が、履歴検索用バッファ３５４が記憶する調停結果と同じ組み合わせが調停履歴記憶部３５３に記憶されていないと判定した場合、または、ステップＳ６で予測部３５６が、読み出した強度情報と発行元が一致するリクエストパケットがないと判定した場合に、予測部３５６が、ラウンドロビンアルゴリズムに基づいて、調停回路３６によって選択されるリクエストパケットを予測する場合を説明したが、これに限られず、例えば、リクエストパケットをランダムに選択し、選択したリクエストパケットを、調停回路３６によって選択されると予測されるリクエストパケットとしても良い。

また、本実施形態では、調停回路３６が調停処理を行う際、最大の値を有する強度情報に関連付けられたリクエストパケットが複数あるとき、調停回路３６は、ラウンドロビンアルゴリズムに基づいて、何れのリクエストパケットを選択するかを決定する場合を用いて説明したが、これに限られず、例えば、調停回路３６は、リクエストパケットをランダムに選択しても良い。

また、本実施形態では、資源要求装置がリクエストパケットに強度情報を付与してクロスバ調停装置に出力する場合を説明したが、これに限られず、例えば、資源要求装置は、強度情報を含まないリクエストパケットをクロスバ調停装置に入力し、調停装置３が入力ポート１の識別情報に関連付けて強度情報を格納する強度情報記憶部を備えておくことで、調停装置３の調停回路３６は、当該強度情報記憶部から読み出した強度情報に基づいて調停処理を行っても、本実施形態と同様の効果を得ることができる。

また、本実施形態では、ステップＳ２で、予測回路３５の履歴検索用バッファ３５４が、一時リクエスト記憶部３５１の末尾に記憶された３つの調停履歴を記憶する場合を説明したが、これに限られず、調停履歴を４つ以上記憶しても良いし、１つ乃至２つ記憶しても良い。

上述の調停装置３は内部に、コンピュータシステムを有している。そして、上述した各回路の動作は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータが読み出して実行することによって、上記処理が行われる。ここでコンピュータ読み取り可能な記録媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等をいう。また、このコンピュータプログラムを通信回線によってコンピュータに配信し、この配信を受けたコンピュータが当該プログラムを実行するようにしても良い。

また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。

１、１−１〜１−５…入力ポート ２、２−１〜２−５…入力側バッファ部 ３…調停装置 ４…クロスバ ５、５−１〜５−５…出力側バッファ部 ６、６−１〜６−５…出力ポート ２１…入力バッファ ２２…入力側ＦＩＦＯバッファ制御回路 ２３…ＦＩＦＯバッファ ２４…出力側ＦＩＦＯバッファ制御回路 ２５…出力バッファ ３１、３１−１〜３１−５…強度入力バッファ ３２…リクエスト入力バッファ ３３…バッファ登録回路 ３４…調停バッファ回路 ３５…予測回路 ３６…調停回路 ３７…強度更新回路 ３８、３８−１〜３８−５…強度出力バッファ ３５１…一時リクエスト記憶部 ３５２…履歴登録部 ３５３…調停履歴記憶部 ３５４…履歴検索用バッファ ３５５…検索部 ３５６…予測部

Claims (5)

1. 複数の資源要求装置から発行される、当該資源要求装置による計算資源の使用の要求を示す資源要求の調停を行い、前記資源要求装置と前記計算資源とを接続するクロスバを制御する調停装置であって、
   複数の前記資源要求装置から資源要求の入力を受け付ける入力部と、
   前記入力部が同一の前記計算資源に対する資源要求の中から１つを選択し、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する調停部と、
   前記調停部による処理を実行する前に、前記調停部によって選択される資源要求を予測し、当該資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する予測部と、
   前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、前記クロスバに対して前記予測部による接続命令の実行を中断させる中断命令を出力する中断部と、
   過去の処理において前記調停部が選択した資源要求を選択した順に調停履歴記憶部に登録する履歴登録部と
   を備え、
   前記調停部は、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが同一である場合に、前記クロスバに対する前記接続命令の出力を行わず、
   前記予測部は、前記調停部による最後の所定の個数の資源要求を選択した順と同じ順に、前記調停履歴記憶部に記憶されている資源要求の直後に登録された資源要求を、前記調停部によって選択される資源要求として予測する
   ことを特徴とする調停装置。
2. 複数の資源要求装置から発行される、当該資源要求装置による計算資源の使用の要求を示す資源要求の調停を行い、前記資源要求装置と前記計算資源とを接続するクロスバを制御する調停装置であって、
   複数の前記資源要求装置から資源要求の入力を受け付ける入力部と、
   前記入力部が同一の前記計算資源に対する資源要求の中から１つを選択し、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する調停部と、
   前記調停部による処理を実行する前に、前記調停部によって選択される資源要求を予測し、当該資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する予測部と、
   前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、前記クロスバに対して前記予測部による接続命令の実行を中断させる中断命令を出力する中断部と、
   前記資源要求装置ごとに、過去の処理において、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが同一となる度合いを示す強度情報を算出する強度情報算出部と
   を備え、
   前記調停部は、前記強度情報算出部が算出した強度情報に基づいて、選択する資源要求を決定し、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが同一である場合に、前記クロスバに対する前記接続命令の出力を行わない
   ことを特徴とする調停装置。
3. 複数の資源要求装置から発行される、当該資源要求装置による計算資源の使用の要求を示す資源要求の調停を行い、前記資源要求装置と前記計算資源とを接続するクロスバを制御する調停装置を用いた調停方法であって、
   入力部は、複数の前記資源要求装置から資源要求の入力を受け付け、
   調停部は、前記入力部が同一の前記計算資源に対する資源要求の中から１つを選択し、
   予測部は、前記調停部による処理を実行する前に、前記調停部によって選択される資源要求を予測し、当該資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力し、
   中断部は、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、前記クロスバに対して前記予測部による接続命令の実行を中断させる中断命令を出力し、
   履歴登録部は、過去の処理において前記調停部が選択した資源要求を選択した順に調停履歴記憶部に登録し、
   前記調停部は、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力し、
   前記予測部は、前記調停部による最後の所定の個数の資源要求を選択した順と同じ順に、前記調停履歴記憶部に記憶されている資源要求の直後に登録された資源要求を、前記調停部によって選択される資源要求として予測する
   ことを特徴とする調停方法。
4. 複数の資源要求装置から発行される、当該資源要求装置による計算資源の使用の要求を示す資源要求の調停を行い、前記資源要求装置と前記計算資源とを接続するクロスバを制御する調停装置を用いた調停方法であって、
   入力部は、複数の前記資源要求装置から資源要求の入力を受け付け、
   調停部は、前記入力部が同一の前記計算資源に対する資源要求の中から１つを選択し、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力し、
   予測部は、前記調停部による処理を実行する前に、前記調停部によって選択される資源要求を予測し、当該資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力し、
   中断部は、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、前記クロスバに対して前記予測部による接続命令の実行を中断させる中断命令を出力し、
   強度情報算出部は、前記資源要求装置ごとに、過去の処理において、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが同一となる度合いを示す強度情報を算出し、
   前記調停部は、前記強度情報算出部が算出した強度情報に基づいて、選択する資源要求を決定し、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する
   ことを特徴とする調停方法。
5. 複数の資源要求装置から発行される、当該資源要求装置による計算資源の使用の要求を示す資源要求の調停を行い、前記資源要求装置と前記計算資源とを接続するクロスバを制御する調停装置を、
   複数の前記資源要求装置から資源要求の入力を受け付ける入力部、
   前記入力部が同一の前記計算資源に対する資源要求の中から１つを選択し、選択された資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する調停部、
   前記調停部による処理を実行する前に、前記調停部によって選択される資源要求を予測し、当該資源要求を当該資源要求の発行先の計算資源へ出力させる接続命令を前記クロスバに出力する予測部、
   前記調停部が選択した資源要求と前記予測部が予測した資源要求とが異なる場合に、前記クロスバに対して前記予測部による接続命令の実行を中断させる中断命令を出力する中断部、
   過去の処理において前記調停部が選択した資源要求を選択した順に調停履歴記憶部に登録する履歴登録部
   として機能させ、
   前記調停部は、前記調停部が選択した資源要求と前記予測部が予測した資源要求とが同一である場合に、前記クロスバに対する前記接続命令の出力を行わず、
   前記予測部は、前記調停部による最後の所定の個数の資源要求を選択した順と同じ順に、前記調停履歴記憶部に記憶されている資源要求の直後に登録された資源要求を、前記調停部によって選択される資源要求として予測する
   ことを特徴とするプログラム。

Images