(57)【要約】  メモリ内にデータブロックを記憶すべく割当てられる所定の数のメモリフレームの各々のサイズを決定する方法、および当該方法を実行する処理装置。本方法は、少なくとも１個の組のデータブロックのデータブロック・サイズ割振りを決定するステップを含んでいる。データブロック・サイズの個数がメモリフレームのサイズの個数と一致するまで、データブロック・サイズ割振りのデータブロック・サイズが反復的に除去される。スラック予測アルゴリズムにより、統合すべきデータブロック・サイズが選択される。メモリフレームのサイズが、除去の後に残る割振りのデータブロック・サイズであるように、決定される。
2008516320.tif 000002
【特許請求の範囲】
【請求項１】
メモリ（１２）に割当てられる所定個数のメモリフレームの各々のサイズを決定する方法であって、前記メモリ（１２）がデータブロックを記憶すべく適合されていて、
少なくとも１組のデータブロック（１０１〜１０６、１１１〜１１７、１２１〜１２５）について、データブロック・サイズの割振りを決定するステップであって、前記データブロックの組の各データブロックが特定のサイズを有する、ステップと、
統合されたデータブロック・サイズを生成すべく前記少なくとも１個のデータブロック・サイズを前記割振りの他のデータブロック・サイズに統合することにより、前記割振りのデータブロック・サイズの個数が前記所定個数のメモリフレームのサイズの個数に一致するまで、前記データブロック・サイズ割振りの少なくとも１個のデータブロック・サイズを反復的に除去するステップであって、前記他のデータブロック・サイズが前記少なくとも１個のデータブロック・サイズより大きく且つ前記統合されたデータブロック・サイズが前記他のデータブロック・サイズに一致し、統合すべきデータブロック・サイズがスラック予測アルゴリズムにより選択される、ステップと、
前記メモリフレームの各々のサイズを、前記除去の後も残る前記割振りのデータブロック・サイズの１つのサイズであるように、且つ前記メモリフレームの各サイズが異なるように、決定するステップとを含む方法。
【請求項２】
統合するデータブロック・サイズが前記スラック予測アルゴリズムにより選択され、前記アルゴリズムに従い前記少なくとも１個のデータブロック・サイズが、前記少なくとも１個のデータブロック・サイズを前記他のデータブロック・サイズに統合することにより少なくとも１回の反復の間に生じるスラックを最少限に抑えることに寄与するように、選択される、請求項１に記載の方法。
【請求項３】
各々の反復において、前記少なくとも１個のデータブロック・サイズが前記他のデータブロック・サイズに統合された際に、前記少なくとも１個のデータブロック・サイズを有するデータブロックの個数を前記他のデータブロック・サイズを有するデータブロックの個数に加算するステップを更に含む、請求項１または２に記載の方法。
【請求項４】
前記割振りの最大データブロック・サイズ以外の各データブロック・サイズについて、各々の反復において、前記少なくとも１個のデータブロック・サイズが前記決定された割振りのより大きいデータブロック・サイズに組み込まれた場合に生じ得る予測スラックを決定するステップを含む、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記より大きいデータブロック・サイズが、前記決定された割振りのうち除去されていない次に大きいデータブロック・サイズである、請求項３に記載の方法。
【請求項６】
前記スラック予測アルゴリズムが、各々の反復において、除去されていない前記割振りのデータブロック・サイズのうち、より大きいデータブロック・サイズに組み込まれた場合に生じ得るスラックが最も少ないものがどれかを決定し、前記決定されたデータブロック・サイズを前記少なくとも１個のデータブロック・サイズの１つとして選択するステップを含む請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記スラック予測アルゴリズムが、各々の反復において、前記割振りの除去されていないデータブロック・サイズに対して、合計予測スラックを示すスラック予測値を生成するステップを含む、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記データブロックの組が、メモリ（１２）を含むシステムの少なくとも１個の所定のプロセス用のデータブロックに関係する、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
前記データブロックの組が、少なくとも１つの信号のデータブロックに関係する、請求項１〜７のいずれか一項に記載の方法。
【請求項１０】
データブロックが前記メモリ（１２）に書き込まれる実行時に、前記データブロック・サイズ割振りを決定するステップを含む、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
現行割振りにおいてデータブロック・サイズを除去する前に、少なくとも１個の可能な後続データブロック・サイズ割振りにおいて現行割振りの特定のデータブロック・サイズを除去する効果が調べられる、請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
現行データブロック・サイズ割振りのデータブロック・サイズの個数に依存して、可能な後続データブロック・サイズ割振りの調べる個数を動的に変えるステップを含む、請求項１１に記載の方法。
【請求項１３】
現行データブロック・サイズ割振りに基づいて生成することができる各々の可能なデータブロック・サイズ割振りを決定して、現行および可能なデータブロック・サイズ割振りの各々に対してスラック予測値を生成するステップを含む、請求項１１または１２に記載の方法。
【請求項１４】
現行データブロック・サイズ割振りから、前記少なくとも１個のデータブロック・サイズの第一のものを、現行および後続反復において生じ得る予測スラックの合計を最少限に抑えるデータブロック・サイズとして選択するステップを含む、請求項１３に記載の方法。
【請求項１５】
後続する反復から前記少なくとも１個のデータブロック・サイズの第二のものを選択して、前記第二のデータブロック・サイズを後続データブロック割振りの他のデータブロック・サイズに統合するステップを含む、請求項１１〜１４のいずれか一項に記載の方法。
【請求項１６】
前記他のデータブロック・サイズが、前記割振りに残る、前記割振り内の前記少なくとも１個のデータブロック・サイズの最大データブロック・サイズの次のデータブロック・サイズである、請求項１〜１５のいずれか一項に記載の方法。
【請求項１７】
メモリ（１２）に割当てられる所定個数のメモリフレームの各々のサイズを決定するための処理装置（１３）であって、前記メモリ（１２）がデータブロックを記憶すべく適合されていて、
前記処理装置が、少なくとも１組のデータブロック（１０１〜１０６、１１１〜１１７、１２１〜１２５）について、データブロック・サイズの割振りを決定するように構成され、前記データブロックの組の各データブロックは特定のサイズを有しており、
前記処理装置が、統合されたデータブロック・サイズを生成すべく前記少なくとも１個のデータブロック・サイズを前記割振りの他のデータブロック・サイズに統合することにより、前記割振りのデータブロック・サイズの個数が前記所定個数のメモリフレームのサイズの個数に一致するまで、前記データブロック・サイズ割振りの少なくとも１個のデータブロック・サイズを反復的に除去するように構成され、前記他のデータブロック・サイズが前記少なくとも１個のデータブロック・サイズより大きく且つ前記統合されたデータブロック・サイズが前記他のデータブロック・サイズに一致しており、前記処理装置が統合すべきデータブロック・サイズをスラック予測アルゴリズムにより選択すべく適合されており、
前記処理装置が、前記メモリフレームの各々のサイズを、前記除去の後も残る前記割振りのデータブロック・サイズの１つのサイズであるように、且つ前記メモリフレームの各サイズが異なるように、決定するよう構成されている、処理装置。
【請求項１８】
前記処理装置は、統合するデータブロック・サイズを前記スラック予測アルゴリズムにより選択するように適合されており、前記アルゴリズムに従い前記少なくとも１個のデータブロック・サイズが、前記少なくとも１個のデータブロック・サイズを前記他のデータブロック・サイズに統合することにより少なくとも１回の反復の間に生じるスラックを最少限に抑えることに寄与するように、選択される、請求項１７に記載の処理装置。
【請求項１９】
前記処理装置は、各々の反復において、前記少なくとも１個のデータブロック・サイズが前記他のデータブロック・サイズに統合された際に、前記少なくとも１個のデータブロック・サイズを有するデータブロックの個数を前記他のデータブロック・サイズを有するデータブロックの個数に加算するように構成されている、請求項１７または１８に記載の処理装置。
【請求項２０】
前記処理装置は、前記割振りの最大データブロック・サイズ以外の各データブロック・サイズについて、各々の反復において、前記少なくとも１個のデータブロック・サイズが前記決定された割振りのより大きいデータブロック・サイズに組み込まれた場合に生じ得る予測スラックを決定するように適合されている、請求項１７〜１９のいずれか一項に記載の処理装置。
【請求項２１】
前記処理装置は、前記より大きいデータブロック・サイズを、前記決定された割振りのうち除去されていない次に大きいデータブロック・サイズとして決定するように構成されている、請求項１９に記載の処理装置。
【請求項２２】
前記スラック予測アルゴリズムが、各々の反復において、前記割振りの除去されていないデータブロック・サイズのうち、より大きいデータブロック・サイズに組み込まれた場合に生じ得るスラックを最少限に抑えるものがどれかを決定し、前記決定されたデータブロック・サイズを前記少なくとも１個のデータブロック・サイズの１つとして選択するステップを含む請求項１７〜２１のいずれか一項に記載の処理装置。
【請求項２３】
前記スラック予測アルゴリズムが、各々の反復において、前記割振りの除去されていないデータブロック・サイズに対して、合計予測スラックを示すスラック予測値を生成するステップを含む、請求項１７〜２１のいずれか一項に記載の処理装置。
【請求項２４】
前記データブロックの組が、メモリ（１２）を含み、前記処理装置（１３）が含まれるシステムの少なくとも１個の所定のプロセス用のデータブロックに関係する、請求項１７〜２３のいずれか一項に記載の処理装置。
【請求項２５】
前記データブロックの組が、少なくとも１つの信号のデータブロックに関係する、請求項１７〜２３のいずれか一項に記載の処理装置。
【請求項２６】
データブロックが前記メモリ（１２）に書き込まれる実行時に、前記データブロック・サイズ割振りを決定する、請求項１７〜２５のいずれか一項に記載の処理装置。
【請求項２７】
前記処理装置は、現行割振りにおいてデータブロック・サイズを除去する前に、少なくとも１個の可能な後続データブロック・サイズ割振りにおいて現行割振りの特定のデータブロック・サイズを除去する効果を調べるように構成されている、請求項１７〜２６のいずれか一項に記載の処理装置。
【請求項２８】
前記処理装置は、現行データブロック・サイズ割振りのデータブロック・サイズの個数に依存して、可能な後続データブロック・サイズ割振りの調べる個数を動的に変えるように構成されている、請求項２７に記載の処理装置。
【請求項２９】
前記処理装置は、現行データブロック・サイズ割振りに基づいて生成することができる各々の可能なデータブロック・サイズ割振りを決定して、現行および可能なデータブロック・サイズ割振りの各々に対してスラック予測値を生成するように構成されている、請求項２７または２８に記載の処理装置。
【請求項３０】
前記処理装置は、現行データブロック・サイズ割振りから前記少なくとも１個のデータブロック・サイズの第一のものを、現行および後続反復において生じ得る予測スラックの合計を最少限に抑えるデータブロック・サイズとして選択すべるように構成されている、請求項２９に記載の処理装置。
【請求項３１】
前記処理装置は、後続する反復から前記少なくとも１個のデータブロック・サイズの第二のデータブロック・サイズを選択して、前記第二のデータブロック・サイズを後続データブロック割振りの他のデータブロック・サイズに統合するように適合されている、請求項２７〜３０のいずれか一項に記載の処理装置。
【請求項３２】
前記処理装置は、前記他のデータブロック・サイズを、前記割振りに残る、前記割振り内の前記少なくとも１個のデータブロック・サイズの最大データブロック・サイズの次のデータブロック・サイズであるように選択するよう構成されている、請求項１７〜３１のいずれか一項に記載の処理装置。
【請求項３３】
コンピュータ・プログラム・コード手段を含む、コンピュータ・プログラム製品であって、
前記コンピュータ・プログラム・コード手段が、コンピュータ・プログラム能力を有する電子装置により実行された場合に、請求項１〜１６のいずれか一項に記載の方法を実行する、コンピュータ・プログラム製品。
【請求項３４】
前記コンピュータ・プログラム・コード手段が計算機可読媒体に具現化されている、請求項３３に記載のコンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の技術分野
本発明は、所定のサイズを有し、メモリ内にデータブロックを記憶すべく使用されるメモリフレームのサイズを決定する方法に関する。本発明はまた、本発明による方法を実行するのに適した処理装置に関する。
【背景技術】
【０００２】
関連技術の説明
動的メモリ割当ては、リアルタイムシステムにおいてメモリ・リソースに対する必要が生じた際にメモリを割当てるために用いられる。メモリ割当て装置におけるメモリ・リソースの動的な割当ては、多くの所定のメモリフレーム・サイズ、またはサイズが異なる多くのメモリフレームに限られる。すなわち各々のメモリフレームが多くのデータ・ビットを記憶できる場合がある。各々のメモリフレームの記憶容量は、メモリフレームの特定のビットがメモリ管理に用いられるため、実際のサイズと一致していなくてもよい。所定サイズのメモリフレームを有することで、メモリの割当ておよび割当て解除の実行時間に関して極めて予測可能に振舞うメモリ・アロケータを提供することが可能になる。しかし、これは性能にも影響を及ぼす。
【０００３】
所定サイズのメモリフレームを用いるメモリ割当てスキームの短所の一つは、内部フラグメンテーションまたはスラック（slack）と呼ばれる現象である。これは、要求されたメモリ・サイズ、すなわち記憶されるデータブロックのサイズが、当該サイズのデータブロックを記憶する能力を有する最小メモリフレームのサイズより小さい場合、異なる数のバイトは使用されず、すなわち内部フラグメンテーションとしても知られるスラックと化す。
【０００４】
スラックによる問題は、動的メモリ割当てを利用するあらゆる分野に影響を及ぼす。このような分野の二つとして、各プロセスにおいてメモリがスラックとして失われるプロセス処理、および各々の割当られた信号についてメモリがスラックとして失われる信号バッファの処理がある。しかし、特定のプロセスのメモリ要件は既知である。従って、極力スラックの発生を少なくするように、メモリフレームのサイズを設定することが可能である。また、信号のデータブロックの可能なサイズが分かっていれば、信号サイズを予測することにより（例えば、異なる使用事例について、動的メモリ割当て装置が実装されるシステムを実行することにより）、メモリフレームのサイズを予測された最適構成に設定することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
当分野で公知のシステムにおいて、メモリフレームのサイズは、プロセス／信号の全ての異なるデータブロック・サイズおよび各データブロック・サイズのデータブロックの個数を見て、次いでメモリフレームのサイズを適当なサイズに整える人物により、推定することができる。当該人物は、プロセス／信号のデータブロック・サイズの新たな組について、繰り返しこれを行なう必要がある。これは、長い時間を要し、そして、手動で決定されたメモリフレームのサイズが往々にして全く最適でないために、問題である。
【０００６】
メモリ・リソースが制限される移動端末等の埋め込み型システムにおいて、動的メモリ割当て装置を、所定メモリフレームの最適なサイズに設定することは、スラックに対して大きな影響を及ぼす。そのようなシステムでは、プロセスの数は、例えば、小規模システムで１０〜３０の範囲であって、より大規模なシステムで数百プロセスに到る場合がある。更に、各プロセスは数百種類の異なるデータブロック・サイズを含む場合があるが、メモリフレームの異なるサイズは、高々数十までの小さい範囲に限られる。同様に、信号のデータブロックの異なるサイズの個数は、プロセスのデータブロックの異なるサイズの個数と同じ範囲となることができる。このような電子装置におけるメモリ・リソースの節約は、生産コストに影響を及ぼし、大規模なシステムほど大きな影響を及ぼす。スラックの減少に起因してメモリ・リソースを制限できる場合、生産コストを下げることができる。
【課題を解決するための手段】
【０００７】
発明の概要
本発明の目的は、メモリ手段のために少なくとも１個のメモリフレームのサイズを決定する方法および装置を提供し、それにより、異なるサイズのデータブロックが前記メモリ手段の前記決定されたサイズ（群）を有するメモリフレームに記憶される際に生じるスラックを極力少なくすることである。
【０００８】
本発明の第一の態様によれば、本目的は、メモリにデータブロックを記憶するために割当てられる所定数のメモリフレームの各々のサイズを決定する方法により達成される。本方法は、少なくとも１組のデータブロックに対するデータブロック・サイズの割振り（data block size distribution）を決定するステップを含む。データブロック・サイズの個数がメモリフレームのサイズの個数と一致するまで、データブロック・サイズ割振りの少なくとも１個のデータブロック・サイズが反復的に除去される。前記少なくとも１個のデータブロック・サイズが、前記割振りの第一のデータブロック・サイズに統合されて、統合されたデータブロック・サイズが生成される。第一のデータブロック・サイズは、前記少なくとも１個のデータブロック・サイズより大きく、前記統合されたデータブロック・サイズのサイズは、第一のデータブロック・サイズに一致する。統合対象であるデータブロック・サイズは、スラック予測アルゴリズムにより選択される。メモリフレームのサイズは、除去の後も残る前記割振りのデータブロック・サイズであるように、決定される。
【０００９】
本方法はまた、前記少なくとも１個のデータブロック・サイズが第一のデータブロック・サイズに統合された際に、前記少なくとも１個のデータブロック・サイズを有するデータブロックの個数を、第一のデータブロック・サイズを有するデータブロックの個数に加算するステップを含んでいてよい。前記割振りの最大データブロック・サイズを除く各データブロック・サイズについて、且つ各々の繰り返しについて、少なくとも１個のデータブロック・サイズが、決定された割振りのより大きいデータブロック・サイズに組み込まれる場合に生じるであろう予測スラックを、決定することができる。前記より大きいデータブロック・サイズは、決定された割振りのうち除去されていない次に大きいデータブロック・サイズであってよい。あるいは、除去されていない任意のより大きいデータブロック・サイズが、前記より大きいデータブロック・サイズとして選択される。
【００１０】
スラック予測アルゴリズムは、各々の反復において、前記割振りの除去されていないデータブロック・サイズのうち、それがより大きいデータブロック・サイズに組み込まれた場合に、スラックの発生を最少限に抑えるものを、決定するステップを含んでいてよい。次いで、決定されたデータブロック・サイズは、前記少なくとも１個のデータブロック・サイズのうちの１個として選択される。スラック予測アルゴリズムはまた、各々の反復において、前記割振りの除去されていないデータブロック・サイズの予測スラックの合計を示すスラック予測値を生成するステップを含んでいてよい。
【００１１】
データブロックの組は、メモリを含むシステムの少なくとも１個の所定のプロセス向けのデータブロックに関係していてよい。あるいは、データブロックの組は、少なくとも１個の信号のデータブロックに関係する。データブロック・サイズの割振りは、実行時、例えばデータブロックがメモリに書き込まれる際に、決定することができる。次いで、本発明の方法は、処理能力が利用可能である場合（processing capacity is available）はいづでも、または所定のイベントに応答して、単位時間当たり最大メモリ書込み／読出し回数でもって、実行可能である。
【００１２】
現行割振りにおいてデータブロック・サイズを除去する前に、少なくとも１個の可能な後続データブロック・サイズ割振り（following possible data block size distribution）において、現行割振りの特定のデータブロック・サイズを除去する効果を調べることができる。可能な後続割振りを決定するため任意の反復回数を行ってよく、例えば前記割振りのデータブロック・サイズの個数に依存するように（in dependence of）、適宜設定することができる。
【００１３】
現在の、且つ可能なデータブロック・サイズ割振りの各々に対するスラック予測値を生成することができる。次いで、現行データブロック・サイズ割振りから、前記少なくとも１個のデータブロック・サイズのうちの１個を、現在および後続割振りの合計において最も低い予測スラックを生成するデータブロック・サイズであるように、選択することができる。また、前記少なくとも１個のデータブロック・サイズの第二のものを、後続の反復から選択して、後続するデータブロック割振りの他のデータブロック・サイズに統合することができ、その場合、各々の反復において複数のデータブロックが統合することができる。
【００１４】
前記少なくとも１個のデータブロック・サイズに統合される第一のデータブロック・サイズが、前記割振りに残される、前記割振り内における前記少なくとも１個のデータブロック・サイズの最大のデータブロック・サイズの次のデータブロック・サイズであってもよい。
【００１５】
本発明の第二態様によれば、本目的は、本発明の方法を実行すべく構成された処理装置により実現される。該処理装置は、処理能力が比較的小さい携帯式電子装置、または処理能力がより大きいコンピュータにおいて提供することができる。プロセッサはまた、実行時に（in run-time）本発明の方法を実行すべく適合されていてよい。
【００１６】
本発明の他の実施形態は、従属請求項に定義されている。
【００１７】
本発明の利点は、メモリフレームのサイズを手動で決定する必要がなく、メモリ・リソースの消費が減少する点である。また、本発明の方法を実行時に用いた場合、メモリ要件（memory requirements）の変化に伴ない、メモリフレームのサイズを適宜調整することができる。また、メモリフレームのサイズを実際のニーズに合わせて調整することにより、メモリ・リソース、従ってコストもまた節約できる。メモリフレームのサイズ変更は、手動で行なうよりも頻繁に行なうことができる。また、新規システム・プラットフォームに対してメモリフレームのサイズを容易に調整することも可能である。更に、結果的に生じるスラックが最小限に抑えられることにより、メモリ要件を最適化できる点が本発明の利点である。
【００１８】
本明細書で用いる「含む／含んでいる」という用語は、記述された特徴、完全体（integers）、ステップまたは構成要素の存在を指定するものの、１個以上の他の特徴、完全体、ステップ、構成要素またはそれらのグループの存在または追加を排除しない点を強調しておかなければならない。
【００１９】
本発明の更なる目的、特徴および利点は、添付の図面を参照しつつ、本発明の以下の詳細説明により明らかになる。
【発明を実施するための最良の形態】
【００２０】
実施形態の詳細な説明
図１に、本発明による装置および方法を実装可能な電子装置を示す。この例における電子装置は、移動電話１として実施されているがこれに限定されない。携帯電子装置ではメモリ・リソースが制限され、より大きなメモリを追加するためのコストによりコスト増に至ることから、本発明は、移動無線端末、ポケットベル、コミュニケータ、電子手帳、スマートフォンその他の携帯情報端末等、これらのパラメータが優先される携帯電子装置で有用である。しかし、本発明はまた、コンピュータ等の固定電子装置に実装されてもよいし、または固定電子装置によって実行されてもよい。より具体的には、本方法は任意のプロセッサによって実行することができ、他の電子装置のメモリのために実行可能である。説明の便宜上、以下では移動電話１のみ参照する。
【００２１】
移動電話１は、例えば基地局へ／基地局からの位置データの提供／受信、時計機能、到着信号の走査、ページング処理等、ネットワークとの通信のような各種のプロセスを実行する各種の回路を含んでいる。移動電話１において、多くのプロセスが、移動電話１を正しく機能させるためだけに動作している。例えばＷＣＤＭＡ（広帯域符号分割多重アクセス）ネットワークにおける通信に適合されている移動電話内では、そのような処理が数百、存在する場合がある。その上に、必須ではないが、移動電話１の設計変更に起因して、および／または移動電話１のカメラ、手帳、電話帳、およびメディアプレーヤ機能等、追加的な機能特徴のために、プロセスが追加される場合がある。
【００２２】
図２に、移動電話１の特定の構成要素を示す。例えば受信器、送信器および入力／出力信号を処理する回路を含む入出力インタフェース１０が、例えば移動ネットワーク等の無線または有線ネットワークを介して、外部電子装置と通信すべく構成されている。不揮発性メモリ１１およびＲＡＭ（ランダムアクセスメモリ）１２がＣＰＵ（中央処理装置）１３に接続されている。ＣＰＵ１３がプロセスを実行しない場合、当該プロセスに関係するデータブロックをメモリ１１に記憶することができる。プロセスが実行される場合、データブロックをメモリ１１より高速なＲＡＭ１２に一時的に記憶することができる。ＲＡＭ１２は、ＣＰＵ１３により処理される予定または処理済みであるプロセスに関係するデータブロックを一時的に記憶する。ＲＡＭ１２は、各々の進行中のプロセスのデータブロックを記憶することができる。
【００２３】
ＲＡＭ１２はまた、ＲＡＭ１２が実装されているシステムで動作している信号のデータブロックを記憶するために、任意の数の信号バッファを実装するように適合されていてよい。
【００２４】
ＲＡＭ１２は、動的メモリ割当てに適合されていてよく、その場合、メモリフレームは所定の数の異なるメモリフレーム・サイズにリアルタイムに割当てられ、そのサイズは予め定められている。メモリフレーム・サイズを決定することができる。割当て済みのメモリフレームは後で割当てを解消でき、例えばメモリ・リストにより管理され、その場合、割当られたメモリフレームのアドレスおよびそのサイズが記憶される。特定サイズのデータブロックを記憶するために十分に大きいサイズを有する解放されたメモリフレームの中に利用可能なメモリフレームが存在しない場合、他の所定のサイズを有する新規メモリフレームが割当てられる。
【００２５】
メモリフレームのサイズは、メモリフレームを使用する装置以外のコンピュータシステムで決定することができる。あるいは、メモリフレームのサイズは、それらがＣＰＵ１３により使用されるシステム内で決定される。
【００２６】
次いで、本発明による方法は、処理能力が利用可能である場合等に、メモリへの／メモリからの単位時間当たりの最大書込み／読出し回数に達した等の所定のイベントに応答して、または所定の時間間隔で、リアルタイムに実行することができる。極力スラックの発生が少なくなるようにメモリフレームのサイズを決定すべく、少なくとも１個のプロセスのバッファサイズ要件、すなわち、当該プロセスに関係する全ての想定できるデータブロックのサイズが調べられる。一緒に評価されるシステムのプロセスが多いほど、メモリフレームのサイズがより正確に決定され、従って、プロセス（群）を実行する際に全体で生じるスラックが少なくなる。その結果、なるべく多くのプロセス、例えばＲＡＭ１２を含むシステムをセットアップする際に分かっている全てのプロセスが同時に評価されたならば好都合である。
【００２７】
図３に３種のプロセス、すなわちプロセスＡ、プロセスＢ、プロセスＣを示す。任意の数のプロセスを一緒に評価することができる。プロセスＡは、６個のデータブロック１０１〜１０６、プロセスＢは７個のデータブロック１１１〜１１７、プロセスＣは５個のデータブロック１２１〜１２５を含んでいる。各々のデータブロック１０１〜１０６、１１１〜１１７、１２１〜１２５は特定のサイズを有する。すなわち各々のデータブロック１０１〜１０６、１１１〜１１７、１２１〜１２５内の数字により示される特定数のデータ・ビットを含んでいる。移動電話１内のプロセスの場合、データブロック・サイズの個数は、例えば３００であってよい。しかし、任意の数のデータブロック・サイズを用いてもよい。プロセスＡ、プロセスＢ、およびプロセスＣのデータブロック１０１〜１０６、１１１〜１１７、１２１〜１２５は、一緒に評価される場合、１組のデータブロックすなわち組ＡＢＣを構成する。あるいは、各プロセスは別々に評価され、その場合各プロセスのデータブロックはデータブロックの別々の組となる。
【００２８】
本発明の方法によれば、組ＡＢＣのような少なくとも１組のデータブロックのデータブロック・サイズ割振りが決定される。特定のサイズを有するデータブロックの個数がカウントされて割振りが生成される。
【００２９】
図４ａに組ＡＢＣの割振りを示す。第一カラムに、組ＡＢＣ内の特定サイズのデータブロックの個数を示し、第二カラムに、当該データブロック・サイズを示し、第三カラムに、当該データブロック・サイズが前記割振り内の他のデータブロック・サイズに統合された場合の予測スラックを示す。一実施形態によれば、予測スラックを以下のように定義することができる。
【００３０】
（データブロック・サイズがＰであるデータブロックの予測スラック）＝（サイズがＰであるデータブロックの個数）×（（データブロック・サイズＰと統合されるデータブロック・サイズ）−（データブロック・サイズＰ））。データブロック・サイズＰと統合されるデータブロック・サイズは、例えば当該データブロック・サイズ割振り内の任意の後続データブロック・サイズであってよい。本実施形態において、実際にプロセスが使用するデータブロック・サイズだけが利用される。これは、システムが使用しないデータブロック・サイズが利用される場合よりも、生じるスラックが少ないため有利である。
【００３１】
データブロック・サイズ割振りのデータブロック・サイズの個数を減らし、そのようにメモリフレームのサイズを決定する一実施形態を図４ａ〜４ｅに示す。本実施形態において、メモリフレーム・サイズの個数を３個と仮定するが、他の実施形態では任意の数であってよい。組ＡＢＣのデータブロック・サイズの個数は７個である。データブロック・サイズの個数は、データブロック割振りのデータブロック・サイズの個数がメモリフレームのサイズの個数と一致するまで、データブロック・サイズ割振りの第一のデータブロック・サイズを第二のデータブロック・サイズと反復的に統合することにより、減少する。第二のデータブロック・サイズは第一のデータブロック・サイズより大きく、統合されたデータブロックのサイズは第二のデータブロック・サイズと一致する。
【００３２】
他のデータブロック・サイズと結合すべきデータブロック・サイズは、以下に述べるようにスラック予測アルゴリズムに基づいて決定される。
【００３３】
最初に、１組のデータブロックのデータブロック・サイズ割振りが決定される。次いで、スラック予測アルゴリズムを用いて、他のデータブロック・サイズに統合すべき候補を見つける。スラック予測アルゴリズムの一実施形態によれば、予測スラックを最小限に抑えるデータブロック・サイズが、他のデータブロック・サイズと統合するものとして選択される、しかし、以下に述べるように、任意のより大きいデータブロック・サイズを選択してもよい。図４ａにおいて、データブロック・サイズ３は、データブロック・サイズ４に統合される場合、最小のスラックを生じる。図４ａ〜４ｅにおいて、全ての除去によって生じる合計スラックが登録される。しかし、これは本発明の全ての実施形態で必要な訳ではない。
【００３４】
図４ｂに、データブロック・サイズ３がデータブロック・サイズ４に統合された後の、データブロック・サイズの残りの割振りを示す。第一のデータブロック・サイズを有するデータブロックの個数が、第二のデータブロック・サイズを有するデータブロックの個数に加算されている。すなわち、データブロック・サイズが３であるデータブロックの個数が、データブロック・サイズが４であるデータブロックの個数に加算されている。次いで、各々のデータブロック・サイズについて新規の予測スラックを上述のように計算する。図４ｂの残りのデータブロック割振りについては、データブロック・サイズ１０をデータブロック・サイズ１１に統合することにより、次の反復で最小のスラックが生じると判定することができる。
【００３５】
図４ｃに、データブロック・サイズ１０を除去した後のデータブロック・サイズの残りの割振りおよびデータブロック・サイズの除去の次の反復を示す。データブロック・サイズ１０がデータブロック・サイズ１１に統合され、その場合に、図４ｃの割振り内のデータブロック・サイズ１１を有するデータブロックの個数が２から５に増やされた。予測スラックを決定した後で、データブロック・サイズ５をデータブロック・サイズ６に統合することにより、次の反復において最小のスラックが生じると判定することができる。
【００３６】
図４ｄに、データブロック・サイズ５を除去した後のデータブロック・サイズの残りの割振りおよびデータブロック・サイズの除去の次の反復を示す。データブロック・サイズ５がデータブロック・サイズ６に統合され、その場合に、図４ｄの割振り内のデータブロック・サイズ６を有するデータブロックの個数が３から６に増やされた。予測スラックを決定した後、データブロック・サイズ４をデータブロック・サイズ６に統合することにより、次の反復において最小のスラックが生じると判定することができる。
【００３７】
図４ｅに、データブロック・サイズ４を除去した後のデータブロック・サイズの残りの割振りおよびデータブロック・サイズの除去の次の反復を示す。データブロック・サイズ４がデータブロック・サイズ６に統合され、その場合に、図４ｅの割振り内のデータブロック・サイズ６を有するデータブロックの個数が４から１０に増やされた。ここで、データブロック・サイズの残りの割振りは３個の異なるサイズを含み、すなわちメモリフレームの個数と同じ数となって、反復は終了する。プロセスが実行されるシステムに使用されるメモリフレームのサイズは、残りの割振りのデータブロック・サイズのサイズであるように、決定される。図４ａ〜４ｅの実施形態において、メモリフレームのサイズは、６、８および１１であると決定される。
【００３８】
図４ａ〜４ｅの実施形態から分かるように、除去されたデータブロック・サイズのサイズが常に、自身が統合されるデータブロック・サイズより小さいため、最大のデータブロック・サイズは除去されない。
【００３９】
上述の実施形態において、各々の反復において１個のデータブロック・サイズしか除去されない。しかし、各々の反復において１個以上、すなわち少なくとも１個のデータブロック・サイズを除去することができる。例えば、スラック予測アルゴリズムは、予測スラックが最も少ないｎ個のデータブロック・サイズが、予測スラックが最も少ない前記データブロックより大きい他のデータブロック・サイズに組み込まれることを必要とするものであってよい。あるいは、各々の反復で、複数のデータブロック・サイズが、より大きい異なるデータブロック・サイズに統合される。
【００４０】
別のスラック予測アルゴリズムによれば、特定のデータブロック・サイズを除去する結果が、実際に１個のデータブロック・サイズが他のデータブロック・サイズに統合されるべく選択される前に、評価される。現行割振りにおいて最小のスラックを生じると予測されるデータブロック・サイズを、現行割振りにおいて選択することは、後続の割振りのデータブロック・サイズの合計スラック合計または予測スラックについて必ずしも最適ではない。評価対象となる後続割振りの数は、例えば、利用可能な処理リソースに応じて設定してもよい。従って、携帯機器において、評価対象となる可能な後続割振りまたは反復の数は、例えば１〜３であってよく、一方、コンピュータでは、全ての可能な後続割振りを評価することができる。また、本方法がリアルタイムで動作する場合、評価対象となる後続反復の数は、例えば現行データブロック割振りのデータブロック・サイズの個数に応じて、または除去されたデータブロック・サイズの合計の個数に応じて、設定されてよい。
【００４１】
図５ａ〜５ｆに、将来の反復の結果を考慮するスラック予測アルゴリズムの結果を示す。初期または現行データブロック・サイズ割振りを図５ａに示す。メモリフレームのサイズの個数は４であると仮定する。各々の可能な将来割振りに対して、特定のデータブロック・サイズを他のデータブロック・サイズに統合することが、将来生じるスラックにどのように影響するかを示す、スラック予測値（ＳＰＶ）が決定される。スラック予測値は、データブロック・サイズ割振りのうち、特定のデータブロック・サイズが除去された場合も残るであろう割振りのうち最も大きいデータブロック・サイズを除く全てのデータブロックについての予測スラックの合計であってよい。このように、図５ａの割振りにおいて何らかの除去を行なう前に、特定のデータブロック・サイズを除去する結果がスラック予測アルゴリズムに従い決定される。図５ｂに、図５ａの割振りにおいてデータブロック・サイズ４を除去した結果を示し、この場合スラック予測値は２２である。図５ｃに、図５ａの割振りにおいてデータブロック・サイズ５を除去した結果を示し、この場合スラック予測値は２９である。図５ｄに、図５ａの割振りにおいてデータブロック・サイズ６を除去した結果を示し、この場合スラック予測値は３１である。図５ｅに、図５ａの割振りにおけるデータブロック・サイズ８を除去した結果を示し、この場合スラック予測値は２２である。スラック予測値は、図５ａの表の列４に集約されている。
【００４２】
図５ｂ〜５ｅに見られるように、図５ｂ、５ｅの割振りは、最も少ないスラック予測値、すなわち２２を有する。このように、スラック予測アルゴリズムの一実施形態によれば、データブロック・サイズ４または８のいずれも、図５ａの現行割振りにおいて除去すべく選択することができる、すなわち最も少ないスラック予測値を有する後続割振りを生成するデータブロックである。
【００４３】
しかし、データブロック・サイズ５が図５ｅの割振りから除去されたならば、後続の反復において生じる可能性のある最も少ないスラックとなるであろう。この場合、後続反復におけるスラックは３となろう。このように、スラック予測アルゴリズムの他の実施形態でも、少なくとも１個の可能な後続反復における各データブロック・サイズに対する予測スラックが評価され、この場合、後続割振りで最小のスラックを生じるであろう、現行割振りで除去すべきデータブロックを、スラック予測アルゴリズムに従い選択することができる。
【００４４】
後続割振りにおいて予測スラックを最少にするには、図５ａの割振りにおけるデータブロック・サイズ８を除去する必要があり、この場合９個のスラックが伴い、これに図５ｅの割振りにおけるデータブロック・サイズ５の除去が続き、この場合スラックの合計は１２個となる。しかし、図５ａの割振りから出発して、データブロック・サイズ４を除去し、次いで図５ｂの割振りからデータブロック・サイズ６を除去した結果生じるスラックは、合計４＋６＝１０個のスラックを生成する。図５ａの割振りから出発して、データブロック・サイズ５を除去し、次いで図５ｃの割振りからデータブロック・サイズ４を除去した結果生じるスラックは、合計３＋８＝１１個のスラックを生成する。図５ａの割振りから出発して、データブロック・サイズ６を除去し、次いで図５ｄの割振りからデータブロック・サイズ４を除去した結果生じるスラックは、合計６＋４＝１０個のスラックを生成する。従って、この場合、および図５ａのデータブロック・サイズ割振りから出発して、図５ａに示す割振りからデータブロック・サイズ４または６を、次いで後続割振りからデータブロック・サイズ６（図５ｂ）または４（図５ｄ）を除去することにより、全体で最小のスラック（この場合は１０になる）が生じる、と判定することができる。結果として、スラック予測アルゴリズムの他の実施形態によれば、現行割振りにおいて除去すべきデータブロック・サイズは、可能な後続する除去と共に、最小のスラックを生じるもの、例えば図の５ａにおけるデータブロック・サイズ６または４である。従って、各々の反復において最小のスラックを生じるデータブロック・サイズを除去することは必ずしも最適でないことがわかるであろう。
【００４５】
スラック予測アルゴリズムの更に別の実施形態によれば、現行割振りの各々のデータブロック・サイズに対する重み付きスラック予測値（ＷＳＰＶ）を生成することができる。各々の重み付きスラック予測値は、現行割振りの特定のデータブロック・サイズの予測スラックおよび、前記特定のデータブロック・サイズが除去された場合に生成されるであろう後続割振りのスラック予測値に基づいている。重み付きスラック予測値を図５ａの列５に示す。重み付きスラック値の予測値のために、以下のアルゴリズムを用いることができる。
【００４６】
ＷＳＰＶ＝Ｃ１（予測スラックデータブロック・サイズＰ）＋Ｃ２（データブロック・サイズＰが除去された結果生じるスラック予測値）。ここに、Ｃ１およびＣ２は重み係数である。Ｃ１およびＣ２は、現行割振りで予測スラックの方が、付随するスラック予測値よりも重要性が高いと考えられるように、例えばＣ１＝０．７５、Ｃ２＝０．２５にように、選択することができる。しかし、他の重み付き係数および重み付きアルゴリズムも可能であって、各々の特定の実装についてテストおよび評価されなければならない。予測スラックに対し、スラック予測値より大きい重みを与えることは、現行割振りにおいて、将来の除去に影響を及ぼす誤った決定を下すリスクが減少する。
【００４７】
図５ａ〜５ｅに示す実施形態において、最小のスラックを生じると予測されるデータブロック・サイズは、他のデータブロック・サイズに統合するものとして選択されず、それによって合計スラックが最少値とすることができるかもしれない。その代わりに、最小の重み付きスラック予測値を有するデータブロック・サイズが、図５ａの割振りにおいて除去すべく選択され、この場合図５ｆの割振りが生成され、これは図５ｂの割振りに一致する。データブロック・サイズの個数が、メモリフレームのサイズの個数と一致するため、除去が終了されて、メモリフレームのサイズが、図５ｆのデータブロック・サイズであるように、決定される。
【００４８】
現行割振りから特定のデータブロック・サイズを除去した結果の評価を、任意の回数の将来の反復について行なうことができる。しかし、現実の実行における処理でのデータ量に起因して、このような予測を、将来可能な１、２回の反復で行なうことが予見できよう。図５ａ〜５ｅに示す実施形態において、可能な後続割振り内でスラック予測値が最も低い後続割振り、すなわち、スラック予測値が２２である図５ｂの割振り（図５ａの割振りにおいてデータブロック・サイズ４を除去することにより生成される）を生成する現行割振りにおいて、除去すべきデータブロック・サイズを選択することにより、最適な結果が実現されることが分かる。同じ結果が、最小重み付きスラック予測値を有するデータブロック・サイズを除去することにより、実現される。
【００４９】
上述のように、本発明による方法は、コンピュータベースドシステムまたはプロセッサを有する電子装置の、少なくとも１個の所定のプロセス用の１組のデータブロックに関する。あるいは、本発明による方法は、少なくとも１つの信号に関するデータブロックの少なくとも一つの組に適用される。信号は、移動電話１内の各種の機能に関係していてよく、ＣＰＵ１３により処理されて、信号バッファを実装可能なＲＡＭ１２に一時的に記憶できる。信号は、プロセス間の情報のやり取りであってよく、ＲＡＭ１２によって実装されたメモリバッファに記憶されたデータブロックの組であってよい。信号のデータブロックは、システム内のプロセス間で、メモリバッファに記憶されたデータブロックの所有権を第一プロセスから第二プロセスへ渡すことにより、伝達することができる。プロセス・スタックと信号の主な違いは、データブロックがＲＡＭ１２に記憶される期間にある。信号のデータブロックは、持続期間が例えば＞５μｓ且つ＜ｌｓの範囲であるのに対し、プロセススタックのデータブロックの持続期間は＞ｌｓであってよい。上で述べたプロセスに関して、信号は各種のサイズのデータブロックを含み、ＲＡＭ１２用のメモリフレームのサイズと一致しても、または一致しなくてもよい。従って、少なくとも１つの信号に関する１組のデータブロックを集めて、評価することができる。より具体的には、少なくとも１つの信号のデータブロックの少なくとも１組に対するデータブロック・サイズ割振りを、例えばデータブロックがＲＡＭ１２に書き込まれた際に、決定することができる。
【００５０】
図６に、本発明による移動端末の内部構成要素の第二の実施形態を示す。図６による実施形態は、基本的に図２の実施形態と一致している。従って、類似構成要素を同一参照番号で表記している。ＣＰＵ１３およびメモリ１１は、ＲＡＭ１２に書き込まれるデータブロックのサイズを登録する手段、すなわちデータブロック・サイズ登録ユニット１４に接続されている。データブロック・サイズ登録ユニットは、ＲＡＭ１２に書き込まれるデータブロックのサイズを登録するように構成されていて、ＣＰＵ１３によりソフトウェアユニットとして、あるいはＦＰＧＡ（フィールド・プログラム可ゲートアレイ）、ＡＳＩＣ（アプリケーション固有集積回路）またはプロセッサ等のスタンド・アローン型ハードウェア構成要素により、実装されていてよい。
【００５１】
データブロック・サイズ登録ユニット１４は、データブロック・サイズ、すなわちＲＡＭ１２へ転送される各データブロックについて、データブロックのビット数を登録するように適合されていてよい。次いで、ＲＡＭ１２に書き込まれたデータブロックのサイズ用のデータブロック・サイズ割振りをメモリ１１に記憶して、連続的に更新することができる。あるいは、ＲＡＭ１２に書き込まれたデータブロック用のデータブロック・サイズ割振りが、データブロック・サイズ登録ユニット１４と一体化されたメモリに記憶される。更に、データブロック・サイズ登録ユニット１４はまた、割当られたメモリフレームの個数、および現在使用中の割当てられたメモリフレームの個数等、メモリフレームの割当てを登録するように適合されていてよい。
【００５２】
ＣＰＵ１３は、データブロック・サイズ登録ユニット１４により生成されたデータブロック・サイズ割振りを評価することができる。あるいは、コンピュータ等、移動電話１の外部に設けられた処理装置が、データブロック・サイズ登録ユニット１４により生成されたデータブロック・サイズ割振りを評価する。
【００５３】
データブロック・サイズ登録ユニット１４により生成されたデータブロック・サイズ割振りは、所定個数のデータブロックがＲＡＭ１２に記憶された時、例えば、ＲＡＭ１２に記憶されたデータブロックの個数が、ＲＡＭ１２に現在割当てられているメモリフレームの個数に等しくなった場合に、評価されてよい。次いで、要求されたメモリリソースの局所最大値が必要な場合に（when local maximums of requested memory resources are required）、データブロック・サイズ登録ユニット１４がＣＰＵ１３に通知することができる。所定の数のデータブロックがＲＡＭ１２に記憶されている場合、ＣＰＵは、データブロック・サイズ登録ユニット１４により生成された割振りを評価して、将来割当てるメモリフレームのサイズを決定することができる。記憶されたデータブロックが所定の数に到達した場合にのみ応答してメモリフレームのサイズを決定することは、データ処理を制限する利点がある。しかし、代替的に、メモリフレームのサイズを所定の時間間隔で決定してもよい。更にまた、メモリフレームのサイズを、ＲＡＭ１２への単位時間当たりの処理（読み出し／書き込み）が所定の数に到達した場合に、生成してもよい。
【００５４】
図４ａ〜４ｅおよび５ａ〜５ｅを参照して記述したのと同一原理により、信号用に決定されたデータブロック・サイズ割振りを評価し、メモリフレームのサイズを決定してもよい。
【００５５】
図７は、本発明の方法の一実施形態のフロー図である。第一のステップ２００において、データブロックの少なくとも１個の組について、データブロック・サイズ割振りが決定される。次いで、決定されたデータブロック・サイズ割振りの各データブロック・サイズについての予測スラックが、ステップ２０１において決定される。現行データブロック・サイズ割振りに対するスラック予測値が、ステップ２０２において決定される。ステップ２０３において、現行データブロック・サイズ割振りの２個のデータ・サイズが統合された場合に生成される、後続データブロック・サイズ割振りに対する予測された効果が、例えば図５ａ〜５ｅを参照して述べたように、決定される。任意の後続するｎ個のデータブロック・サイズ割振りに対する効果を、決定することができる。効果は、例えば、現行割振りにおいて２個のデータブロック・サイズが統合された場合に結果として生じる後続割振りにおける、データ・サイズ割振りに対するスラック予測値を決定することであってよい。ステップ２０４において、現行データブロック・サイズ割振りの第一のデータブロック・サイズに統合される現行割振りの少なくとも１個のデータブロック・サイズが、スラック予測アルゴリズムに基づいて選択される。前記少なくとも１個のデータブロック・サイズおよび第一のデータブロック・サイズを、例えば図４ａ〜４ｂまたは５ａ〜５ｂに関して記述されているように、スラック予測アルゴリズムにより測定することができる。しかし、統合すべきデータブロック・サイズはまた、他のスラック予測アルゴリズムに従い決定することができ、これらは各々の特定の実装において試験されるべきである。ステップ２０５において、前記少なくとも１個のデータブロック・サイズのデータブロックの個数が、第一のデータブロック・サイズのデータブロックの個数に加えられる。次いで、ステップ２０６において、データブロック・サイズが統合される。ステップ２０７において、メモリフレームのサイズの個数が、割振りに残っているデータブロック・サイズの個数と一致するか否かが判定される。ステップ２０７における答えがｎｏであれば、プロシージャはステップ２０１に戻り、その場合、残りのデータブロック・サイズ割振りの他のデータブロック・サイズが除去される。ステップ２０７における答えがｙｅｓである場合、プロシージャはステップ２０８へ進み、そこでメモリフレームのサイズが、残りのデータブロック・サイズ割振りのデータブロック・サイズであるように、決定される。
【００５６】
理解されるように、図７のフロー図に示すステップの全部を本発明による方法のあらゆる実施形態において実行する必要がある訳ではない。例えば、図４ａ〜４ｅに関して示す実施形態を実行する場合、ステップ２０２、２０３を実行する必要はない。更に、各々の反復において２個以上のデータブロック・サイズを除去することも可能である。任意の数のデータブロックについて、これらが後続割振りにおけるより大きいデータブロック・サイズに組み込まれると決定された場合、１回の反復で同一のより大きいデータブロック・サイズに組み込むことができる。これは例えば、可能な決定済みデータブロック・サイズ割振りに基づいて決定することができる。また、第一と第二、第三と第四のデータブロック・サイズを１回の反復で統合することが可能である。例えば、図５ａ〜５ｅの実施形態において、データブロック・サイズ８がデータブロック・サイズ１１に組み込まれている場合、図５ｅの割振りが生成される。次いで、最も少ない予測スラックを有する生成された割振りからのデータブロック・サイズが、より大きいデータブロック・サイズと直接統合されなければならないこと、すなわち、データブロック・サイズ５を図５ｅの割振りのデータブロック・サイズ６に統合しなければならないこと、が判定できる。従って、データブロック・サイズ８、５の両方が、図５ａの割振りから始まる１回の反復で除去されることにより、図５ａの割振りのデータブロック・サイズの個数が１回の反復で２だけ減少する。理解されるように、後続割振りが何個生成されたにせよ、任意の数のデータブロック・サイズを１回の反復で除去することができる。
【００５７】
本発明の方法はソフトウェアにより実行することができる。コンピュータ・プログラム・コード手段を含むコンピュータ・プログラム製品が、本方法を実行してよい。前記コンピュータ・プログラム・コード手段は、コンピュータ・プログラム機能を有する電子装置により実行された場合に、本発明を実行する。前記電子装置は、上述のコンピュータまたは移動電話１等、任意の処理装置であってよい。前記コンピュータ・プログラム・コード手段は、計算機可読媒体に実装することができる。
【００５８】
本発明を、特定の実施形態に関して上に記載した。しかし、上記以外の他の実施形態も本発明の範囲内で可能である。本方法をハードウェアまたはソフトウェアにより実行する、上述のものとは異なる方法のステップを、本発明の範囲内で提供することができる。本発明の異なる特徴およびステップを、上述のものとは別の仕方で組み合わせてもよい。本発明の範囲は、添付の特許請求項のみにより限定される。
【図面の簡単な説明】
【００５９】
図面の簡単な説明
【図１】本発明の方法により設定されたメモリを有する移動電話の正面図である。
【図２】本発明による装置の特定の構成要素のブロック図である。
【図３】サイズの異なるデータブロックを含む３個のプロセスのブロック図である。
【図４ａ】本発明による、データブロック・サイズの反復的減少の第一実施形態を示す表である。
【図４ｂ】本発明による、データブロック・サイズの反復的減少の第一実施形態を示す表である。
【図４ｃ】本発明による、データブロック・サイズの反復的減少の第一実施形態を示す表である。
【図４ｄ】本発明による、データブロック・サイズの反復的減少の第一実施形態を示す表である。
【図４ｅ】本発明による、データブロック・サイズの反復的減少の第一実施形態を示す表である。
【図５ａ】本発明による、データブロック・サイズの反復的減少の第二実施形態を示す表である。
【図５ｂ】本発明による、データブロック・サイズの反復的減少の第二実施形態を示す表である。
【図５ｃ】本発明による、データブロック・サイズの反復的減少の第二実施形態を示す表である。
【図５ｄ】本発明による、データブロック・サイズの反復的減少の第二実施形態を示す表である。
【図５ｃ】本発明による、データブロック・サイズの反復的減少の第二実施形態を示す表である。
【図５ｅ】本発明による、データブロック・サイズの反復的減少の第二実施形態を示す表である。
【図５ｆ】本発明による、データブロック・サイズの反復的減少の第二実施形態を示す表である。
【図６】本発明による装置の第二実施形態の特定の構成要素のブロック図である。
【図７】本発明による方法の一実施形態のフロー図である。
【図１】
2008516320.tif 000003
【図２】
2008516320.tif 000004
【図３】
2008516320.tif 000005
【図４ａ】
2008516320.tif 000006
【図４ｂ】
2008516320.tif 000007
【図４ｃ】
2008516320.tif 000008
【図４ｄ】
2008516320.tif 000009
【図４ｅ】
2008516320.tif 000010
【図５ａ】
2008516320.tif 000011
【図５ｂ】
2008516320.tif 000012
【図５ｃ】
2008516320.tif 000013
【図５ｄ】
2008516320.tif 000014
【図５ｅ】
2008516320.tif 000015
【図５ｆ】
2008516320.tif 000016
【図６】
2008516320.tif 000017
【図７】
2008516320.tif 000018
【手続補正書】
【提出日】平成18年8月11日(2006.8.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
メモリ（１２）の所定個数のメモリフレームの各々のサイズを決定する方法であって、前記メモリ（１２）が、割当てられる異なるサイズの所定個数のデータ・フレーム内のデータブロックを記憶するように適合されていて、
少なくとも１個のプロセスまたは信号の少なくとも１組のデータブロック（１０１〜１０６、１１１〜１１７、１２１〜１２５）について、データブロック・サイズの割振りを決定するステップであって、前記データブロックの組の各データブロックが特定のサイズを有する、ステップを含み、
統合されたデータブロック・サイズを生成すべく前記少なくとも１個のデータブロック・サイズを前記割振りの他のデータブロック・サイズに統合することにより、前記割振りのデータブロック・サイズの個数が前記所定個数のメモリフレームのサイズの個数に一致するまで、前記データブロック・サイズ割振りの少なくとも１個のデータブロック・サイズを反復的に除去するステップであって、前記他のデータブロック・サイズが前記少なくとも１個のデータブロック・サイズより大きく且つ前記統合されたデータブロック・サイズが前記他のデータブロック・サイズに一致し、統合すべきデータブロック・サイズがスラック予測アルゴリズムにより選択され、前記アルゴリズムに従い前記少なくとも１個のデータブロック・サイズ及び前記他のデータブロック・サイズが、前記少なくとも１個のデータブロック・サイズを前記他のデータブロック・サイズに統合することにより少なくとも１回の反復の間に生じるスラックを最少限に抑えることに寄与するように、選択される、ステップと、
前記メモリフレームの各々のサイズを、前記除去の後も残る前記割振りのデータブロック・サイズの１つのサイズであるように、且つ前記メモリフレームの各サイズが異なるように、決定するステップと、を含むことを特徴とする方法。
【請求項２】
各々の反復において、前記少なくとも１個のデータブロック・サイズが前記他のデータブロック・サイズに統合された際に、前記少なくとも１個のデータブロック・サイズを有するデータブロックの個数を前記他のデータブロック・サイズを有するデータブロックの個数に加算するステップを更に含む、請求項１記載の方法。
【請求項３】
前記割振りの最大データブロック・サイズ以外の各データブロック・サイズについて、各々の反復において、前記少なくとも１個のデータブロック・サイズが前記決定された割振りのより大きいデータブロック・サイズに組み込まれた場合に生じ得る予測スラックを決定するステップを含む、請求項１又は２記載の方法。
【請求項４】
前記より大きいデータブロック・サイズが、前記決定された割振りのうち除去されていない次に大きいデータブロック・サイズである、請求項２記載の方法。
【請求項５】
前記スラック予測アルゴリズムが、各々の反復において、除去されていない前記割振りのデータブロック・サイズのうち、より大きいデータブロック・サイズに組み込まれた場合に生じ得るスラックが最も少ないものがどれかを決定し、前記決定されたデータブロック・サイズを前記少なくとも１個のデータブロック・サイズの１つとして選択するステップを含む請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記スラック予測アルゴリズムが、各々の反復において、前記割振りの除去されていないデータブロック・サイズに対して、合計予測スラックを示すスラック予測値を生成するステップを含む、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記データブロックの組が、メモリ（１２）を含むシステムの少なくとも１個の所定のプロセス用のデータブロックに関係する、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記データブロックの組が、少なくとも１つの信号のデータブロックに関係する、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
データブロックが前記メモリ（１２）に書き込まれる実行時に、前記データブロック・サイズ割振りを決定するステップを含む、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
現行割振りにおいてデータブロック・サイズを除去する前に、少なくとも１個の可能な後続データブロック・サイズ割振りにおいて現行割振りの特定のデータブロック・サイズを除去する効果が調べられる、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
現行データブロック・サイズ割振りのデータブロック・サイズの個数に依存して、可能な後続データブロック・サイズ割振りの調べる個数を動的に変えるステップを含む、請求項１０に記載の方法。
【請求項１２】
現行データブロック・サイズ割振りに基づいて生成することができる各々の可能なデータブロック・サイズ割振りを決定して、現行および可能なデータブロック・サイズ割振りの各々に対してスラック予測値を生成するステップを含む、請求項１０または１１に記載の方法。
【請求項１３】
現行データブロック・サイズ割振りから、前記少なくとも１個のデータブロック・サイズの第一のものを、現行および後続反復において生じ得る予測スラックの合計を最少限に抑えるデータブロック・サイズとして選択するステップを含む、請求項１２に記載の方法。
【請求項１４】
後続する反復から前記少なくとも１個のデータブロック・サイズの第二のものを選択して、前記第二のデータブロック・サイズを後続データブロック割振りの他のデータブロック・サイズに統合するステップを含む、請求項１０〜１３のいずれか一項に記載の方法。
【請求項１５】
前記他のデータブロック・サイズが、前記割振りに残る、前記割振り内の前記少なくとも１個のデータブロック・サイズの最大データブロック・サイズの次のデータブロック・サイズである、請求項１〜１４のいずれか一項に記載の方法。
【請求項１６】
請求項１〜１５のいずれか一項に記載の方法に従い、メモリ（１２）の所定個数のメモリフレームの各々のサイズを決定するように構成されている処理装置（１３）。
【請求項１７】
コンピュータ・プログラム・コード手段を含む、コンピュータ・プログラム製品であって、
前記コンピュータ・プログラム・コード手段が、コンピュータ・プログラム能力を有する電子装置により実行された場合に、請求項１〜１５のいずれか一項に記載の方法を実行する、コンピュータ・プログラム製品。
【請求項１８】
前記コンピュータ・プログラム・コード手段が計算機可読媒体に具現化されている、請求項３１に記載のコンピュータ・プログラム製品。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
メモリ・リソースが制限される移動端末等の埋め込み型システムにおいて、動的メモリ割当て装置を、所定メモリフレームの最適なサイズに設定することは、スラックに対して大きな影響を及ぼす。そのようなシステムでは、プロセスの数は、例えば、小規模システムで１０〜３０の範囲であって、より大規模なシステムで数百プロセスに到る場合がある。更に、各プロセスは数百種類の異なるデータブロック・サイズを含む場合があるが、メモリフレームの異なるサイズは、高々数十までの小さい範囲に限られる。同様に、信号のデータブロックの異なるサイズの個数は、プロセスのデータブロックの異なるサイズの個数と同じ範囲となることができる。このような電子装置におけるメモリ・リソースの節約は、生産コストに影響を及ぼし、大規模なシステムほど大きな影響を及ぼす。スラックの減少に起因してメモリ・リソースを制限できる場合、生産コストを下げることができる。
システムの、異なるシステム・リソースの量および種類を自動的に決定する従来方式のアルゴリズムが、ｘｐ０１０５８８１２６「動的再設定可能なＦＰＧＡを備えた低電力リアルタイム分散型埋め込みシステムのハードウェア／ソフトウェア相互の統合」（設計自動化会議、２００２）に開示されている。当該システム・リソースは動的再設定可能なＦＰＧＡ、プロセッサ、および他のシステム・リソースを含んでいる。当該アルゴリズムはまた、異なるシステム・リソースに対して実行されるタスクの割当てをも含んでいる。
ＸＰ−０００９０３９２７に、時間制約シングルレートシステム仕様をヘテロジニアスシステム仕様にマッピングするアルゴリズムが開示されている。ヘテロジニアスシステムは、プロセッサのメモリサイズ、通信リンクのバッファサイズ、およびＡＳＩＣの面積等、複数のリソース制約を含んでいる。
ＸＰ−００２２６２８４５はメモリ断片化に関係する。メモリブロックのサイズが断片化に関わることが開示されている。
ＵＳ−Ａ−６０８８７７７に、動的メモリ割当てのためのメモリシステムおよび管理方法が開示されている。固定メモリ領域を整数個数のクラスに分割する。各メモリクラスは、ポインタにより互いにリンクされた同一サイズのメモリブロックを含んでいる。メモリブロックサイズは各クラス毎に異なる。異なるメモリブロックのサイズが、特定のアプリケーションで処理される筈である様々なサイズのデータを収容すると共に、ハードウェアを除くＣＰＵおよびメモリアクセスに準拠すべく、選択されている。
【国際調査報告】
2008516320.tif 000019
2008516320.tif 000020
2008516320.tif 000021