(57)【要約】【課題】  メモリ内に不連続に存在する各配置可能領域に、複数のオブジェクトを、配置禁止領域に重なることなく配置できるような配置指示情報を生成する。【解決手段】  リンカーが生成したマップ情報から、メモリに配置しようとする各オブジェクトのサイズとアドレスとを取得し、前記オブジェクトを再配置するための領域であって予め定義された配置可能領域のアドレスとサイズとを取得し、前記リンカーが前記マップ情報を生成するために参照する配置指示情報に基づいて、各オブジェクトの各配置可能領域に対する配置優先度を設定し、前記配置可能領域に配置しようとする前記オブジェクトの累計サイズが前記配置可能領域のサイズより大きい場合、前記配置優先度に基づいて当該配置可能領域に配置可能なオブジェクトであってその累計サイズが当該配置可能領域のサイズを超えないような前記オブジェクトの組み合わせを決定し、前記組み合わせに含まれる前記オブジェクトを前記配置可能領域に配置する指示となるように前記配置指示情報を更新する。【選択図】図１
2010218201.tif 000002
【特許請求の範囲】
【請求項１】
リンカーが生成したマップ情報から、メモリに配置しようとする各オブジェクトのサイズとアドレスとを取得するマッピング情報取得機能と、
前記オブジェクトを再配置するための領域であって予め定義された配置可能領域のアドレスとサイズとを取得する配置可能領域情報取得機能と
前記リンカーが前記マップ情報を生成するために参照する配置指示情報に基づいて、各オブジェクトの各配置可能領域に対する配置優先度を設定する配置優先度設定機能と、
前記配置可能領域に配置しようとする前記オブジェクトの累計サイズが前記配置可能領域のサイズより大きい場合、前記配置優先度に基づいて当該配置可能領域に配置可能なオブジェクトであってその累計サイズが当該配置可能領域のサイズを超えないような前記オブジェクトの組み合わせを決定する組み合わせ決定機能と、
前記組み合わせに含まれる前記オブジェクトを前記配置可能領域に配置する指示となるように前記配置指示情報を更新する配置指示情報更新機能と、
をコンピューターに実現させる配置指示情報更新プログラム。
【請求項２】
前記組み合わせ決定機能は、前記各オブジェクトの前記各配置可能領域に対する前記配置優先度の高低を品物の価値とし、前記オブジェクトのサイズを前記品物の大きさとし、前記配置可能領域のサイズをナップザックの大きさとして、ナップザック問題を解くことにより、前記配置可能領域に再配置するオブジェクトの組み合わせを決定する、
請求項１に記載の配置指示情報更新プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイラーが生成したオブジェクトをリンカーが結合する際に、リンカーが参照する、オブジェクトの配置指示情報を更新するプログラムに関する。
【背景技術】
【０００２】
従来、プログラムをコンパイルして生成したオブジェクトを、性質が互いに異なる複数のメモリに配置する際に、プログラムの実行頻度に応じて最適なメモリに配置する技術が知られている（特許文献１）。性質が異なる例として、メモリ種別（ＲＯＭ／ＲＡＭ）が異なること、読み書き速度が異なること、消費電力が異なることなどが挙げられている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００３−３３０７３０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
静的ライブラリやコンパイル済みのオブジェクトを、リンカーによってメモリ内の予め決められた領域に配置させるために、配置指示情報をリンク処理前に準備しておく必要がある。配置指示情報は、メモリ内のどの領域にどのオブジェクトを配置しようとするかを指定したものである。リンカーはこの配置指示情報を参照してリンク処理を実行する。リンク処理が実行されると、リンカーは、オブジェクトを配置するアドレスと、オブジェクトのサイズとが、オブジェクトごとに示されたマップ情報を生成する。しかし、もし、この配置指示情報の記述に誤りがあると、リンカーは静的ライブラリやコンパイル済みオブジェクトを配置指示情報の記載通りに配置することができないため、リンカーはリンクエラーを発生し、マップ情報のみを生成して終了する。マップ情報を解析すると、例えばある領域に配置しようとするオブジェクトの累計サイズがその領域を超えていることなどがわかる。このようなリンクエラーが発生した場合には、配置指示情報の誤りを正して配置指示情報を更新し、更新された配置指示情報をリンカーに参照させてリンク処理を実行させる必要がある。
【０００５】
本発明では、メモリ内にオブジェクトの配置禁止領域が存在し、オブジェクトの配置可能領域はメモリ内に連続領域として存在せず当該配置禁止領域により複数に分断されていることを想定している。このような場合に、メモリ内に不連続に存在する各配置可能領域に、複数のオブジェクトを、配置禁止領域に重なることなく配置できるような配置指示情報を生成することを目的の１つとする。
【課題を解決するための手段】
【０００６】
（１）上記目的を達成するための配置指示情報更新プログラムは、リンカーが生成したマップ情報から、メモリに配置しようとする各オブジェクトのサイズとアドレスとを取得するマッピング情報取得機能と、オブジェクトを再配置するための領域であって予め定義された配置可能領域のアドレスとサイズとを取得する配置可能領域情報取得機能と、前記リンカーが前記マップ情報を生成するために参照する配置指示情報に基づいて、各オブジェクトの各配置可能領域に対する配置優先度を設定する配置優先度設定機能と、前記配置可能領域に配置しようとする前記オブジェクトの累計サイズが前記配置可能領域のサイズより大きい場合、前記配置優先度に基づいて当該配置可能領域に配置可能なオブジェクトであってその累計サイズが当該配置可能領域のサイズを超えないような前記オブジェクトの組み合わせを決定する組み合わせ決定機能と、前記組み合わせに含まれる前記オブジェクトを前記配置可能領域に配置する指示となるように前記配置指示情報を更新する配置指示情報更新機能と、を備えている。
【０００７】
本発明によると、各配置可能領域に、当該領域のサイズを超えない範囲で、当該領域に配置可能なオブジェクトを配置する指示を含んだ配置指示情報に更新することができる。その結果、更新された配置指示情報を用いれば、リンクエラーを発生させずに、リンク処理を実行させることができる。すなわち、配置禁止領域（メモリ内の配置可能領域以外の領域）に重なることなく、配置可能領域に、当該領域に対して配置することが可能なオブジェクトを、当該領域のサイズを超えない範囲で配置させることができる。
【０００８】
（２）上記目的を達成するための配置指示情報更新プログラムにおいて、前記組み合わせ決定機能は、前記各オブジェクトの前記各配置可能領域に対する前記配置優先度の高低を品物の価値とし、前記オブジェクトのサイズを前記品物の大きさとし、前記配置可能領域のサイズをナップザックの大きさとして、ナップザック問題を解くことにより、前記配置可能領域に再配置するオブジェクトの組み合わせを決定する機能であってもよい。
本発明によると、少ない計算コストで最適な組み合わせを決定することができる。すなわち、総当たり的に組み合わせを調べる場合、組み合わせ調査回数はＯ（２Ｎ）であるのに対し、ナップザック問題を周知の動的計算法アルゴリズムを用いて解くと、組み合わせ調査回数はＯ（ＮＷ）である。
【０００９】
さらに、本発明のように、リンカーが生成したマップ情報から、メモリに配置しようとする各オブジェクトのサイズとアドレスとを取得し、オブジェクトを再配置するための領域であって予め定義されている配置可能領域のアドレスとサイズとを取得し、前記リンカーが前記マップ情報を生成するために参照する配置指示情報に基づいて、各オブジェクトの各配置可能領域に対する配置優先度を設定し、前記配置可能領域に配置しようとする前記オブジェクトの累計サイズが前記配置可能領域のサイズより大きい場合、前記配置優先度に基づいて当該配置可能領域に配置可能なオブジェクトであってその累計サイズが当該配置可能領域のサイズを超えないような前記オブジェクトの組み合わせを決定し、前記組み合わせに含まれる前記オブジェクトを前記配置可能領域に配置する指示を含んで前記配置指示情報を更新する手法は、この手法を実施する装置や方法の発明として適用可能である。また、以上のような手法を実施する装置は、単独の装置によって実現される場合もあれば、複数の装置を組み合わせることによって実現される場合もあり、各種の態様を含むものである。また、一部がソフトウェアであり一部がハードウェアであったりするなど、適宜、変更可能である。さらに、このソフトウェアプログラムを記録する記録媒体としても発明は成立する。むろん、その記録媒体は、磁気記録媒体であってもよいし光磁気記録媒体であってもよいし、今後開発されるいかなる記録媒体においても全く同様に考えることができる。
【図面の簡単な説明】
【００１０】
【図１】配置指示情報更新プログラムのブロック図。
【図２】（２Ａ）はエラーが発生しない場合のscatファイルの例を示す図、（２Ｂ）はその場合のマップファイルの例を示す図、（２Ｃ）はその場合のメモリを示す図。
【図３】（３Ａ）はエラーが発生する場合のscatファイルの例を示す図、（３Ｂ）はその場合のマップファイルの例を示す図、（３Ｃ）はその場合のメモリを示す図。
【図４】配置指示情報更新処理を示すフローチャート。
【図５】現状配置情報取得処理を示すフローチャート。
【図６】配置優先度設定処理を示すフローチャート。
【図７】組み合わせ決定処理を示すフローチャート。
【図８】未決定オブジェクトの配置領域決定処理を示すフローチャート。
【図９】（９Ａ）は領域情報構造体を示す図、（９Ｂ）〜（９Ｄ）はオブジェクト情報構造体を示す図。
【図１０】（１０Ａ）は属性テーブルを示す図、（１０Ｂ）〜（１０Ｄ）はオブジェクト情報構造体を示す図。
【図１１】新たに出力されるscatファイルの例を示す図。
【発明を実施するための形態】
【００１１】
ここでは、下記の順序に従って本発明の実施の形態について説明する。
（１）配置指示情報更新プログラムの概要と構成：
（２）配置指示情報更新処理：
（２−１）変数初期化：
（２−２）現状配置情報取得処理：
（２−３）配置優先度設定処理：
（２−４）組み合わせ決定処理：
（２−５）scatファイル出力：
（３）他の実施形態：
【００１２】
（１）配置指示情報更新プログラムの概要と構成：
図１は、本発明にかかる配置指示情報更新プログラム２３の構成を示すブロック図である。コンピューター１０は、ＲＡＭ，ＲＯＭ，ＣＰＵ等を備える制御部２０とＨＤＤ３０を備えており、ＲＯＭまたはＨＤＤ３０に記録された様々なプログラムを制御部２０で実行することができる。本実施形態においては、コンパイルプログラム（以降、コンパイラーという）２１と、リンクプログラム（以降、リンカーという）２２と、配置指示情報更新プログラム２３を実行することができる。
【００１３】
コンパイラー２１は、ユーザーが作成したソースコードをコンパイルしてオブジェクトコードを生成し、オブジェクトコードを含んだオブジェクトファイル３０ａを生成する機能を有している。リンカー２２は、生成された複数のオブジェクトファイル３０ａ（以下、単にオブジェクトという）をメモリの所定の領域に配置するリンク処理機能を有している。リンカー２２は、このリンク処理を実行する際、scatファイル３０ｂと呼ばれる、各オブジェクトの配置の仕方を指定する配置指示情報が含まれたファイルを参照する。scatファイル３０ｂにおいては、オブジェクトを配置可能なメモリ内の領域（配置可能領域）が先頭アドレスとサイズによって表されており、各配置可能領域に配置しようとするオブジェクトが指定されている。図２Ａはscatファイルの記述例を示している。図２Ａのscatファイルでは、0x40000000番地から0x6000000バイト分の領域にa.oとb.oとc.oの３つのオブジェクトを配置し、0x47000000番地から0x2000000バイト分の領域にオブジェクトd.oを配置することを指定している。
【００１４】
リンカー２２は、scatファイル３０ｂを参照してリンク処理を実行する過程で、マップファイル３０ｃを生成する。マップファイル３０ｃには、リンク処理の対象となるオブジェクトのオブジェクト名と、当該オブジェクトのサイズ・配置アドレス・属性との対応が記述されている。オブジェクトの属性は、プログラム（ＴＥＸＴ）、初期値付き変数（ＤＡＴＡ）、初期値なし変数（ＢＳＳ）などが該当する。図２Ｂはマップファイル３０ｃの一例を示している。
【００１５】
scatファイルが誤りなく記述されていれば、リンカー２２はそのscatファイルの配置指示情報に基づいてオブジェクトをメモリに配置するとともに、マップファイル３０ｃを生成することができる。「誤りなく」というのは、配置しようとする領域に対して配置しようとするオブジェクトの累計サイズが超過しないように配置指示情報が記述されていることを意味する。具体例を、図２Ａ・２Ｂを用いて説明する。
【００１６】
0x40000000番地から0x6000000バイト分の領域を以降では領域Ａと呼び、0x46000000番地から0x1000000バイト分の領域を領域Ｂ、0x47000000番地から0x2000000バイト分の領域を領域Ｃと呼ぶことにする。この例で用いる４つのオブジェクトa.o、b.o、c.o、d.oを配置可能な領域（配置可能領域）は領域Ａと領域Ｃであり、領域Ｂはこれらのオブジェクトの配置禁止領域であるとする。図２Ｂのマップファイルを参照すると、a.o、b.o、c.o、d.oの各オブジェクトのサイズは順に0x2000000,0x2000000,0x2000000,0x1000000バイトであることがわかる。したがって領域Ａに配置しようとするオブジェクトa.oとb.oとc.oの累計サイズが領域Ａのサイズを超えず、かつ、領域Ｃに配置しようとするオブジェクトd.oの累計サイズも領域Ｃのサイズを超えないため、リンクエラーは発生せず、図２Ａに示された配置指示通りにオブジェクトが配置される（図２Ｃ参照）。
【００１７】
しかし、scatファイル３０ｂに誤りがある場合、リンクエラーとなりリンカー２２はメモリ上の所定の位置にオブジェクトを配置せず、マップファイル３０ｃのみを生成する。scatファイルに誤りがある場合とは、配置しようとする領域に対して配置しようとするオブジェクトの累計サイズが超えてしまう場合である。リンクエラーが発生する状況を説明する。まず、scatファイルにおけるオブジェクトの配置指定の記述方法としては、先に説明した図２Ａのように、配置しようとする領域に対して直接的にオブジェクト名を記述する方法の他に、ワイルドカード（＊）を用いて記述する方法がある。
【００１８】
直接的にオブジェクト名を記述されている場合、リンカー２２はその領域にそのオブジェクトを配置しようとする。そのため、配置しようとする領域に対して直接的にオブジェクト名が記述されている場合であってそれらの直接的にオブジェクト名が記述されているオブジェクトの累計サイズが配置しようとする領域のサイズを超える場合にリンクエラーが発生する。なお、ワイルドカード（＊）を用いて記述する場合は、直接的にオブジェクト名で列挙されているオブジェクト以外を列挙していることと等価である。直接的にオブジェクト名で列挙されていないオブジェクトについては、ある特定の領域に優先的に配置させたいという意図は、直接的にオブジェクト名を記載して列挙しているオブジェクトより低い。
【００１９】
図３Ａは、リンクエラーが発生するscatファイルの例を示している。各領域のサイズやアドレス、領域名、リンク処理の対象とする４つのオブジェクト（a.o、b.o、c.o、d.o）のサイズは、図２の例と同じものとする。領域Ｃのサイズは0x2000000バイトであるが、図３Ａのscatファイルでは、領域Ｃにc.oとd.oの２つのオブジェクトを配置するように記載されており、領域Ｃにあふれが生じる（図３Ｃ参照）。また、領域Ａにはa.oと*.oが記述されている。つまり、領域Ａにはa.oを優先的に配置しようとするとともにa.o以外のオブジェクトも配置可能であることを意味する。このようなscatファイルを参照してリンカー２２がリンク処理を実行すると、例えば図８Ｂに示すようなマップファイルが出力される。制御部２０は、リンクエラーが発生したときのマップファイルを解析すると、オブジェクトのあふれが発生している領域を検出することができる。
【００２０】
配置指示情報更新プログラム２３は、リンカー２２においてリンクエラーが発生したときに、scatファイル３０ｂに記載されているオブジェクトの配置指示情報を修正し新しいscatファイル３０ｂを出力する機能を有している。その機能を実現するために配置指示情報更新プログラム２３は、マッピング情報取得部２３ａ、配置優先度設定部２３ｂ、配置可能領域情報取得部２３ｃ、組み合わせ決定部２３ｄ、配置指示情報更新部２３ｅを備えている。各部の詳細は、配置指示情報更新処理の説明と合わせて後述する。
【００２１】
（２）配置指示情報更新処理：
次に、上述の構成における配置指示情報更新処理を説明する。配置指示情報更新処理は、リンクエラーが発生するような場合にその際にリンカー２２が参照したscatファイル３０ｂやリンカー２２が出力したマップファイル３０ｃ等に基づいて、リンクエラーを発生しないようなscatファイルを新しく生成する処理である。以降の処理ステップにおいてする具体例の説明には、上述の図３のリンクエラーのケースを用いるものとする。
【００２２】
図４は配置指示情報更新処理の流れを示すフローチャートである。まず、制御部２０は、この処理で使用する変数を初期化する（ステップＳ１００）。以降、順に、現状配置情報取得処理（ステップＳ１０５）、配置優先度設定処理（ステップＳ１１０）、組み合わせ決定処理（ステップＳ１２０）、scatファイル出力処理（ステップＳ１２５）を実行する。
【００２３】
（２−１）変数初期化：
ステップS１００で初期化される変数について説明する。配置指示情報更新処理では、オブジェクト情報構造体３０ｅ、領域情報構造体３０ｆ、属性テーブル３０ｄの３つのデータ構造体を用いる。オブジェクト情報構造体は３０ｅ、個々のオブジェクトに関する情報を格納するデータ構造体であり、オブジェクトファイル名・属性（ＴＥＸＴ，ＤＡＴＡ，ＢＳＳ等）・サイズ・現割り当て領域・新割り当て領域・領域毎の優先度配列をメンバーに持つ。ステップＳ１００では各メンバーに「−１」を設定して初期化する。
【００２４】
領域情報構造体３０ｆは、領域毎にサイズの過不足状況を保持するためのデータ構造体であり、領域ごとに、領域の先導アドレス・サイズ・配置しようとするオブジェクトの累計サイズをメンバーに持つ。ステップＳ１００では、例えば「−１」を設定して初期化する。属性テーブル３０ｄは、ＴＥＸＴ，ＤＡＴＡ，ＢＳＳ等のオブジェクトの属性ごとに、各領域に対する配置可否配列をメンバーに持つ。具体的には、その属性を持つオブジェクトを各領域に配置可能であるか（＋１）、または配置を禁止するか（−１）を示す値が設定されている。ステップＳ１００では、予めユーザーによって定義された初期値（＋１／−１）を設定する。
【００２５】
（２−２）現状配置情報取得処理：
図５は、現状配置情報取得処理を示すフローチャートである。制御部２０は、配置可能領域情報取得部２３ｃの処理を実行することにより、オブジェクトの配置に割り当てる複数の領域のアドレスとサイズを取得し、領域情報構造体３０ｆにそれぞれ設定する（ステップＳ２００）。具体的には例えば、制御部２０はscatファイル３０ｂを解析し、各領域の先頭アドレスとサイズを取得し、領域情報構造体３０ｆの「先頭アドレス」と「サイズ」にそれぞれ設定する。それらの領域をアドレスの若い順に領域Ａ、領域Ｂ、領域Ｃと呼ぶことにする。
【００２６】
続いて制御部２０は、マッピング情報取得部２３ａの処理を実行することによりマップファイル３０ｃを解析する（ステップＳ２０５）。解析の結果、制御部２０は、マップファイルに記載されている、オブジェクト名と、当該オブジェクトのアドレス・サイズ・属性との対応をオブジェクトごとに取得する。制御部２０は、各オブジェクトについて、そのオブジェクトを配置しようとしているアドレスから、当該オブジェクトを配置しようとしている領域を判定し、オブジェクト情報構造体３０ｅの「現割り当て領域」にその領域の識別子を設定する（ステップＳ２１０）。続いて、制御部２０は、各オブジェクトのサイズをオブジェクト情報構造体３０ｅの各オブジェクトに対応する「サイズ」に格納する（ステップＳ２１５）。なお、各オブジェクトのオブジェクト名や属性もオブジェクト情報構造体３０ｅの各オブジェクトに対応する「オブジェクト名」・「属性」に設定される。
【００２７】
続いて、制御部２０は、マップファイル３０ｃに記載されている全てのオブジェクトについてオブジェクト情報構造体３０ｅへの設定が終了すると（ステップＳ２２０）、各領域に配置しようとするオブジェクトの累計サイズを計算し、領域情報構造体３０ｆの各領域に対応する「累計サイズ」に設定する（ステップＳ２２５）。図９Ａおよび図９Ｂは、現状配置情報取得処理を終了した時点での領域情報構造体３０ｆの設定内容とオブジェクト情報構造体３０ｅの設定内容とを示している。
【００２８】
（２−３）配置優先度設定処理：
図６は、配置優先度設定部２３ｂによる配置優先度設定処理を示すフローチャートである。この処理は、scatファイル３０ｂと属性テーブル３０ｄとに基づいて、各オブジェクトについて、各領域に対する配置優先度を設定する処理である。まず制御部２０は、scatファイル３０ｂの内容を解析する（ステップＳ３００）。scatファイルでは、領域ごとにその領域に配置しようとするオブジェクトを、直接的にオブジェクト名を列挙するかあるいはワイルドカードによって記述している。解析の結果、任意の領域Ｘに対して列挙されている文字列が現状配置情報取得処理で取得したオブジェクト名の中のいずれかと一致しているか判定し（ステップＳ３０５）、一致している場合は、当該オブジェクトを、領域Ｘに最も優先度高く配置することを示す「＋２」を、オブジェクト情報構造体３０ｅの当該オブジェクトの「優先度配列」の領域Ｘに設定する（ステップＳ３１０）。具体的には、ステップＳ３１０の処理を実行すると、オブジェクトa.oについては、領域Ａに「＋２」、オブジェクトc.o、d.oについては領域Ｃに「＋２」が設定される（図９Ｃ参照）。
【００２９】
次に制御部２０は、任意の領域Ｘに対して列挙されている文字列が、オブジェクト名と一致しない場合であってその文字がワイルドカードを意味する「*.o」と一致するかどうかを判定する（ステップＳ３１５）。「*.o」と一致する場合は、直接的にオブジェクト名で記述する場合よりも配置優先度が低いことを示す「＋１」を、領域Ｘについて直接的にオブジェクト名で記述されていない全てのオブジェクトに対応するオブジェクト情報構造体３０ｅの「優先度配列」の領域Ｘに設定する（ステップＳ３２０）。具体的には、「*.o」が記述されている領域Ａについて、直接的にオブジェクト名で記述されているa.o以外の全てのオブジェクトであるb.o、c.o、d.oに対応するオブジェクト情報構造体３０ｅの領域Ａに「＋１」を設定する（図９Ｄ参照）。
【００３０】
すなわち、本実施形態において、配置優先度として設定されうる「＋２」は、そのオブジェクトをその領域に優先的に配置することを示している。「＋１」は、そのオブジェクトをその領域に配置可能である（別の領域に配置してもよい）ことを意味している。初期値でもある「−１」は、そのオブジェクトをその領域に配置することを禁止することを示している。属性テーブル３０ｄに設定されている「＋１」と「−１」についても上記と同じ意味を持つ。
【００３１】
制御部２０は、scatファイルに記述されているすべてのオブジェクト名文字列あるいはワイルドカード文字列について、オブジェクト情報構造体３０ｅへの設定が完了したか否かを判定し（ステップＳ３２５）、完了するまで以上の処理を繰り返す。設定が終了すると、制御部２０は、scatファイルに記載されていた領域の優先度配列に未設定箇所があるか否かを判定する（ステップＳ３３０）。具体的には、ステップＳ３３０を実行する時点で、オブジェクト情報構造体３０ｅは図９Ｄに示す状態であり、オブジェクトa.oとb.oに関する領域Ｃへの配置優先度を表す値が設定されていない。すなわち、初期値「−１」のままで、新たに値が設定されていない。領域Ｂは属性テーブル３０ｄで予め定義されているように配置禁止領域であるので除外される。そのため制御部２０は、属性テーブル３０ｄを参照し、未設定箇所を埋める。
【００３２】
属性テーブル３０ｄは、ＴＥＸＴやＤＡＴＡ，ＢＳＳなどのオブジェクトの属性ごとに、各領域についてその領域に配置可能であるか（＋１）、または配置を禁止するか（−１）を示す値が設定されたデータ構造体である。設定値は予めユーザーによって定義されており、その設定値に基づいてステップＳ１００において初期化されている。図１０Ａは属性テーブル３０ｄの例を示している。
【００３３】
制御部２０は、オブジェクト情報構造体３０ｅを参照し、オブジェクトa.oとb.oの属性「ＴＥＸＴ」を取得する。図１０Ａの属性テーブル３０ｄでは、属性がＴＥＸＴであるオブジェクトは領域Ｃへは配置可能（＋１）であるため、領域Ｃに対応するオブジェクトa.o、b.oの変数に「＋１」を設定する（図１０Ｂ参照）。以上のように、配置優先度設定処理で設定した値は、後述するナップザック問題のパラメーターとして用いられる。
【００３４】
（２−４）組み合わせ決定処理：
次に、制御部２０は組み合わせ決定処理を実行する（ステップＳ１２０、組み合わせ決定部２３ｄの処理に対応する）。図７は、組み合わせ決定処理を示すフローチャートである。制御部２０は、配置可能領域からあふれて配置されるオブジェクトが存在するか否かを判定する（ステップＳ４００）。あふれて配置されるオブジェクトが存在するかどうかを判定することは、マップファイルにおいて、当該配置可能領域に配置しようとするオブジェクトの累計サイズが、配置可能領域のサイズよりも大きいかどうかを判定することと同義である。したがって制御部２０は、領域情報構造体３０ｆの各領域について、それぞれ「サイズ」と「累計サイズ」を比較し、「累計サイズ」が「サイズ」より大きい領域が存在するか否かを判定する。あふれる領域が存在する場合、その領域に対して、前述の配置優先度設定処理で優先度配列に設定した値を品物の価値とし、各オブジェクトのサイズを品物の大きさ、当該あふれる領域のサイズをナップザックの大きさとしてナップザック問題を解く（ステップＳ４０５）。
【００３５】
ナップザック問題は、大きさｗと価値ｖを持った品物がＮ個あり、これらを大きさＷのナップザックに入れる場合に、大きさの合計がＷを超えず、価値の合計が最大となるような品物の組み合わせを求める問題である。本実施形態では、この問題を計算機上で解くにあたり動的計算法を利用した周知のアルゴリズムを採用する。最適な組み合わせを総当たり的に調べると、組み合わせ調査回数はＯ（２Ｎ）となるが、動的計算法を利用したアルゴリズムを採用すると調査回数はＯ（ＮＷ）となり、最適な組み合わせを決定するまでの計算量を減らすことができる。
【００３６】
具体的には、あふれが発生している領域Ｃについてナップザック問題を解く。すなわち、サイズがa.o、b.o、c.o、d.oの順に0x2000000バイト、0x2000000バイト、0x2000000バイト、0x1000000バイトであり、領域Ｃに対するオブジェクトの配置優先度としてa.o、b.o、c.o、d.oの順に＋１，＋１，＋２，＋２の価値を持った、オブジェクト４個を、サイズが0x2000000バイトの領域Ｃに、当該サイズを超えずできるだけ価値の合計が最大となるように配置できる組み合わせを求める。その結果、上記条件を満たす組み合わせとして、オブジェクトc.oが選ばれる。制御部２０は、オブジェクト情報構造体３０ｅのオブジェクトc.oの「新割り当て領域」にＣを設定する（図１０Ｃ参照）。
【００３７】
続いて制御部２０は、配置領域未決定オブジェクトの配置領域決定処理を実行する（ステップＳ４１０）。図８は、未決定オブジェクトの配置領域決定処理を示すフローチャートである。制御部２０は、未決定オブジェクトが存在するか否かを判定し（ステップＳ５００）、存在する場合は、配置可能領域が存在するか否かを判定する（ステップＳ５０５）。具体的には、ステップＳ４０５で領域Ｃにオブジェクトc.oが割り当てられることが決まると、オブジェクトd.oが配置する領域が決定していない状態となるため未決定オブジェクトは存在する。またオブジェクト情報構造体３０ｅ（図１０Ｃ）を参照すると、オブジェクトd.oに対応する領域Ａには「＋１」が設定されており、すなわちオブジェクトd.oは領域Ｃ以外に領域Ａにも配置可能であることが示されている。
【００３８】
配置可能領域が存在する場合、制御部２０は、ナップザック問題の対象にまだなっていない領域であってかつその領域にオブジェクトのあふれは発生していないかどうかを判定する（ステップＳ５１０）。ナップザック問題未対象領域であってその領域にあふれが発生していない場合は、当該ナップザック問題未対象領域に対してナップザック問題を解く（ステップＳ５１５）。具体的には、領域Ａはナップザック問題の対象とまだしておらず、領域情報構造体３０ｆを参照すると、あふれも発生していないため、ステップＳ５１５では領域Ａに対してナップザック問題を解く。対象とするオブジェクトは配置領域が確定していないオブジェクトである。すなわち、サイズがa.o、b.o、d.oの順に0x2000000バイト、0x2000000バイト、0x1000000バイトであり、領域Ａに対するオブジェクトの配置優先度としてa.o、b.o、d.oの順に＋２，＋１，＋１の価値を持った、オブジェクト３個を、サイズが0x6000000バイトの領域Ａに、当該サイズを超えずできるだけ価値の合計が最大となるように配置できる組み合わせを求める。その結果、領域Ａに割り当てるオブジェクトの組み合わせとしてa.o、b.o、d.oが決定し、制御部２０は、オブジェクト情報構造体３０ｅのa.o、b.o、d.oの「新割り当て領域」に領域Ａを設定する（図１０Ｄ参照）。
【００３９】
ステップＳ５００で、未決定オブジェクトがもう存在しないと判定された場合は、図６のステップＳ４００に戻る。ステップＳ５０５で配置可能領域が存在しないと判定された場合は未決定オブジェクトの配置領域決定処理を終了する。なお、ステップＳ５１０でナップザック問題未対象領域でないかまたはその領域があふれている場合は、ステップＳ５０５の処理に戻って、ナップザック問題未対象領域でかつあふれが発生していない領域を探す。
【００４０】
（２−５）scatファイル出力：
ステップＳ１２０の組み合わせ決定処理を終えると、制御部２０は、各配置可能領域に割り当てられたオブジェクトの組み合わせに基づいて、リンクエラーを発生させない新しいscatファイル３０ｇを出力する（ステップＳ１２５、配置指示情報更新部２３ｅの処理に対応する）。具体的には、制御部２０は、領域情報構造体３０ｆの領域毎の「サイズ」と、オブジェクト情報構造体３０ｅの各オブジェクトの「新割り当て領域」を参照して、各領域に配置しようとするオブジェクトを列挙したscatファイル３０ｇを生成する。より具体的には、領域Ａに対してオブジェクト名a.oとb.oとd.oを列挙し、領域Ｃに対してオブジェクト名c.oを列挙したscatファイルを生成する（図１１参照）。
【００４１】
以上の配置指示情報更新処理を実行することによって新たに生成されたscatファイル３０ｇをリンカー２２に参照させてリンク処理を実行させると、リンクエラーが発生することなく、scatファイル３０ｇに記載された通りにオブジェクトをメモリ内に配置することができる。
【００４２】
（３）他の実施形態：
尚、本発明の技術的範囲は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加え得ることは勿論である。例えば、上記実施形態で用いたデータ構造体の内容やデータ構造はこれに限定されるものではない。
【符号の説明】
【００４３】
１０：コンピューター、２０：制御部、２１：コンパイラー、２２：リンカー、２３：配置指示情報更新プログラム、２３ａ：マッピング情報取得部、２３ｂ：配置優先度設定部、２３ｃ：配置可能領域情報取得部、２３ｄ：組み合わせ決定部、２３ｅ：配置指示情報更新部、３０ａ：オブジェクトファイル、３０ｂ：scatファイル（旧）、３０ｃ：マップファイル、３０ｄ：属性テーブル、３０ｅ：オブジェクト情報構造体、３０ｆ：領域情報構造体、３０ｇ：scatファイル（新）。
【図１】
2010218201.tif 000003
【図２】
2010218201.tif 000004
【図３】
2010218201.tif 000005
【図４】
2010218201.tif 000006
【図５】
2010218201.tif 000007
【図６】
2010218201.tif 000008
【図７】
2010218201.tif 000009
【図８】
2010218201.tif 000010
【図９】
2010218201.tif 000011
【図１０】
2010218201.tif 000012
【図１１】
2010218201.tif 000013