(57)【要約】【課題】処理が利用するバッファをメモリ上に連続領域として確保できるようにする。【解決手段】メモリ割り当て装置は、バッファ割り当て情報出力モジュール５１１とバッファメモリ範囲決定モジュール５２２と処理モジュール５２４を具備する。バッファ用連続領域をメモリ上に確保する必要のある１以上の処理を処理名の集合で表し、それら処理間で並列実行されない処理の組合せを排他関係で表し、処理がバッファとして利用可能な１つ以上のメモリ範囲候補をバッファ割り当て情報ＢＡＩで表す。モジュール５１１は、処理名の集合、排他関係等に基づいてＢＡＩを処理毎に出力する。モジュール５２２は、処理名の集合に含まれる特定の処理を開始する際に、ＢＡＩに記述されているメモリ範囲候補のうち特定の処理を開始する時点で他の処理に利用されているメモリ範囲と重複しないメモリ範囲を選択する。モジュール５２４は、選択されたメモリ範囲をバッファとしてメモリに確保し、確保されたバッファを用いて特定の処理を実行する。【選択図】図１
2011034510.tif 000002
【特許請求の範囲】
【請求項１】
バッファとして用いる連続領域をメモリ上に確保する必要のある１以上の処理を処理名の集合で表し、それら処理間で並列実行されない処理の組合せを排他関係で表し、前記処理がバッファとして利用可能な１つ以上のメモリ範囲候補をバッファ割り当て情報で表すときに、前記処理名の集合および前記排他関係に基づいて、前記バッファ割り当て情報を前記処理毎に出力するバッファ割り当て情報出力モジュールと、
前記処理名の集合に含まれる特定の処理を開始する際には、前記バッファ割り当て情報に記述されているメモリ範囲候補のうち、前記特定の処理を開始する時点で他の処理に利用されているメモリ範囲と重複しないメモリ範囲を選択するバッファメモリ範囲決定モジュールと、
選択された前記メモリ範囲を前記バッファとして前記メモリに確保し、確保された前記バッファを用いて前記特定の処理を実行する処理モジュールを具備したメモリ割り当て装置。
【請求項２】
利用するバッファサイズが既知である処理に対して割り当てられるバッファ領域を静的バッファ領域とし、この静的バッファ領域以外のバッファ領域を動的バッファ領域とするときに、前記バッファとして利用可能な前記メモリの領域は前記静的バッファ領域と前記動的バッファ領域に分割され、
前記バッファメモリ範囲決定モジュールにより選択された前記メモリ範囲が、前記静的バッファ領域に対して適用される請求項１に記載のメモリ割り当て装置。
【請求項３】
新たにバッファとして連続領域を前記メモリ上に確保する必要のある第１の処理の名前、および、その第１の処理が利用するバッファのサイズを入力する処理情報入力モジュールと、
前記第１の処理と既に前記バッファ割り当て情報に含まれている処理との間の排他関係を入力する処理間排他関係入力モジュールをさらに具備した請求項１に記載のメモリ割り当て装置。
【請求項４】
バッファとして連続領域を前記メモリ上に確保する必要のなくなった第２の処理の名前を入力する処理情報入力モジュールをさらに具備し、
前記バッファ割り当て情報出力モジュールが、前記第２の処理以外の処理の集合と、前記第２の処理に関連する排他関係を現在利用している排他関係から削除した新たな排他関係に基づいて、前記バッファ割り当て情報を出力するように構成される請求項１に記載のメモリ割り当て装置。
【請求項５】
前記バッファ割り当て情報を格納する格納モジュールをさらに具備し、
前記バッファメモリ範囲決定モジュールが、前記格納モジュールに格納された前記バッファ割り当て情報を用いて前記メモリ範囲を選択するように構成される請求項１に記載のメモリ割り当て装置。
【請求項６】
前記バッファとして利用される可能性のある前記メモリの領域について、その領域のサイズの目標値を目標メモリサイズとするときに、この目標メモリサイズを決定する目標メモリサイズ決定モジュールをさらに備え、
並行動作する可能性のある処理組合せの各処理が利用するバッファメモリサイズの和の最大値を前記目標メモリサイズの初期値とし、前記排他関係にない処理の組合せであればどのような順序で処理が開始されても必ず処理が利用するバッファを選択できるようなバッファ割り当て情報を要求合致バッファ割り当て情報とするときに、前記目標メモリサイズの初期値では前記要求合致バッファ割り当て情報が前記バッファ割り当て情報に存在しない場合に、前記目標メモリサイズをその初期値から増加させるように、前記目標メモリサイズ決定モジュールが構成される請求項１に記載のメモリ割り当て装置。
【請求項７】
前記バッファとして利用される可能性のある前記メモリの領域について、その領域のサイズの目標値を目標メモリサイズとするときに、この目標メモリサイズを決定する目標メモリサイズ決定モジュールと、
前記目標メモリサイズをどのように決定するかに関する元の問題から部分問題を作成する部分問題作成モジュールをさらに備え、
前記排他関係にない処理の組合せであればどのような順序で処理が開始されても必ず処理が利用するバッファを選択できるようなバッファ割り当て情報を要求合致バッファ割り当て情報とするときに、前記部分問題の要求合致バッファ割り当て情報の必要メモリサイズを、前記元の問題の目標メモリサイズの初期値とするように、前記目標メモリサイズ決定モジュールが構成される請求項１ないし請求項６のいずれか１項に記載のメモリ割り当て装置。
【請求項８】
前記処理名の集合の情報、および、この処理名の集合が示す１以上の処理で利用される前記バッファのサイズ情報を入力する処理情報入力モジュールと、
前記排他関係の情報を入力する排他関係情報入力モジュールと、
前記バッファとして利用される可能性のあるメモリ領域のサイズの目標値を目標メモリサイズとするときに、この目標メモリサイズを設定する目標メモリサイズ決定モジュールと、
前記目標メモリサイズ決定モジュールにより設定された前記目標メモリサイズ内で前記処理が実行可能なメモリ割り当てを探索するバッファ割り当て探索モジュールと、
前記処理情報入力モジュールおよび前記排他関係情報入力モジュールにより入力された情報を用いて、前記バッファ割り当て探索モジュールによる探索範囲を絞り込む探索範囲絞り込みモジュールと、
前記バッファ割り当て探索モジュールによる探索で得られた前記バッファ割り当て情報で、前記排他関係にない処理が実行可能かどうかを判定する実行可能／不可能判定モジュールを備え、
前記バッファメモリ範囲決定モジュールが、前記排他関係にない処理組合せであれば、どのような順序で処理が開始されても処理が利用する前記バッファを選択するように構成され、かつ、
前記バッファ割り当て情報出力モジュールが、前記静的バッファ領域のサイズが最小になるような前記バッファ割り当て情報を出力するように構成された請求項２に記載のメモリ割り当て装置。
【請求項９】
映像情報のデータストリームを処理する際にバッファとして用いる連続領域を含むメモリと、前記メモリでバッファリングされた前記データストリームを記録再生するデータ記憶装置と、前記メモリ上に前記バッファとして用いる連続領域を割り当てるメモリ割り当て装置を備えた映像機器において、
前記バッファとして用いる連続領域を前記メモリ上に確保する必要のある１以上の処理を処理名の集合で表し、それら処理間で並列実行されない処理の組合せを排他関係で表し、前記処理がバッファとして利用可能な１つ以上のメモリ範囲候補をバッファ割り当て情報で表すときに、
前記メモリ割り当て装置が、
前記処理名の集合および前記排他関係に基づいて、前記バッファ割り当て情報を前記処理毎に出力するバッファ割り当て情報出力モジュールと、
前記処理名の集合に含まれる特定の処理を開始する際には、前記バッファ割り当て情報に記述されているメモリ範囲候補のうち、前記特定の処理を開始する時点で他の処理に利用されているメモリ範囲と重複しないメモリ範囲を選択するバッファメモリ範囲決定モジュールと、
選択された前記メモリ範囲を前記バッファとして前記メモリに確保し、確保されたバッファを用いて前記特定の処理を実行する処理モジュールを含んで構成される映像機器。
【請求項１０】
バッファとして用いる連続領域をメモリ上に確保する必要のある１以上の処理を処理名の集合で表し、それら処理間で並列実行されない処理の組合せを排他関係で表し、前記処理がバッファとして利用可能な１つ以上のメモリ範囲候補をバッファ割り当て情報で表すときに、前記処理名の集合および前記排他関係に基づいて、前記バッファ割り当て情報を前記処理毎に出力する方法であって、
利用するバッファサイズが既知である処理に対して割り当てられるバッファ領域を静的バッファ領域とし、この静的バッファ領域以外のバッファ領域を動的バッファ領域とするときに、前記バッファとして利用可能な前記メモリの領域が前記静的バッファ領域と前記動的バッファ領域に分割される場合において、
前記処理名の集合に含まれる特定の処理を開始する際には、前記バッファ割り当て情報に記述されているメモリ範囲候補のうち、前記特定の処理を開始する時点で他の処理に利用されているメモリ範囲と重複しないメモリ範囲を選択し、
選択された前記メモリ範囲を前記静的バッファ領域として前記メモリに確保し、確保された前記静的バッファ領域を用いて前記特定の処理を実行するメモリ割り当て方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データストリームの記録再生処理等において処理が利用するバッファをメモリ上に連続領域として確保するメモリ割り当て方法、および、この方法を用いるメモリ割り当て装置に関する。
【背景技術】
【０００２】
近年は大容量のハードディスクドライブ（ＨＤＤ）が安価に供給されるようになってきており、数百ギガバイトないしテラバイトクラスのＨＤＤがパーソナルコンピュータ（ＰＣ）、デジタルＴＶ、デジタルビデオレコーダなどに装備されている。このような大容量ＨＤＤは、動画情報を含むデータストリームの記録再生に多用される。
【０００３】
ＨＤＤに代表される大容量記憶メディアでは、高精細デジタルＴＶ放送など情報量の多いデータストリームの記録再生処理をスムースに行うために、比較的大容量の高速メモリ（バッファ）が用いられる。この種のメモリ（バッファ）の制御には、種々な提案がなされている。例えば、ＰＣ（ＡＶパソコン）やデジタルビデオレコーダ（ＨＤＤレコーダ）においてデジタルＴＶ放送ストリームの記録再生処理を実行する場合、その処理の実行にあたりメモリが必要になると、動的にメモリ領域を確保し利用する仕組みが提案されている（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−３２５１４５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１のデータ格納システムおよびそれを用いたデータ放送受信装置では、ＲＡＭ１４２のデータ領域は、割当要求に従ってバッファ領域が割り当てられるパーティション領域と、割当要求に従ってセグメント領域が割り当てられるリージョン領域を含んでいる。バッファ領域は所定の固定長データに対応し、セグメント領域は格納されるべきデータ長に対応する。演算処理部１４４は、デジタルデータのデータ長に応じて、パーティション領域とリージョン領域のいずれにデータを格納するかを決定し、割当要求を生成している。
【０００６】
特許文献１の動的バッファ確保方法は、実行される処理およびその処理が必要とするバッファサイズが静的に決定できない場合に有効である。しかし、デジタルＴＶ放送など情報量の多いデータストリームの記録再生処理をスムースに行うためには、十分なサイズのメモリ領域を用意しておく必要がある上、連続した領域を当該処理のバッファ用にいつでも確保できるという保証はない。
【０００７】
メモリ上で連続した領域を処理のバッファ用に確保できなかったときは、その処理のバッファとして利用する領域がメモリ上で分散され断片化する。バッファとして利用する領域が断片化すると、処理の実行にオーバーヘッドが発生する。また、メモリ上で連続した領域を処理のバッファ用に確保できなかったときは、バッファとして利用されているメモリ領域間に中途半端な利用されない空きメモリ領域ができることがある。そのような空きメモリ領域は無駄になる。
【０００８】
この発明の課題の１つは、処理が利用するバッファをメモリ上に連続領域として確保できるようにすることである。
【課題を解決するための手段】
【０００９】
この発明の一実施の形態に係るメモリ割り当て装置は、バッファ割り当て情報出力モジュール（５１１）と、バッファメモリ範囲決定モジュール（５２２）と、処理モジュール（５２４）を具備している。いま、バッファとして用いる連続領域をメモリ（５３０）上に確保する必要のある１以上の処理を「処理名の集合」で表し、それらの処理が利用するバッファのサイズを「バッファサイズ情報」で表し、それら処理間で並列実行されない処理の組合せを「排他関係」で表し、処理がバッファとして利用可能な１つ以上のメモリ範囲候補を「バッファ割り当て情報」で表す。その場合、バッファ割り当て情報出力モジュール（５１１）は、処理名の集合、バッファサイズ情報、および排他関係に基づいて、バッファ割り当て情報（ＢＡＩ）を処理毎に出力する。また、バッファメモリ範囲決定モジュール（５２２）は、処理名の集合に含まれる特定の処理を開始する際には、バッファ割り当て情報（ＢＡＩ）に記述されているメモリ範囲候補のうち、その特定の処理を開始する時点で他の処理に利用されているメモリ範囲と重複しないメモリ範囲（メモリ上で連続した領域）を、１箇所選択する。そして、処理モジュール（５２４）は、選択されたメモリ範囲をバッファとしてメモリ（５３０）に確保し、確保されたバッファを用いて特定の処理を実行する。
【発明の効果】
【００１０】
この発明によれば、処理が利用するバッファをメモリ上に連続領域として確保できる。
【図面の簡単な説明】
【００１１】
【図１】この発明の一実施の形態に係るメモリ割り当て装置の構成を説明する図。
【図２】この発明の他の実施の形態に係るメモリ割り当て装置の構成を説明する図。
【図３】バッファとして利用可能なメモリ領域の構成を説明する図。
【図４】バッファ割り当て情報を説明する図。
【図５】バッファとして利用可能なメモリ領域に利用できない無駄な領域が生じた場合を説明する図。
【図６】メモリ領域にバッファを割り当てる処理の一例を説明するフローチャート図。
【図７】バッファ割り当て情報の初期状態の一例を説明する図。
【図８】バッファを用いて２並列処理が行える場合（枝刈り後）の一例を説明する図。
【図９】バッファを用いて３並列処理が行えない場合（枝刈り前）の一例を説明する図。
【図１０】バッファを用いて３並列処理が行える場合（枝刈り後）の一例を説明する図。
【図１１】バッファ割り当て処理における深さ優先探索の一例を説明する図。
【図１２】バッファ割り当ての探索範囲が絞り込まれる前の、バッファ割り当て情報初期状態を説明する図。
【図１３】図２の部分問題作成部における処理の一例を説明するフローチャート図。
【図１４】図１または図２のメモリ割り当て装置の応用例を説明する図。
【図１５】図１または図２のメモリ割り当て装置を具備したデジタルビデオレコーダの構成の一例を説明する図。
【発明を実施するための形態】
【００１２】
以下、図面を参照してこの発明の種々な実施の形態を説明する。図１は、この発明の一実施の形態に係るメモリ割り当て装置の構成を説明する図である。このメモリ割り当て装置５００は、メモリ５３０に対してバッファ用連続領域をどのように割り当てるかを決定するもので、バッファ割り当て情報出力装置（バッファ割り当て情報出力モジュール）５１１、データ格納部（格納モジュール）５２０、バッファメモリ範囲決定部（バッファメモリ範囲決定モジュール）５２２、および、処理実行部（処理モジュール）５２４を具備している。
【００１３】
図２は、この発明の他の実施の形態に係るメモリ割り当て装置の構成を説明する図である。図２の構成は、バッファ割り当て情報出力装置５１１内に部分問題作成部（部分問題作成モジュール）５０５が追加された点を除き、図１の構成と同じである。部分問題作成部５０５の処理機能については、図１３等を参照して後述する。以下では、まず図１と図２で共通する構成について、説明する。
【００１４】
図１の構成において、メモリ５３０は、例えば複数の高精細映像信号ストリームの処理で利用可能なリードライトメモリであり、その処理に必要な容量と速度を持ったＳＲＡＭあるいはＤＲＡＭで構成される。このメモリ５３０には、ストリーム処理等のためにバッファとして利用可能なメモリ領域（バッファ領域）５３２を適宜確保できるようになっている。
【００１５】
図３は、バッファとして利用可能なメモリ領域５３２の構成を説明する図である。メモリ領域（バッファ領域）５３２は、図３に例示されるように、静的バッファ領域５３４と動的バッファ領域５３６に分割（または分離）され、それぞれ個別に管理される。ここで、静的バッファ領域５３４は、利用するバッファサイズが既知である処理に対して割り当てられるバッファ領域である。この静的バッファ領域５３４以外の領域５３２が動的バッファ領域５３６となる。
【００１６】
この発明の実施の形態は、静的バッファ領域５３４の使い方に特徴がある。動的バッファ領域５３６は、静的バッファ領域５３４を用いない処理あるいは静的バッファ領域５３４で賄い切れない処理で利用される。動的バッファ領域５３６の利用方法は周知の方法でよい。具体的には、動的バッファ領域５３６は、例えば前掲の特許文献１（特開２００１−３２５１４５号公報）におけるセグメント領域と同様に利用できる。
【００１７】
なお、動的バッファ領域５３６に対する「動的メモリ割り当て」には、別の既存方法を用いることもできる。この「動的メモリ割り当て」に関する既存の方法は、Ｃ言語におけるmalloc関数で利用されている。これについては下記文献参照：
Ｂ．Ｗ．カーニハン、Ｄ．Ｍ．リッチー、“プログラミング言語Ｃ”、共立出版、１９８９
図１の構成において、処理実行部５２４は、例えば機器組込用のコンピュータ（所定のファームウエアを実行するＣＰＵまたはＭＰＵ）で構成される。処理実行部５２４は、例えばあるストリーム処理Ａを実行しようとする場合、バッファメモリ範囲決定部５２２が選択するメモリ範囲を処理Ａの利用するバッファとしてメモリ５３０上に確保して、処理Ａを実行する。
【００１８】
バッファメモリ範囲決定部５２２は、処理実行部５２４がある処理Ａを開始する場合、データ格納部５２０に格納されているバッファ割り当て情報ＢＡＩから、１つのメモリ範囲を選択する。その１つとは、処理Ａがバッファとして利用可能なメモリ範囲の候補のうち他のストリーム処理が現在利用しているメモリ範囲と重複しないものをいう。その選択されたメモリ範囲の１つが、処理Ａのバッファとして利用されることになる。
【００１９】
ここで、実行しようとする処理が２以上ある場合、バッファメモリ範囲決定部５２２は、排他関係にない処理の組合せであれば、どのような順序でそれらの処理が発生しても、利用可能なバッファ範囲を必ず確保できるように構成されている（この点については後に詳述する）。
【００２０】
データ格納部５２０に格納されるバッファ割り当て情報ＢＡＩには、実行される可能性のある１以上のストリーム処理毎に、バッファメモリとして利用可能なメモリ範囲の候補が１つ以上含まれる。（バッファ割り当て情報ＢＡＩについては、図４等を参照して後述する。）
図１の構成において、バッファ割り当て情報出力装置５１１は、処理情報入力部（処理情報入力モジュール）５０１と、処理間排他関係入力部（処理間排他関係入力モジュール）５０２と、入力情報格納部５０３と、目標メモリサイズ決定部（目標メモリサイズ決定モジュール）５０４と、バッファ割り当て決定部５０９と、バッファ割り当て情報出力部５１０を含んでいる。ここで、バッファ割り当て決定部５０９は、実行可能／不可能判定部（実行可能／不可能判定モジュール）５０６、バッファ割り当て探索部（バッファ割り当て探索モジュール）５０７、および、探索範囲絞り込み部（探索範囲絞り込みモジュール）５０８により構成される。
【００２１】
処理情報入力部５０１からは、実行される可能性のある全ての処理について、処理名とその処理が利用するバッファサイズが入力される。
【００２２】
処理間排他関係入力部５０２からは、並列実行されない処理の組合せが入力される。（逆に、並列実行されるストリーム処理の組合せを処理間排他関係入力部５０２から入力する方法もある。並列実行される処理の組合せが分かれば、それ以外に存在する処理の組合せを、並列実行されない処理の組合せとして扱うことができる。）
入力情報格納部５０３には、処理情報入力部５０１および処理間排他関係入力部５０２から入力された情報が格納される。
【００２３】
バッファ割り当て情報出力装置５１１の目標メモリサイズ決定部５０４は、最初、静的バッファ領域５３４（図３参照）として利用するメモリのサイズ（目標値）を十分に小さい値と仮定し、利用可能なバッファ割り当て情報を探索する（その探索方法については後述する）。目標メモリサイズで実行可能なバッファメモリ割り当てが見つからない場合（換言すると、その目標メモリサイズでは「排他関係にない処理の組合せであれば、どのような順序で処理が発生しても、利用可能なバッファ範囲を必ず確保できる」とはいえない場合）、目標メモリサイズが更新（増加）され、実行可能なバッファ割り当て情報を探索する処理が繰り返される。このメモリサイズの目標値を設定し適宜更新するのが、目標メモリサイズ決定部５０４である。
【００２４】
ここで、静的バッファ領域５３４を用いて処理が実行可能な最小メモリサイズと最初に設定される目標メモリサイズとの差が大きいと、バッファメモリ割り当ての算出に多くの計算時間を要する。そのため、なるべく差が小さい目標メモリサイズを最初に設定するようにする。
【００２５】
実行可能／不可能判定部５０６は、現在のバッファ割り当て情報ＢＡＩで排他関係にない全ての処理組合せが実行可能かどうかを判定する（排他関係については後述）。
【００２６】
バッファ割り当て探索部５０７は、目標メモリサイズ決定部５０４で設定された目標メモリサイズ内で、処理が実行可能なメモリ割り当てを探索する。
【００２７】
探索範囲絞り込み部５０８は、バッファ割り当て探索部５０７が探索する範囲を絞り込む。探索範囲絞り込み部５０８は、入力部５０１および５０２からの入力情報等を利用して、効率よく実行可能なバッファ割り当て情報ＢＡＩを算出するために利用される。
【００２８】
バッファ割り当て情報出力部５１０は、処理が実行可能で、かつ、バッファ（静的バッファ領域５３４）として利用するメモリのサイズが最小となるバッファ割り当て情報ＢＡＩを出力する（その具体的方法は後述する）。
【００２９】
図４は、バッファ割り当て情報出力部５１０から出力されデータ格納部５２０に格納されるバッファ割り当て情報ＢＡＩが、どのような内容であるのかを説明する図である。図１または図２のデータ格納部５２０に格納されるバッファ割り当て情報ＢＡＩ（バッファメモリ割り当てのための情報）は、イメージ的には図４に例示されるようになる。図４には、７つの処理Ａ〜Ｇに対して、バッファメモリ（静的バッファ領域５３４）として利用可能な範囲の候補が例示されている。ただし、Ａ〜Ｇの各処理を実行するにあたり必要なバッファメモリサイズ（その単位は任意）は、処理Ａが２単位、処理Ｂが５単位、処理Ｃが３単位、処理Ｄが７単位、処理Ｅが４単位、処理Ｆが７単位、処理Ｇが１５単位、と仮定している。ここで、例えば１単位が１ＭＢ（メガバイト）であれば、ｎ単位はｎＭＢになる。
【００３０】
図４の例示では、
処理Ａが利用できるバッファメモリ範囲はメモリ５３０の２９番地〜３０番地のみ；
処理Ｂが利用できるバッファメモリ範囲はメモリ５３０の２９番地〜３３番地のみ；
処理Ｃが利用できるバッファメモリ範囲はメモリ５３０の０番地〜２番地または１５番地〜１７番地；
処理Ｄが利用できるバッファメモリ範囲はメモリ５３０の０番地〜６番地または１５番地〜２１番地；
処理Ｅが利用できるバッファメモリ範囲はメモリ５３０の２２番地〜２５番地のみ；
処理Ｆが利用できるバッファメモリ範囲はメモリ５３０の２２番地〜２８番地のみ；
処理Ｇが利用できるバッファメモリ範囲はメモリ５３０の０番地１４番地または７番地〜２１番地
ということが示されている。このようなバッファメモリ割り当ての場合、処理実行に必要なバッファメモリサイズ（静的バッファ領域５３４のサイズ）は、０番地〜３３番地の３４単位分（例えば３４ＭＢ）になる。このような情報が、処理Ａ〜Ｇに対するバッファ割り当て情報ＢＡＩとして作成され、データ格納部５２０に格納される。
【００３１】
図５は、バッファとして利用可能なメモリ領域に利用できない無駄な領域が生じた場合を説明する図である。もし、図１または図２のメモリ割り当て装置５００が用いられないと、図５に例示されるように、メモリ領域（バッファ領域）５３２内に、バッファとして利用できない無駄な領域が生じる恐れがある。図１または図２の装置５００では、以下に述べるような動作によって、このような無駄な領域の発生を防止している。
【００３２】
いま、メモリ割り当て装置５００に相当する構成を持つＰＣまたはＨＤＤレコーダ等の機器において、実行すべき処理名の集合を{A, B, C, D,… }とする。これらの処理名は、頻繁に実行されることが分かっていて、かつ、実行に際して必要なバッファサイズが既知で、かつ、バッファとして連続したメモリ領域を確保したい処理を示す。ここで、各処理が実行に際して必要なバッファサイズはs(N)で与えられているものとする（Nは処理名）。
【００３３】
例えば、３つの処理Ａ（s(A)=3）、B（s(B)=5）、C（s(C)=1）が「Ａ開始→Ｂ開始→Ａ終了(バッファを開放)→Ｃ開始→  …」の順に実行される場合を考えてみる。その場合、単純にバッファの開いている場所に必要な連続領域を詰めて確保する方法を利用すると、図５のように利用できない無駄なメモリ領域が必要となる。バッファ領域を詰め直すことも考えられるが、そうすると、余計な処理時間を要することになる。そこで、この例の場合、処理Ａはメモリの０番地〜２番地、処理Ｂはメモリの３番地〜７番地、処理Ｃはメモリの８番地を常に利用するようにしておけば、無駄なメモリ領域が発生することはない。
【００３４】
しかし、図１または図２の装置５００では、単に無駄なメモリ領域の発生を防止するに止まらず、必要なメモリ量をさらに減らせるようにしている。すなわち、例えば「処理Ａと処理Ｂは同時に実行されない」ということが予め分かっている場合、処理Ａがバッファとして利用するメモリ領域と処理Ｂがバッファとして利用するメモリ領域を共有して、必要なメモリを減らすようにしている。そのために、図１または図２のメモリ割り当て装置５００は、「どのように処理がバッファとして利用するメモリ領域を共有化すれば必要なメモリを最小限に減らすことができるか」という情報（バッファ割り当て情報ＢＡＩ）を出力するように構成されている。
【００３５】
いま、実行されることが分かっていて、かつ、実行に際して必要なバッファサイズが既知で、かつ、バッファとして連続したメモリ領域を確保したい処理名の集合を{A, B, C, D, E, F, G}とし、処理が必要とするバッファサイズをs(A)=2, s(B)=5, s(C)=3, s(D)=3, s(E)=4, s(F)=7, s(G)=15とする。さらに、４つの処理が同時に実行されることはなく、処理ＡとＢ、処理ＥとＦ、処理ＣとＤとＧ、処理ＥとＧとＣ、処理ＥとＧとＤの各組合せは同時に実行されないことが予め分かっている場合を考える。これらの既知情報のうち、処理名の集合の情報、および、処理が必要とするバッファサイズの情報は、処理情報入力部５０１から入力される。また、既知情報のうち、同時に実行されない処理の組合せの情報は、処理間排他関係入力部５０２から入力される。
【００３６】
上記の既知情報が処理情報入力部５０１と処理間排他関係入力部５０２に入力されると、バッファ割り当て情報出力部５１０から図４に例示されるような内容のバッファ割り当て情報ＢＡＩが出力される。このバッファ割り当て情報ＢＡＩから、メモリ割り当て装置５００は、０〜３３番地までのメモリ領域を、処理Ａ〜Ｇを実行するのに必要なバッファ用の静的メモリ領域５３４（処理Ａ〜Ｇ専用のメモリ領域）として利用する。処理Ａ〜Ｇ以外の処理については、動的メモリ領域５３６（図３参照）を利用し、既存の方法（前述した「Ｃ言語におけるmalloc関数で利用されている方法」など）でバッファを確保する。
【００３７】
図６は、メモリ割り当て装置５００がメモリ５３０内の静的メモリ領域５３４にバッファを割り当てる処理の一例を説明するフローチャートである。メモリ割り当て装置５００は、処理間排他関係入力部５０２から入力される排他関係から、実行される可能性のある並列処理の組み合わせを算出し、算出された並列処理の組合せを入力情報格納部５０３に格納する（ＳＴ１）。ここで、処理間排他関係入力部５０２から入力される排他関係とは、複数存在する処理のうち、並列実行されない処理の関係をいう。
【００３８】
入力情報格納部５０３に格納された並列処理の組合せのうち、各処理が必要とするバッファサイズの和が最大となる組合せが、目標メモリサイズ決定部５０４により検出される（ＳＴ２）。検出された必要バッファサイズの和（最大値）は、静的バッファ領域５３４に対する、目標メモリサイズの初期値となる。
【００３９】
なお、図６の処理において「…→ＳＴ８→ＳＴ２」の順でＳＴ２に到達した場合では、ＳＴ２の処理において、目標メモリサイズを、現状（始めは初期値）から最小単位分増加させた値に更新する。静的バッファ領域５３４をＭＢ（メガバイト）単位の粒度で増減させる場合、ここでの最小単位は１ＭＢとなる。
【００４０】
続いて、バッファ割り当て決定部５０９内のバッファ割り当て探索部５０７が、バッファ割り当て情報ＢＡＩを初期化する（ＳＴ３）。この初期化において、各処理がバッファとして確保する可能性のあるメモリ範囲の候補が、全て列挙される。例えば、目標メモリサイズが１１単位（１単位を１ＭＢとすれば１１ＭＢ）で、入力として排他関係のない処理Ａ（必要バッファサイズ７単位）と処理Ｂ（必要バッファサイズ４単位）を仮定すると、初期化時のバッファ割り当て情報ＢＡＩの内容（各処理がバッファとして確保する可能性のあるメモリ範囲の候補）は、図７のようになる（図７の図解は、横軸方向に沿って、バッファサイズの１単位毎に縦割りされている）。
【００４１】
バッファ割り当て情報ＢＡＩが初期化されると、バッファ割り当て決定部５０９内の探索範囲絞り込み部５０８が、バッファ割り当て情報ＢＡＩの枝刈りを行う（ＳＴ４）。ここで、枝刈りとは、複数存在するメモリ範囲の候補のうち、並行処理が不可能となるようなメモリ範囲の候補を削除することをいう。
【００４２】
例えば、図７の初期状態で処理Ａと処理Ｂが並行動作する場合を考える。処理Ａがメモリ範囲候補Ａ２を利用してしまうと処理Ｂはどのメモリ範囲候補（Ｂ１〜Ｂ８）も利用できず並列動作できなくなることから、メモリ範囲候補Ａ２は候補から削除（枝刈り）する。同様に候補を削除していくと、図８のように枝刈りされたバッファ割り当て情報ＢＡＩが得られる（図８では枝刈りにより削除されたメモリ範囲候補が×で示されている）。この例では、２並列動作を考慮した枝刈りが行われたことになる。この枝刈りの結果、処理Ａに対してはメモリ範囲候補Ａ１とＡ５が残り、処理Ｂに対してはメモリ範囲候補Ｂ１とＢ８が残る。
【００４３】
さらに複雑な例として、３並列動作を考慮した枝刈りを説明する。図９のようなバッファ割り当て情報（初期状態）があり、処理Ａと処理Ｂと処理Ｃが並行動作する場合を考える。処理Ａがメモリ範囲候補Ａ２を利用してしまうと、処理Ｂおよび処理Ｃがどのようにメモリ範囲候補を選択しても並行動作できなくなることから、メモリ範囲候補Ａ２は候補から削除（枝刈り）する。同様に、候補を削除していくと、図１０のように枝刈りされたバッファ割り当て情報ＢＡＩが得られる。４並列動作、５並列動作、…などの多並列動作を考慮した枝刈りも同様に行うことができる。
【００４４】
図６の処理の説明に戻る。バッファ割り当て情報の枝刈りが済むと、バッファ割り当て探索部５０７は、各処理について、バッファとして利用するメモリ範囲候補を仮定設定する（ＳＴ５）。この設定において、バッファ割り当て探索部５０７は、利用するメモリ範囲候補を仮定する処理の順番を決定しておく（ここで仮定するメモリ範囲候補の個数は1つ以上ある）。
【００４５】
続いて、バッファ割り当て探索部５０７は、全ての処理についてメモリ範囲候補の仮定を行ったかどうかを判定する（ＳＴ６）。全ての処理についてメモリ範囲候補の仮定が行われていなければ（ＳＴ６ノー）、バッファ割り当て情報の枝刈り（ＳＴ４）とバッファとして利用するメモリ範囲候補の仮定設定（ＳＴ５）を再度行う。
【００４６】
全ての処理についてメモリ範囲候補の仮定が終了したならば（ＳＴ６イエス）、バッファ割り当て決定部５０９内の実行可能／不可能判定部５０６は、「仮定のおかれたメモリ範囲候補をバッファ割り当て情報として選択した場合に、排他関係にない処理組合せであれば、どのような順序で処理が開始されても、処理がバッファとして利用するメモリ範囲を必ず選択できる」かどうかを判定する。例えば、処理Ａと処理Ｂと処理Ｃが並行動作する場合ならば、実行開始順が「Ａ→Ｂ→Ｃ」、「Ａ→Ｃ→Ｂ」、「Ｂ→Ａ→Ｃ」、「Ｂ→Ｃ→Ａ」、「Ｃ→Ａ→Ｂ」、「Ｃ→Ｂ→Ａ」の６パターンのどの場合についても、処理がバッファとして利用するメモリ範囲を必ず選択できるかどうかを判定する（ＳＴ７）。処理がバッファとして利用するメモリ範囲を必ず選択できるならば、その処理は実行可能となる。そうでないなら、その処理は実行不可能とする。
【００４７】
実行不可能と判定された場合は（ＳＴ７ノー）、全ての処理の全てのパターンについてバッファ割り当て探索部５０７が仮定設定をし終えたかを調べる（ＳＴ８）。全ての処理の全てのパターンについて仮定設定が終わっていないならば（ＳＴ８ノー）、ＳＴ４〜ＳＴ７の処理が再度実行される。
【００４８】
全ての処理の全てのパターンについて仮定設定が終わっている場合は（ＳＴ８イエス）、現在の目標メモリサイズでは、実行可能なバッファ割り当て情報が存在しないことになる。その場合は、ＳＴ２に戻り、目標メモリサイズを更新したのち、実行可能なバッファ割り当て情報の探索（ＳＴ３〜ＳＴ７の処理）をやり直す。
【００４９】
ＳＴ７で実行可能と判定された場合は（ＳＴ７イエス）、現在仮定のおかれたメモリ範囲の候補（例えば図８または図１０において、×以外のメモリ範囲が候補になる）をバッファ割り当て情報としたものが、最終的なバッファ割り当て情報ＢＡＩとしてバッファ割り当て情報出力部５１０から出力される（ＳＴ９）。出力されたバッファ割り当て情報ＢＡＩは、データ格納部５２０に格納される（ＳＴ１０）。
【００５０】
ＳＴ９で出力されるバッファ割り当て情報ＢＡＩは、処理を実行するのに必要なバッファをバッファメモリ範囲決定部５２２が必ず選択可能（ＳＴ７で判定済み）な内容となっている。さらに、目標メモリサイズ決定部５０４は、目標メモリサイズを、最小限の最適メモリサイズ以下の値から、最小の単位（例えば１ＭＢ）で徐々に大きくしていく仕組みを持っている（ＳＴ２での更新）。そのため、ＳＴ９で出力されるバッファ割り当て情報ＢＡＩは、静的バッファ領域５３４のサイズを処理の実行が可能な範囲で最小にする内容となる。
【００５１】
こうしてＳＴ９で出力されるバッファ割り当て情報ＢＡＩから、静的バッファ領域５３４として利用するメモリ範囲を決定できる。メモリ割り当て装置５００は、処理情報入力部５０１から入力されなかった処理を実行する際には、静的バッファ領域５３４として利用されない領域（動的バッファ領域５３６）を利用する。一方、処理情報入力部５０１から入力された処理に関しては、バッファ割り当て情報ＢＡＩを利用し、既に実行中の処理が利用していないメモリ範囲をバッファとして確保（必ず確保できることが保証されている）して、処理を実行する。
【００５２】
すなわち、データ格納部５２０に格納されたバッファ割り当て情報ＢＡＩから処理間で重複しないメモリ範囲が選択される（ＳＴ１１）（図８の２並列動作の場合を例にとれば、Ａ１とＡ５とＢ１とＢ８が、処理Ａと処理Ｂの間で重複しないメモリ範囲として選択される）。バッファメモリ範囲決定部５２２は選択されたメモリ範囲をバッファ用としてメモリ５３０上に確保する（ＳＴ１２）。処理実行部５２４は、こうして確保されたバッファメモリ範囲を用いて、１以上の処理を実行する（ＳＴ１３）。
【００５３】
なお、バッファ割り当て探索部５０７が仮定するメモリ範囲候補の個数が１つ以上ある場合において、「…→ＳＴ８→ＳＴ２→ＳＴ３→ＳＴ４→ＳＴ５」の順でＳＴ５に到達する場合を除き、ＳＴ５では同じ処理について一度仮定したメモリ範囲候補の組み合わせをもう一度仮定することはない。しかし、「…→ＳＴ８→ＳＴ２→ＳＴ３→ＳＴ４→ＳＴ５」の順でＳＴ５に到達する場合は、今まで仮定をおいた処理や仮定をおいたメモリ範囲候補の組み合わせに関する情報をクリアし、最初の処理の処理から仮定をおく（ＳＴ５の仮定設定を行う）。
【００５４】
「ＳＴ１→ＳＴ２→ＳＴ３→ＳＴ４→ＳＴ５」または「…→ＳＴ６→ＳＴ４→ＳＴ５」の順でＳＴ５に到達する場合は、ＳＴ５ではまだ仮定をおいていない次の処理について、利用するメモリ範囲候補の仮定を行う。また、「…→ＳＴ８→ＳＴ４→ＳＴ５」の順でＳＴ５に到達する場合は、最後に仮定を行った処理について次の仮定を行う。ただし、最後に仮定を行った処理が既に全てのパターンについて仮定をし終わっていた場合、さらにその前の処理に戻り次の仮定をする。その前の処理についても、既に全てのパターンについて仮定をし終わっていた場合、さらに前といった具合に戻していく（全ての処理について、全ての仮定設定が終了している場合は、「…→ＳＴ８→ＳＴ４→ＳＴ５」の順でＳＴ５に到達することはない）。このようにしてＳＴ５に至る動作は、いわゆる「深さ優先探索」に対応する。
【００５５】
図１１は、バッファ割り当て処理における「深さ優先探索」の一例をグラフィカルイメージで説明する図である。例えば、３つの処理（処理Ａ、Ｂ、Ｃ）に対して図１０に例示したようなメモリ範囲の候補を想定し得る場合において、処理Ｂに関してメモリ範囲候補の仮定をおいてみる（図６ではＳＴ５）。複数ある処理Ｂのメモリ範囲候補を横方向（幅方向）に探索する場合は、いわゆる「幅優先探索」となる。一方、「深さ優先探索」では、複数ある処理Ｂのメモリ範囲候補のうちの１つに対して、処理Ａに関するメモリ範囲の候補に仮定をおく（ＳＴ５）。その際、処理Ｂと同時実行が不可能な処理Ａのメモリ範囲候補に関しては、以後の深さ優先探索が打ち切られる（これにより処理時間の短縮を図れる）。処理Ｂと同時実行が可能な処理Ａのメモリ範囲候補が１つ以上みつかったときは、そのうちの１つに対して、処理Ｃに関するメモリ範囲の候補に仮定をおく（ＳＴ５）。その際、処理Ｂおよび処理Ａと同時実行が可能な処理Ｃのメモリ範囲候補がみつかれば、３つの処理Ａ、Ｂ、Ｃの並列実行が可能な解（メモリ範囲候補の組合せ）が見つかったことになるので、そこで深さ優先探索のアルゴリズムは終了する。
【００５６】
この発明の実施の形態では、高速にバッファ割り当て情報ＢＡＩを出力するため、目標メモリサイズを初期値設定する（図６ＳＴ２）ことの他に、バッファ割り当て探索部５０７の探索範囲を狭める工夫として、上記「深さ優先探索」を行っている。探索方法には「幅優先探索」もあるが、この発明の実施の形態では「深さ優先探索」の方を採用して説明した。
【００５７】
上記の「深さ優先探索」および「幅優先探索」については下記文献参照：
石畑清、岩波講座  ソフトウエア科学３“アルゴリズムとデータ構造”、岩波書店、１９８９
図１２は、バッファ割り当ての探索範囲が絞り込まれる前の、バッファ割り当て情報初期状態を説明する図である。バッファ割り当て探索部５０７の探索範囲は、探索範囲絞り込み部５０８によって絞り込まれる（図６のＳＴ４における枝刈り）。その際、次の考え方を導入して、さらに絞り込みを行うことができる。例えば、処理Ａ（s(A)=7）と処理Ｂ（s(B)=6）と処理Ｃ（s(C)=1）があり、目標メモリサイズが７単位の場合、バッファ割り当て情報の初期状態は図１２のようになる。しかし、解（メモリ範囲候補の組合せ）を探索するにあたり、図１２のＣ２〜Ｃ６のメモリ範囲候補については、条件が同じであるため（他の処理のメモリ範囲候補との重複関係が同じ）、全てを候補としておく必要はなく、どれか１つで十分（これで絞り込み可）となる。
【００５８】
既に作成されているバッファ割り当て情報を更新する場合も、上記の流れに従って新たにバッファ割り当て情報を作成する。新たに静的バッファ領域５３４を利用する処理を追加する場合は、その処理と利用するバッファサイズおよびその処理が関連する排他関係を追加する形で入力情報格納部５０３の内容を更新し、その内容を元に新たなバッファ割り当て情報を作成する。逆に静的バッファ領域５３４を利用する処理を減らす場合には、入力情報格納部５０３に格納されている情報から、削除する処理に関連する情報を削除し、その内容を元に新たなバッファ割り当て情報を作成する。
【００５９】
ところで、図１または図２のメモリ割り当て装置５００で実行される図６の処理において、ＳＴ２における目標メモリサイズの初期値は、「排他関係にない処理組合せなら実行可能なバッファ割り当て情報が必要とする最小のメモリサイズ（最適メモリサイズ）」以下の値としている。ここで、目標メモリサイズの初期値は０でもバッファ割り当て情報を得ることができるが、最適メモリサイズと目標メモリサイズの初期値が離れ過ぎていると、処理の並列実行が可能な解（メモリ範囲候補の組合せ）の探索に時間がかかる（図６のＳＴ２〜ＳＴ８の処理ループの反復回数が増えて時間がかかる）ことになる。そこで、図６の説明では、例えば、処理Ａと処理Ｂと処理Ｃが並行動作するなら、少なくともs(A)＋s(B)＋s(C)以上のメモリサイズが必要となることを、目標メモリサイズの初期値の設定時（ＳＴ２）に利用している。
【００６０】
さらに、図２のメモリ割り当て装置５００では、最適メモリサイズと目標メモリサイズの初期値を近づけるため、部分問題作成部５０５において部分問題を作成し、その部分問題が必要とするメモリサイズを目標メモリサイズの初期値とする仕組みを導入している。具体的には、例えば６個以上の処理が処理情報入力部５０１に入力された場合、そのうち、処理の実行に必要なバッファサイズが大きい順（または排他関係が多い順）に５つの処理を選択し、その５つの処理が入力となっていると想定した場合のバッファ割り当て情報を計算する。その時、必要となる静的バッファ領域のサイズを目標メモリサイズの初期値（図６のＳＴ２）として、元の入力に対するバッファ割り当て情報を計算する。
【００６１】
図１３は、図２の部分問題作成部５０５における処理の一例を説明するフローチャートである。まず、部分問題作成部５０５が扱う処理の種類がｎ＋１以上あるかどうかチェックされる（ＳＴ２０）。ここで、例えば６個以上の処理（元の問題）が処理情報入力部５０１に入力され、ｎが５であるとする。その場合ｎ＋１は６となり（ＳＴ２０イエス）、必要バッファサイズの多い順、もしくは、排他関係の多い順に、処理がｎ個（５個）選択される（ＳＴ２１）。そして、選択したｎ個の処理、および、選択したｎ個の処理間の排他関係のみを残した問題を、部分問題として作成し（ＳＴ２２）、図６の処理を行う。
【００６２】
ここで、ＳＴ２２において部分問題を作成する理由は、元の問題の目標メモリサイズ（初期値）を、最終的に得る「要求合致のバッファ割り当て情報が必要とする（必要最小限の）メモリサイズ」に近づけるためである。具体的には、部分問題作成部５０５の作成した部分問題に対する「要求合致バッファ割り当て情報」を計算し、その「要求合致バッファ割り当て情報」で必要なメモリサイズを、元の問題での目標メモリサイズの初期値とする。
【００６３】
このように、「部分問題の要求合致バッファ割り当て情報の必要メモリサイズを、元の問題の目標メモリサイズの初期値とする」ことが、部分問題作成部５０５を有する図２の構成の特徴となる。
【００６４】
部分問題作成部５０５が扱う処理の種類がｎ＋１以上でない、つまりその種類がｎ以下であるときは（ＳＴ２０ノー）、部分問題を作成せず（ＳＴ２３）、図６の処理を行う。
【００６５】
なお、ＳＴ２１において「必要バッファサイズの多い順、もしくは、排他関係の多い順に」ｎ個選択するのは、部分問題が必要とするメモリサイズ（ｎ個の処理を扱えるバッファサイズ）を元の問題の最適メモリサイズ（ｎ＋１個の処理を扱えるバッファサイズ）に近づけるためである。
【００６６】
また、元の問題の処理の種類数がかなり多い場合（ＳＴ２０におけるｎ＋１がかなり多い場合）、例えばある部分問題１の目標サイズの初期値を、その部分問題１から作成される部分問題２から決定することもできる（この例では部分問題１の扱う処理数＞部分問題２が扱う処理数となる）。すなわち、部分問題を多段に作成することもできる。
【００６７】
図１４は、図１または図２のメモリ割り当て装置の応用例を説明する図である。ここでは、バッファを用いた並列処理の具体例として、複数のデジタル放送ストリームの処理を例にとって説明する。図１４の例では、ＴＶ放送サービスの１つとして放送局から送られてくる電子番組表情報（ＥＰＧ情報）、インターネット配信される電子番組表情報（ｉＥＰＧ情報）、ユーザがリモコン操作などで入力する番組予約情報などの処理情報ソース６０１が、ホスト６００に接続されている。このホスト６００には、映像表示を行う表示部６０４も接続されている。
【００６８】
ホスト６００としては、ＰＣ（ＴＶチューナ付きのＡＶパソコン）、デジタルＴＶ、ＨＤＤ付きビデオレコーダなどを用いることができる。このホスト６００に、図１または図２のメモリ割り当て装置５００およびバッファとして利用するリードライトメモリ５３０が装備される。処理情報ソース６０１は、図１または図２の処理情報入力部５０１および処理間排他関係入力部５０２に対応する。処理情報ソース６０１から得た情報は、図１または図２の入力情報格納部５０３に対応する記憶エリア（図示せず）に格納される。
【００６９】
メモリ割り当て装置５００は、ホスト６００から出力される複数のデジタル放送ストリームに対する処理を、複数の処理として扱う（これらの複数処理は、１つの放送番組中に含まれる映像ストリーム、音声ストリーム、その他のデータストリーム等に対する処理でもよい）。そして、これらの複数処理の排他関係に基づいてバッファ割り当て情報ＢＡＩが作成され、作成されたＢＡＩに基づいて、メモリ５３０上の静的バッファ領域に対するメモリ範囲の割り当てが行われる（図８、図１０等参照）。
【００７０】
図６等を参照して説明した処理により、必要最小限の静的バッファ領域サイズでバッファリングが可能となっているメモリ５３０を介して、ホスト６００から出力される複数ストリームがＨＤＤなどのデータ記憶装置１００ａで記録される。あるいは、データ記憶装置１００ａから読み出された複数ストリームは、メモリ５３０を介してホスト６００に返される。ホスト６００は、例えば、読み出されたストリームに含まれる映像を表示部６０４で表示し、読み出されたストリームに含まれる音声を図示しないスピーカを用いて再生する。
【００７１】
図１４の装置は、ＵＳＢインターフェース（Ｉ／Ｆ）１１０およびネットワークインターフェース（Ｉ／Ｆ）１１０ａをさらに備えている。メモリ５３０でバッファリングされる１以上のデータストリームは、ＵＳＢＩ／Ｆ１１０およびＵＳＢハブ１１２を介して１以上の外付けデータ記憶装置１００ｂ〜１００ｄに転送される。あるいは、外付けデータ記憶装置１００ｂ〜１００ｄから読み出された１以上のデータストリームは、ＵＳＢハブ１１２およびＵＳＢＩ／Ｆ１１０を通し、メモリ５３０を介してホスト６００に返される。
【００７２】
同様に、メモリ５３０でバッファリングされる１以上のデータストリームは、ネットワークＩ／Ｆ１１０ａを介して外付けデータ記憶装置１００ｅに転送される。あるいは、外付けデータ記憶装置１００ｅから読み出された１以上のデータストリームは、ネットワークＩ／Ｆ１１０ａを通し、メモリ５３０を介してホスト６００に返される。
【００７３】
ここで、ネットワークＩ／Ｆ１１０ａには、ＩＥＥＥ８０２．３あるいはＤＬＮＡ（Digital Living Network Alliance）に準拠したＩ／Ｆを用いることができる。
【００７４】
図１４の構成では、外部機器（１００ｂ〜１００ｅ）から見れば、メモリ割り当て装置５００は機器外部に存在することになる。それでも、データ転送を仲介するＩ／Ｆが必要な速度に対応しておれば、機器内臓のデータ記憶装置１００ａを用いる場合と同様に、外部機器（１００ｂ〜１００ｅ）において、メモリ５３０をバッファとして用いた処理が可能となる。
【００７５】
一般論として、ＰＣにおける処理のように、ユーザ毎に実行する処理が異なる場合は、バッファ割り当て情報出力装置５１０を具備したメモリ割り当て装置５００を内蔵してメモリ割り当てを行うのが便利である。一方、ＨＤＤビデオレコーダのように、実行する処理が確定されている機器の場合や、頻繁にバッファ割り当て情報を更新する必要がない機器の場合は、機器（外付けＨＤＤレコーダなど）の外部に存在するバッファ割り当て情報出力装置５１０の出力するバッファ割り当て情報ＢＡＩをバッファメモリ範囲決定部５２２に入力し利用する方が便利である。
【００７６】
図１５は、図１または図２のメモリ割り当て装置を具備したデジタルビデオレコーダの構成の一例を説明する図である。このビデオレコーダは複数のＴＶチューナ（８２、８９）をもち、複数のＴＶ放送番組の同時録画（Ｗ録など）が可能な構成となっている。このビデオレコーダは、図１または図２のメモリ割り当て装置５００を持ち、この装置５００によって、一時記憶部５３０内に静的バッファ領域を適宜確保している。もし、メインＭＰＵ８０の処理能力に余裕があるときは、メモリ割り当て装置５００の処理（図６の処理など）を、ＭＰＵ８０のファームウエアでこなしてもよい
＜実施の形態のまとめ＞
ストリーム処理のように高速な処理実行が必須であることなどから、バッファとして連続メモリ領域の確保が必要な場合に、この発明が実施される。その際、既知の処理がバッファとして利用するメモリ領域（静的バッファ領域）と、その他の処理がバッファとして利用するメモリ領域（動的バッファ領域）に、本来バッファとして利用可能だったメモリ領域を分離する。静的バッファ領域を利用する各処理に関するバッファ領域の確保は、各処理がバッファとして利用可能なメモリ範囲を表わすバッファ割り当て情報ＢＡＩに従って行う。動的バッファ領域の利用方法に関しては既存の方法を利用できる。すなわち、従来の処理実行も同様に行える。
【００７７】
バッファ割り当て情報ＢＡＩとは、静的バッファ領域を利用する処理毎に処理がバッファとして利用可能なメモリ範囲の候補（１つ以上）を表わす情報である。メモリ割り当て装置は、静的バッファ領域を利用する処理に関しては、既に利用されているメモリ範囲と重複しないメモリ範囲を候補の中から１つ選択し、そのメモリ範囲をバッファとして割り当てる。処理の実行装置は、そのバッファを利用し処理を開始する。バッファ割り当て情報ＢＡＩは、次に述べる特長をもつバッファ割り当て情報出力部５１０から得る。
【００７８】
バッファ割り当て出力部５１０は、静的バッファ領域を利用する処理、各処理が利用するバッファサイズ、および、それら処理間の排他関係を入力として用いる。排他関係にない処理の組合せであれば、どのような順序で処理が開始されても、処理がバッファとして利用するメモリ範囲を必ず選択でき（処理が実行可能）、かつ、静的バッファ領域のサイズが最小となるような、バッファ割り当て情報ＢＡＩを出力する。
【００７９】
＜実施の形態の効果＞
新たに静的バッファ領域を利用する処理が発生した場合や、これまで静的バッファ領域を利用していた処理が不要になった場合は、新たに発生した処理に関する情報や、不要になった処理に関する情報を入力することにより、バッファ割り当て情報を更新することができる（図６の処理）。
【００８０】
この発明を利用すれば、バッファとして連続領域が必要で、かつ、処理が利用するバッファサイズが既知の処理に関しては、静的バッファ領域上に連続するメモリ領域としてバッファを必ず確保できるようになる。そのため、高速な処理実行が可能になる。
【００８１】
また、動的にバッファを確保せざるを得ない処理（もしくは、静的バッファ領域にバッファを確保する必要のない処理）に関しては、従来通り動的バッファ領域上にバッファを確保できる。その上、バッファ割り当て情報出力部５１０の出力するバッファ割り当て情報ＢＡＩは静的バッファ領域のサイズを最小にすることが保証されているため、動的バッファ領域を最大限確保できる。
【００８２】
＜実施の形態と発明との対応例＞
（１）バッファとして用いる連続領域をメモリ（５３０）上に確保する必要のある１以上の処理を処理名の集合（｛Ａ，Ｂ，Ｃ，…｝）で表し、それらの処理が利用するバッファのサイズをバッファサイズ情報（s(N)）で表し、それら処理間で並列実行されない処理の組合せを排他関係で表し、前記処理がバッファとして利用可能な１つ以上のメモリ範囲候補をバッファ割り当て情報（ＢＡＩ）で表すときに、前記処理名の集合（｛Ａ，Ｂ，Ｃ，…｝）、前記バッファサイズ情報（s(N)）、および前記排他関係に基づいて、前記バッファ割り当て情報（ＢＡＩ）を前記処理毎に出力する（ＳＴ１〜ＳＴ８）。
【００８３】
ここで、利用するバッファサイズが既知である処理に対して割り当てられるバッファ領域を静的バッファ領域とし、この静的バッファ領域以外のバッファ領域を動的バッファ領域とするときに、前記バッファとして利用可能な前記メモリの領域（５３２）が前記静的バッファ領域（５３４）と前記動的バッファ領域（５３６）に分割される。
【００８４】
前記処理名の集合（｛Ａ，Ｂ，Ｃ，…｝）に含まれる特定の処理を開始する際には、前記バッファ割り当て情報（ＢＡＩ）に記述されているメモリ範囲候補（５２０に格納されている）のうち、前記特定の処理を開始する時点で他の処理に利用されているメモリ範囲と重複しないメモリ範囲を選択し（ＳＴ１１）、選択された前記メモリ範囲を前記静的バッファ領域（５３４）として前記メモリ（５３０）に確保し（ＳＴ１２）、確保された前記静的バッファ領域（５３４）を用いて前記特定の処理を実行する（ＳＴ１３）。
【００８５】
（２）利用するバッファサイズが既知である処理に対して割り当てられるバッファ領域を静的バッファ領域とし、この静的バッファ領域以外のバッファ領域を動的バッファ領域とするときに、前記バッファとして利用可能な前記メモリの領域（５３２）は前記静的バッファ領域（５３４）と前記動的バッファ領域（５３６）に分割され、前記バッファメモリ範囲決定モジュール（５２２）により選択された前記メモリ範囲が、前記静的バッファ領域（５３４）に対して適用される。
【００８６】
（３）新たにバッファとして連続領域を前記メモリ（５３０）上に確保する必要のある第１の処理の名前、および、その第１の処理が利用するバッファのサイズ（s(N)）を入力する処理情報入力モジュール（５０１）と、前記第１の処理と既に前記バッファ割り当て情報（ＢＡＩ）に含まれている処理との間の排他関係を入力する処理間排他関係入力モジュール（５０２）を、さらに具備できる。
【００８７】
（４）バッファとして連続領域を前記メモリ（５３０）上に確保する必要のなくなった第２の処理の名前を入力する処理情報入力モジュール（５０１）をさらに具備し、前記バッファ割り当て情報出力モジュール（５１１）が、前記第２の処理以外の処理の集合と、前記第２の処理に関連する排他関係を現在利用している排他関係から削除した新たな排他関係に基づいて、前記バッファ割り当て情報（ＢＡＩ）を出力するように構成できる。
【００８８】
（５）前記バッファ割り当て情報（ＢＡＩ）を格納する格納モジュール（５２０）をさらに具備し、前記バッファメモリ範囲決定モジュール（５２２）が、前記格納モジュール（５２０）に格納された前記バッファ割り当て情報（ＢＡＩ）を用いて前記メモリ範囲を選択するように構成できる。
【００８９】
（６）前記バッファとして利用される可能性のある前記メモリの領域について、その領域のサイズの目標値を目標メモリサイズとするときに、この目標メモリサイズを決定する目標メモリサイズ決定モジュール（５０４）をさらに備えることができる。そして、並行動作する可能性のある処理組合せの各処理が利用するバッファメモリサイズの和の最大値を前記目標メモリサイズの初期値とし、前記排他関係にない処理の組合せであればどのような順序で処理が開始されても必ず処理が利用するバッファを選択できるようなバッファ割り当て情報を要求合致バッファ割り当て情報とするときに、前記目標メモリサイズの初期値では前記要求合致バッファ割り当て情報が前記バッファ割り当て情報（ＢＡＩ）に存在しない場合に、前記目標メモリサイズをその初期値から増加させるように、前記目標メモリサイズ決定モジュール（５０４）を構成できる。
【００９０】
（７）前記バッファとして利用される可能性のある前記メモリの領域について、その領域のサイズの目標値を目標メモリサイズとするときに、この目標メモリサイズを決定する目標メモリサイズ決定モジュール（５０４）と、前記目標メモリサイズをどのように決定するかに関する元の問題から部分問題を作成する部分問題作成モジュール（５０５）をさらに備えることができる。そして、前記排他関係にない処理の組合せであればどのような順序で処理が開始されても必ず処理が利用するバッファを選択できるようなバッファ割り当て情報を要求合致バッファ割り当て情報とするときに、前記部分問題の要求合致バッファ割り当て情報の必要メモリサイズを、前記元の問題の目標メモリサイズの初期値とする（ＳＴ３）ように、前記目標メモリサイズ決定モジュール（５０４）を構成できる。
【００９１】
（８）前記処理名の集合（｛Ａ，Ｂ，Ｃ，…｝）の情報、および、この処理名の集合が示す１以上の処理で利用される前記バッファのサイズ情報（s(N)）を入力する処理情報入力モジュール（５０１）と、前記排他関係の情報を入力する排他関係情報入力モジュール（５０２）と、前記バッファとして利用される可能性のあるメモリ領域のサイズの目標値を目標メモリサイズとするときに、この目標メモリサイズを設定する目標メモリサイズ決定モジュール（５０４）と、前記目標メモリサイズ決定モジュール（５０４）により設定された前記目標メモリサイズ内で前記処理が実行可能なメモリ割り当てを探索するバッファ割り当て探索モジュール（５０７）と、前記処理情報入力モジュール（５０１）および前記排他関係情報入力モジュール（５０２）により入力された情報（５０３に格納された情報）を用いて、前記バッファ割り当て探索モジュール（５０７）による探索範囲を絞り込む探索範囲絞り込みモジュール（５０８）と、前記バッファ割り当て探索モジュール（５０７）による探索で得られた前記バッファ割り当て情報（ＢＡＩ）で、前記排他関係にない処理が実行可能かどうかを判定する実行可能／不可能判定モジュール（５０６）を備えることができる。
【００９２】
ここで、前記バッファメモリ範囲決定モジュール（５２２）は、前記排他関係にない処理組合せであればどのような順序で処理が開始されても処理が利用する前記バッファを選択するように構成される（その結果５２４が処理を実行可能になる）。そして、前記バッファ割り当て情報出力モジュール（５１１）は、前記静的バッファ領域（５３４）のサイズが最小になるような前記バッファ割り当て情報（ＢＡＩ）を出力するように構成される。
【００９３】
（９）映像情報のデータストリームを処理する際にバッファとして用いる連続領域を含むメモリ（図１４、図１５の５３０）と、前記メモリでバッファリングされた前記データストリームを記録再生するデータ記憶装置（図１４、図１５の１００ａ〜１００ｅ）と、前記メモリ上に前記バッファとして用いる連続領域を割り当てるメモリ割り当て装置（図１４の５００、図１５の５００または５００ａ）を備えた映像機器（ＨＤＤレコーダ付きＴＶ、ＤＶＤ／ＢＤレコーダ、ノートパソコンなど）において、前記バッファとして用いる連続領域を前記メモリ（５３０）上に確保する必要のある１以上の処理を処理名の集合（｛Ａ，Ｂ，Ｃ，…｝）で表し、それら処理間で並列実行されない処理の組合せを排他関係で表し、前記処理がバッファとして利用可能な１つ以上のメモリ範囲候補をバッファ割り当て情報（ＢＡＩ）で表す。
【００９４】
この場合、前記メモリ割り当て装置（５００）が、前記処理名の集合（｛Ａ，Ｂ，Ｃ，…｝）および前記排他関係に基づいて、前記バッファ割り当て情報（ＢＡＩ）を前記処理毎に出力するバッファ割り当て情報出力モジュール（５１１）と、前記処理名の集合（｛Ａ，Ｂ，Ｃ，…｝）に含まれる特定の処理を開始する際には、前記バッファ割り当て情報（ＢＡＩ）に記述されているメモリ範囲候補（５２０に格納されている）のうち、前記特定の処理を開始する時点で他の処理に利用されているメモリ範囲と重複しないメモリ範囲を選択するバッファメモリ範囲決定モジュール（５２２）と、選択された前記メモリ範囲を前記バッファとして前記メモリ（５３０）に確保し、確保されたバッファを用いて前記特定の処理を実行する処理モジュール（５２４）を含んで構成される。
【００９５】
なお、この発明は前述した実施の形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、各実施形態は可能な限り適宜組み合わせて実施してもよく、その場合組み合わせた効果が得られる。更に、上記実施形態には種々の段階の発明が含まれており、開示される複数の構成要件における適当な組み合わせにより種々の発明が抽出され得る。例えば、実施形態に示される全構成要件からいくつかの構成要件が削除されても、発明が解決しようとする課題の欄で述べた課題が解決でき、発明の効果の欄で述べられている効果が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。
【符号の説明】
【００９６】
５００…メモリ割り当て装置、５０１…処理情報入力部、５０２…処理間排他関係入力部、５０３…入力情報格納部、５０４…目標メモリサイズ決定部、５０５…部分問題作成部、５０６…実行可能／不可能判定部、５０７…バッファ割り当て探索部、５０８…探索範囲絞り込み部、５０９…バッファ割り当て決定部、５１０…バッファ割り当て情報出力部、５１１…バッファ割り当て情報出力装置、５２０…データ格納部（バッファ割り当て情報格納部）、５２２…バッファメモリ範囲決定部、５２４…処理実行部（ＣＰＵまたはＭＰＵ）、５３０…バッファ領域を含むメモリ（バッファとして利用するメモリ）。
【図１】
2011034510.tif 000003
【図２】
2011034510.tif 000004
【図３】
2011034510.tif 000005
【図４】
2011034510.tif 000006
【図５】
2011034510.tif 000007
【図６】
2011034510.tif 000008
【図７】
2011034510.tif 000009
【図８】
2011034510.tif 000010
【図９】
2011034510.tif 000011
【図１０】
2011034510.tif 000012
【図１１】
2011034510.tif 000013
【図１２】
2011034510.tif 000014
【図１３】
2011034510.tif 000015
【図１４】
2011034510.tif 000016
【図１５】
2011034510.tif 000017