Top > Search of Japanese Patents > MEMORY MANAGEMENT METHOD, INFORMATION PROCESSOR, CREATION METHOD OF PROGRAM, AND PROGRAM

MEMORY MANAGEMENT METHOD, INFORMATION PROCESSOR, CREATION METHOD OF PROGRAM, AND PROGRAM foreign

Patent code P100001083
File No. WASEDA-138-PCT -604
Posted date Oct 21, 2010
Application number P2007-050269
Publication number P2008-217134A
Patent number P5224498
Date of filing Feb 28, 2007
Date of publication of application Sep 18, 2008
Date of registration Mar 22, 2013
Inventor
  • (In Japanese)笠原 博徳
  • (In Japanese)木村 啓二
  • (In Japanese)中野 啓史
  • (In Japanese)仁藤 拓実
  • (In Japanese)丸山 貴紀
  • (In Japanese)三浦 剛
  • (In Japanese)田川 友博
Applicant
  • (In Japanese)学校法人早稲田大学
Title MEMORY MANAGEMENT METHOD, INFORMATION PROCESSOR, CREATION METHOD OF PROGRAM, AND PROGRAM foreign
Abstract PROBLEM TO BE SOLVED: To efficiently arrange data in a memory, in a memory management method in a multiprocessor system.
SOLUTION: In a method of managing a storage area of the memory used by a processor, the processor is connected to the memory for storing the data used in executing a task, divides the storage area of the memory into blocks of a plurality of different sizes, selects the block of the size matching to the data used in executing the task, and stores the data used in executing the task in the selected block.
Outline of related art and contending technology (In Japanese)

複数のプロセッサコアを一つのチップ上に集積したマルチコアプロセッサ(チップマルチプロセッサ)が、各マイクロプロセッサメーカによって次々に発表されている。スーパーコンピュータ、サーバ、デスクトップコンピュータ及びPCサーバ分野の他、情報家電及び装置組み込みの分野(例えば、携帯電話機、ゲーム機、カーナビゲーションシステム、デジタルテレビ受像機、HDD/DVDレコーダ・プレーヤ等)においても、マイクロプロセッサのマルチコア化の動きが見られる。

このように、現在情報家電からスーパーコンピュータに至るほとんどの情報機器においてマルチコアプロセッサが使われるようになっており、今後、さらに多くの情報機器にマルチコアプロセッサが組み込まれていくと考えられる。

マルチコアプロセッサは、細粒度命令レベルの並列性だけでなく、より並列性の大きいループレベルの並列性、さらに粒度の粗いループ間の並列性、関数間の粗粒度タスク並列性も利用することができる。このように、マルチコアプロセッサは、より大きな並列性の利用によって、プロセッサの処理性能を向上させることができる点で有利である。また、マルチコアプロセッサは、n台のプロセッサコアを用い同一性能を達成することができるので、クロック周波数をn分の1にし、印加する電圧も下げることによって、消費電力(電圧の2乗で増大する)を低く抑えることができる点でも有利である。

また、ソフトウェア面では、マルチプロセッサ用の並列プログラミングは、通常、チューニングに多大な時間を要することから、アプリケーションソフトウェアの開発が大変である。しかし、比較的少数のプロセッサが集積されている現時点では、逐次プログラムを自動的に並列化する自動並列化コンパイラによって高性能を得ることができる。情報家電分野ではアプリケーションの質と数が市場での競争力を決めることから、コンパイラによって、4コア、8コア、16コアのマルチプロセッサ用のプログラムの自動並列化が可能となれば、マルチコアの優位性が高まる。

また、マルチグレイン並列化では、文レベル、ループレベル、より粗いレベル(例えば、ループ間、サブルーチン間、ベーシックブロック間)の全ての並列性を組み合わせて最早実行可能条件解析によって並列性を抽出する(例えば、特許文献1参照)。
【特許文献1】
特開2001-175619号公報

Field of industrial application (In Japanese)

本発明は、複数のプロセッサコアで構成されるマルチプロセッサシステムにおけるメモリの管理方法に関し、特に、コンパイラが取得した情報に基づいて、プロセッサによってアクセスされるされるデータをメモリの分割された領域に割り当てる方法に関する。

Scope of claims (In Japanese)
【請求項1】
 
プロセッサによって使用されるメモリの記憶領域を管理する方法であって、
前記プロセッサは、タスクの実行時にアクセスされるデータを格納するメモリに接続されており、
前記タスクを含むプログラムの解析によって得られた情報に基づいて、前記プログラムで使用されるデータのサイズに適合するように、前記メモリの記憶領域を分割するためのブロックの複数の異なるサイズを決定し、
前記決定された複数のサイズのブロックに前記記憶領域を分割し、
前記タスクの実行時にアクセスされるデータに適合するサイズのブロックを選択し、
前記選択されたブロックに、前記タスクの実行時にアクセスされるデータを格納することを特徴とするメモリ管理方法。

【請求項2】
 
請求項1に記載のメモリ管理方法であって、
前記複数のサイズのブロックのサイズは互いに整数倍の関係にあることを特徴とするメモリ管理方法。

【請求項3】
 
請求項1又は2に記載のメモリ管理方法であって、
前記データを前記選択されたブロックへ割り当てることを決定した後、データ転送手段によって、前記データを前記選択されたブロックに格納し、
前記ブロックの解放タイミングまでに、前記データ転送手段によって、前記選択されたブロックに格納されたデータを読み出し、他のメモリに格納することを特徴とするメモリ管理方法。

【請求項4】
 
請求項1から3のいずれか一つに記載のメモリ管理方法であって、
前記プログラムの解析によって得られた情報に基づいて定められた複数の形状及びサイズのテンプレートを、適合する大きさの前記ブロックに割り当て、
前記割り当てられたテンプレートに適合する形状及び大きさのデータを、前記テンプレートに格納することを特徴とするメモリ管理方法。

【請求項5】
 
請求項4に記載のメモリ管理方法であって、
前記タスクでアクセスされるデータにn次元の配列データが含まれる場合に、各ブロッ
クに割り当て可能な複数種類のテンプレートから、前記タスクの実行時にアクセスされる配列データの次元nに1を加えた次元n+1を有し、加えられた次元以外の各次元の最大値が前記タスクの実行時にアクセスされる配列データの各次元の最大値以上のテンプレートを割り当て、
前記加えられた次元の値によって、アクセスされるブロックが異なるように、次元が異なるか又は同じ次元で各次元のサイズが異なる複数種類の前記テンプレートの一つを前記各ブロックに割り当てることを特徴とするメモリ管理方法。

【請求項6】
 
プロセッサ及び前記プロセッサによってアクセスされるデータを格納するメモリを備える情報処理装置であって、
前記プロセッサは、
前記プロセッサで実行されるプログラムの解析によって得られた情報に基づいて、前記プログラムで使用されるデータのサイズに適合するように、前記メモリの記憶領域を分割するためのブロックの複数の異なるサイズを決定し、
前記決定された複数のサイズのブロックに前記記憶領域を分割し、
前記タスクの実行時にアクセスされるデータに適合するサイズのブロックを選択し、
前記選択されたブロックに、前記タスクの実行時にアクセスされるデータを格納することを特徴とする情報処理装置。

【請求項7】
 
請求項6に記載の情報処理装置であって、
前記ブロックは、複数のサイズのブロックを含み、前記ブロックの複数のサイズは整数倍の関係にあることを特徴とする情報処理装置。

【請求項8】
 
請求項6又は7に記載の情報処理装置であって、
前記プロセッサは、
前記データを前記選択されたブロックへ割り当てることを決定した後、データ転送手段によって、前記データを前記選択されたブロックに格納し、
前記ブロックの解放タイミングまでに、前記データ転送手段によって、前記選択されたブロックに格納されたデータを読み出し、他のメモリに格納することを特徴とする情報処理装置。

【請求項9】
 
請求項6から8のいずれか一つに記載の情報処理装置であって、
前記プロセッサは、
前記プログラムの解析によって得られた情報に基づいて定められた複数の形状及びサイズのテンプレートを、適合する大きさの前記ブロックに割り当て、
前記割り当てられたテンプレートに適合する形状及び大きさのデータを、前記テンプレートに格納することを特徴とする情報処理装置。

【請求項10】
 
請求項9に記載の情報処理装置であって、
前記タスクでアクセスされるデータにn次元の配列データが含まれる場合に、各ブロックに割り当て可能な複数種類のテンプレートから、前記プログラムでアクセスされる配列データの次元nに1を加えたn+1次元を有し、加えられた次元以外の各次元の最大値が前記プログラムでアクセスされる配列データの各次元の最大値以上のテンプレートを割り当て、
前記加えられた次元の値によって、アクセスされるブロックが異なるように、次元が異なるか又は同じ次元で各次元のサイズが異なる複数種類の前記テンプレートの一つを前記各ブロックに割り当てることを特徴とする情報処理装置。

【請求項11】
 
プロセッサによって実行可能なプログラムを作成する方法であって、
前記方法は、計算機において実行され、
前記計算機が、
元プログラムの情報をコンパイラによって解析し、
前記元プログラムに含まれる各タスクの実行に必要なデータを特定し、
前記元プログラムの解析によって得られた情報に基づいて、前記作成されるプログラムで使用されるデータのサイズに適合するように、前記メモリの記憶領域を分割するためのブロックの複数の異なるサイズを決定し、前記作成されるプログラムが実行されるプロセッサのメモリの記憶領域を前記決定された複数のサイズのブロックに分割する命令と、前記タスクの実行時にアクセスされるデータに適合するサイズのブロックを選択する命令と、前記選択されたブロックに、前記タスクの実行時にアクセスされるデータを格納する命令とを追加することによって、前記プロセッサ上で実行可能なプログラムを生成することを特徴とするプログラムの作成方法。

【請求項12】
 
請求項11に記載のプログラムの作成方法であって、
前記複数の異なるサイズのブロックのサイズは互いに整数倍の関係にあることを特徴とするプログラムの作成方法。

【請求項13】
 
請求項11又は12に記載のプログラムの作成方法であって、
前記計算機は、
前記コンパイラが前記元プログラムを解析して得られた情報に基づいて、
前記データを前記選択されたブロックへ割り当てることを決定した後、データ転送手段
によって、前記データを前記選択されたブロックに格納する命令と、
前記ブロックの解放タイミングまでに、前記データ転送手段によって、前記選択されたブロックに格納されたデータを読み出し、他のメモリに格納する命令を追加することによって、前記プロセッサ上で実行可能なプログラムを生成することを特徴とするプログラムの作成方法。

【請求項14】
 
請求項11から13のいずれか一つに記載のプログラムの作成方法であって、
前記計算機は、
前記元プログラムを前記コンパイラによって解析して得られた情報に基づいて、定められた複数の形状及びサイズのテンプレートを、適合する大きさの前記ブロックに割り当てる命令と、
前記割り当てられたテンプレートに適合する形状及び大きさのデータを、前記テンプレートに格納する命令と、を追加することによって、前記プロセッサ上で実行可能なプログラムを生成することを特徴とするプログラムの作成方法。

【請求項15】
 
請求項14に記載のプログラムの作成方法であって、
前記計算機は、
前記元プログラムを前記コンパイラによって解析して得られた情報に基づいて、
前記タスクでアクセスされるデータにn次元の配列データが含まれる場合に、各ブロックに割り当て可能な複数種類のテンプレートから、前記タスクでアクセスされる配列データの次元nに1を加えた次元n+1を有し、加えられた次元以外の各次元の最大値が前記タスクでアクセスされる配列データの各次元の最大値以上のテンプレートを割り当てる命令と、
前記加えられた次元の値によって、アクセスされるブロックが異なるように、次元が異なるか又は同じ次元で各次元のサイズが異なる複数種類の前記テンプレートの一つを前記各ブロックに割り当てる命令と、を追加することによって、前記プロセッサ上で実行可能なプログラムを生成することを特徴とするプログラムの作成方法。

【請求項16】
 
請求項11に記載のプログラムの作成方法であって、
前記計算機は、
前記元プログラムを前記コンパイラによって解析して得られた情報に基づいて、解放する前記領域及び前記領域を解放するタイミングを決定し、
前記割り当てられた領域を解放するために、前記決定されたタイミングまでに前記メモリに書き込まれたデータを読み出す命令を追加することによって、前記プロセッサ上で実行可能なプログラムを生成することを特徴とするプログラムの作成方法。

【請求項17】
 
請求項16に記載のプログラムの作成方法であって、
前記計算機は、
前記元プログラムを前記コンパイラによって解析して得られた情報に基づいて、
前記メモリの領域を割り当てた後に、データ転送手段によって、前記データを前記メモリに格納する命令、及び
前記メモリの領域の解放タイミングまでに、前記データ転送手段によって、前記メモリに格納されたデータを読み出し、他のメモリに格納する命令を、前記プロセッサ上で実行可能なプログラムに追加して前記プロセッサ上で実行可能なプログラムを生成することを特徴とするプログラムの作成方法。

【請求項18】
 
請求項11に記載のプログラムの作成方法であって、
前記元プログラムを前記コンパイラによって解析して得られた情報は、前記元プログラムでアクセスされるデータの情報、前記データが次にアクセスされるタイミングの情報、前記データをアクセスするプロセッサの情報の少なくとも一つを含むことを特徴とするプログラムの作成方法。

【請求項19】
 
請求項11に記載のプログラムの作成方法であって、
前記作成されるプログラムが実行される前記プロセッサは複数のプロセッサコアを備えるマルチプロセッサであって、
前記方法は、
前記計算機が、
前記タスクをいつどのプロセッサに実行させるかを決定し、
前記決定されたプロセッサに前記タスクを割り当てる命令を追加することによって、前記プロセッサ上で実行可能なプログラムを生成することを特徴とするプログラムの作成方法。

【請求項20】
 
請求項11に記載のプログラムの作成方法であって、
前記計算機は、
前記元プログラムを前記コンパイラによって解析して得られた情報に基づいて、前記前記プロセッサ上で実行可能なプログラムの実行時にアクセスされるデータを前記一つのブロックに収まるように前記プロセッサ上で実行可能なプログラムに含まれるタスクを分割して、前記プロセッサ上で実行可能なプログラムを生成することを特徴とするプログラムの作成方法。

【請求項21】
 
請求項19に記載のプログラムの作成方法であって、
前記元プログラムは多重ループを含み、
前記方法は、
前記計算機が、
前記元プログラムを前記コンパイラによって解析して得られた情報に基づいて、外側のループの分割によって生成されたタスクの実行時にアクセスされるデータが前記ブロックに収まるか否かを判定し、
前記外側のループの分割によって生成されたタスクの実行時にアクセスされるデータが前記ブロックに収まらなければ、更に内側のループを分割することによって、前記データのサイズを変更して前記プロセッサ上で実行可能なプログラムを生成することを特徴とするプログラムの作成方法。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2007050269thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close