(57)【要約】【課題】大容量データに対するランダムアクセス可能なマルチプレクサ回路の回路量を削減する。【解決手段】Ｍ個のデータ区分を格納する第１レジスタ３１から、任意のデータ区分を先頭とするＮ（Ｎ＜Ｍ）個のデータ区分を、第２レジスタ３２へロードするマルチプレクサ回路３０において、第１レジスタ３１と第２レジスタ３２との間に中間レジスタ３３が介設される。そして、第１レジスタ３１と中間レジスタ３３との間の第１選択回路３４、および、中間レジスタ３３と第２レジスタ３２との間の第２選択回路３５は、第１選択回路３４および第２選択回路３５の回路量を最小にするＬの値に基づいて設計されている。前記回路量を最小にするＬの値は、ＭおよびＮの値に応じて算出される。【選択図】図４
2015154400.tif 000002
【特許請求の範囲】
【請求項１】
Ｍ（Ｍは２以上の整数）個のデータ区分を格納する第１レジスタから、任意のデータ区分を先頭とするＮ（ＮはＮ＜Ｍの整数）個のデータ区分を、第２レジスタへロードするマルチプレクサ回路であって、
前記第１レジスタと前記第２レジスタとの間において、前記Ｍ個のデータ区分のうちの、前記Ｎ個のデータ区分を含むＬ（ＬはＮ＜Ｌ＜Ｍの整数）個のデータ区分を、一時的に格納する中間レジスタと、
前記第１レジスタから前記中間レジスタへ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を選択的にロードする第１選択回路と、
前記中間レジスタから前記第２レジスタへ、前記Ｌ個のデータ区分のうちの前記Ｎ個のデータ区分を選択的にロードする第２選択回路と、を有し、
前記第１選択回路および前記第２選択回路は、前記ＭおよびＮの値に応じて算出された、前記第１選択回路および前記第２選択回路の回路量を最小にするＬの値に基づいて設計されている、マルチプレクサ回路。
【請求項２】
前記第１選択回路は、前記Ｍ個のデータ区分の先頭から所定個数Ｂ（Ｂ≦Ｎ）毎のデータ区分を先頭とする前記Ｌ（ただし、Ｌ＝Ｎ＋Ｂ−１）個のデータ区分を、前記中間レジスタへ選択的にロードして格納する、
請求項１に記載のマルチプレクサ回路。
【請求項３】
前記第１選択回路および前記第２選択回路の回路量が、前記Ｍ，Ｎ，Ｂの値と下記回路量換算式（１）とに基づいて、２個のデータ区分から１個のデータ区分を選択的に切り換えて出力する２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）によって換算され、
下記回路量換算式（１）によって換算される前記２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）を最小にするＢの値が、下記式（２）を満たす整数ｋまたはｋ＋１として決定されている、
請求項２に記載のマルチプレクサ回路。
【数１】
2015154400.tif 000016
【請求項４】
前記ｋおよび前記ｋ＋１のうち、前記ｋおよび前記ｋ＋１をそれぞれ上記回路量換算式（１）に代入して得られる前記２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）が小さくなる方が、前記２：１マルチプレクサの個数を最小にするＢの値として決定されている、
請求項３に記載のマルチプレクサ回路。
【請求項５】
Ｍ（Ｍは２以上の整数）個のデータ区分を格納する第１レジスタから、任意のデータ区分を先頭とするＮ（ＮはＮ＜Ｍの整数）個のデータ区分を、第２レジスタへロードするマルチプレクサ回路であって、前記第１レジスタと前記第２レジスタとの間において、前記Ｍ個のデータ区分のうちの、前記Ｎ個のデータ区分を含むＬ（ＬはＮ＜Ｌ＜Ｍの整数）個のデータ区分を、一時的に格納する中間レジスタと、前記第１レジスタから前記中間レジスタへ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を選択的にロードする第１選択回路と、前記中間レジスタから前記第２レジスタへ、前記Ｌ個のデータ区分のうちの前記Ｎ個のデータ区分を選択的にロードする第２選択回路と、を有する前記マルチプレクサ回路を設計するコンピュータに、
前記ＭおよびＮの値を取得し、
前記第１選択回路および前記第２選択回路の回路量を最小にする前記Ｌの値を、前記ＭおよびＮの値に基づいて算出し、
前記第１選択回路および前記第２選択回路を、算出された前記Ｌの値に基づいて生成する、
処理を実行させる、マルチプレクサ回路の設計プログラム。
【請求項６】
Ｍ（Ｍは２以上の整数）個のデータ区分を格納する第１レジスタから、任意のデータ区分を先頭とするＮ（ＮはＮ＜Ｍの整数）個のデータ区分を、第２レジスタへロードするマルチプレクサ回路であって、前記第１レジスタと前記第２レジスタとの間において、前記Ｍ個のデータ区分のうちの、前記Ｎ個のデータ区分を含むＬ（ＬはＮ＜Ｌ＜Ｍの整数）個のデータ区分を、一時的に格納する中間レジスタと、前記第１レジスタから前記中間レジスタへ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を選択的にロードする第１選択回路と、前記中間レジスタから前記第２レジスタへ、前記Ｌ個のデータ区分のうちの前記Ｎ個のデータ区分を選択的にロードする第２選択回路と、を有する前記マルチプレクサ回路を
設計する装置であって、
前記ＭおよびＮの値を取得する取得部と、
前記第１選択回路および前記第２選択回路の回路量を最小にする前記Ｌの値を、前記ＭおよびＮの値に基づいて算出する算出部と、
前記第１選択回路および前記第２選択回路を、前記算出部によって算出された前記Ｌの値に基づいて生成する生成部と、有する、マルチプレクサ回路の設計装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチプレクサ回路、マルチプレクサ回路の設計プログラムおよびマルチプレクサ回路の設計装置に関する。
【背景技術】
【０００２】
近年、情報処理装置に係るハードウエアの性能向上（処理速度の高速化，回路の高密度化等）に伴い、ハードウエアで扱えるデータ量は、極めて大きな容量（例えば数千〜数ギガバイト）になっている。当該ハードウエアとしては、例えば、ネットワークパケット処理回路，動画データエンコード／でコード回路，データベース処理回路が挙げられる。
【０００３】
また、半導体技術の進化に伴い、ＡＳＩＣ（Application Specific Integrated Circuit），ＦＰＧＡ（Field Programmable Gate Array）などのＬＳＩ（Large Scale Integration）の単体チップでも、数メガバイトの大容量データを搭載することが可能になっている。
【０００４】
このようなＬＳＩ上で大容量データを保持する回路としては、オンチップメモリやレジスタ（またはＦＦ（flip-flop））が用いられている。
【０００５】
オンチップメモリはポート数に制限があるため、オンチップメモリに対し同時にアクセスすることの可能な処理回路の数にも制限がある。したがって、ハードウエアの処理性能を向上させるためにはハードウエアの使い方を工夫する必要がある。
【０００６】
一方、レジスタは、ポート数を多く取ることができるため、多数の処理回路から同時にランダムアクセスすることが可能である。したがって、レジスタは、ハードウエアの処理性能を向上させるのに適している。
【０００７】
ところで、一般に、大容量データは、データ構造を有する。例えば、ＴＣＰ（Transmission Control Protocol）(IPv4)パケットは、図１２に示すようなデータ構造を有している。さらに、ネットワークパケットや動画ファイルは、データ構造の情報さえも、ヘッダとしてデータに含まれる。
【０００８】
このような大容量データをＬＳＩ等で処理する場合、例えば図１３に示すように、データ全体（Ｍバイト）をレジスタに格納してから、指定されたオフセットに配置されているフィールドデータ（Ｎバイト；Ｎ＜Ｍ）に対するアクセスが、頻繁に実行される。
【０００９】
このとき、柔軟で且つ高速な処理を実現するために、Ｍバイト長のデータにおいて、任意のオフセットからＮバイトのフィールドデータに対し、一度に（即ち１クロックサイクルで）アクセスできるようにすることが好ましい。
【００１０】
なお、図１３では、Ｍバイトのデータ区分において、オフセット８バイトから連続するＮ（Ｎ＝４）バイトのデータ区分にアクセスする例が示されている。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開平０５−１９１２９１号公報
【特許文献２】特開平０６−７７７９２号公報
【特許文献３】特開平０７−６６６９９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
大容量データに対するランダムアクセスを実現するためには、大容量データ（Ｍバイト長データ）を格納する第１レジスタと、処理回路で処理するフィールドデータ（Ｎバイト長データ）を格納する第２レジスタとは、マルチプレクサ回路によって接続される。当該マルチプレクサ回路は、制御信号を受け第１レジスタと第２レジスタとの間の接続関係を切り換え、第１レジスタから第２レジスタへのデータロード、または、第２レジスタから第１レジスタへのデータロードを行なう。
【００１３】
しかしながら、大容量データに対するランダムアクセスを可能にするマルチプレクサ回路の回路量は、極めて大きくなる。
【００１４】
一つの側面で、本発明は、大容量データに対するランダムアクセス可能なマルチプレクサ回路の回路量を削減することを目的とする。
【課題を解決するための手段】
【００１５】
本件のマルチプレクサ回路は、Ｍ（Ｍは２以上の整数）個のデータ区分を格納する第１レジスタから、任意のデータ区分を先頭とするＮ（ＮはＮ＜Ｍの整数）個のデータ区分を、第２レジスタへロードする。また、本件のマルチプレクサ回路は、中間レジスタ，第１選択回路および第２選択回路を有している。前記中間レジスタは、前記第１レジスタと前記第２レジスタとの間において、前記Ｍ個のデータ区分のうちの、前記Ｎ個のデータ区分を含むＬ（ＬはＮ＜Ｌ＜Ｍの整数）個のデータ区分を、一時的に格納する。前記第１選択回路は、前記第１レジスタから前記中間レジスタへ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を選択的にロードする。前記第２選択回路は、前記中間レジスタから前記第２レジスタへ、前記Ｌ個のデータ区分のうちの前記Ｎ個のデータ区分を選択的にロードする。そして、前記第１選択回路および前記第２選択回路は、前記ＭおよびＮの値に応じて算出された、前記第１選択回路および前記第２選択回路の回路量を最小にするＬの値に基づいて設計されている。
【発明の効果】
【００１６】
一実施形態によれば、大容量データに対するランダムアクセス可能なマルチプレクサ回路の回路量が削減される。
【図面の簡単な説明】
【００１７】
【図１】（Ａ）は２：１マルチプレクサの基本構成を示す図、（Ｂ）は（Ａ）に示す２：１マルチプレクサの真理値表を示す図である。
【図２】２：１マルチプレクサによって構成された４：１マルチプレクサを示す図である。
【図３】入力レジスタにおけるＭバイトのデータ区分から、任意のデータ区分を先頭とするＮバイトのデータ区分を、出力レジスタへ直接的にロードするＭＵＸ木の例を示す図である。
【図４】本発明の第１実施形態での設計対象マルチプレクサ回路の構成を説明する図である。
【図５】本発明の第１実施形態としてのマルチプレクサ回路の設計手順を説明するフローチャートである。
【図６】図５に示す設計手順でマルチプレクサ回路の設計を行なうマルチプレクサ回路設計装置のハードウエア構成および機能構成を示すブロック図である。
【図７】図６に示すマルチプレクサ回路設計装置によって生成設計されたマルチプレクサ回路の一例を示す図である。
【図８】入力・中間レジスタ間隔Ｂと２：１マルチプレクサの個数との関係を示すグラフである。
【図９】入力・中間レジスタ間隔Ｂと２：１マルチプレクサの段数との関係を示すグラフである。
【図１０】本発明の第２実施形態での設計対象マルチプレクサ回路の構成を説明する図である。
【図１１】本発明の第２実施形態としてのマルチプレクサ回路の設計手順を説明するフローチャートである。
【図１２】ＴＣＰ(IPv4)パケットのデータ構造を示す図である。
【図１３】Ｍバイト長データにおけるＮバイト（Ｎ＜Ｍ）のデータに対するアクセスの一例を示す図である。
【発明を実施するための形態】
【００１８】
以下に、図面を参照し、本願の開示するマルチプレクサ回路、マルチプレクサ回路の設計プログラムおよびマルチプレクサ回路の設計装置の実施形態について、詳細に説明する。ただし、以下に示す実施形態は、あくまでも例示に過ぎず、実施形態で明示しない種々の変形例や技術の適用を排除する意図はない。すなわち、本実施形態を、その趣旨を逸脱しない範囲で種々変形して実施することができる。また、各図は、図中に示す構成要素のみを備えるという趣旨ではなく、他の機能を含むことができる。そして、各実施形態は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【００１９】
〔１〕マルチプレクサ回路の構成
まず、図１〜図４を参照しながら、本実施形態での設計対象になるマルチプレクサ回路について説明する。以下では、説明を簡単にするため、バイト単位でのアクセスが対象とされ、マルチプレクサの入出力データのデータ幅、即ち１個のデータ区分のサイズは、８ビット（１バイト）とする。したがって、以下では、データのバイト数（バイト長）とデータ区分の個数とは等価なものとして説明する。なお、「マルチプレクサ」は「ＭＵＸ」と記載される場合がある。
【００２０】
任意のマルチプレクサは、複数の２：１−ＭＵＸ（２：１マルチプレクサ）の組み合わせによって実現することができる。２：１−ＭＵＸは、２入力１出力のＭＵＸであり、例えば図１（Ａ）に示すように、不図示の制御部等からの制御信号Ｃによって２個のデータ区分Ａ，Ｂのいずれか一方を選択的に切り換えて１個のデータ区分Ｘとして出力する。このとき、２：１−ＭＵＸは、例えば図１（Ｂ）に示す真理値表に従って制御される。つまり、制御信号が０の場合、２：１−ＭＵＸはデータ区分Ａを出力する一方、制御信号が１の場合、２：１−ＭＵＸはデータ区分Ｂを出力する。なお、図１（Ａ）は２：１−ＭＵＸの基本構成を示す図、図１（Ｂ）は図１（Ａ）に示す２：１−ＭＵＸの真理値表を示す図である。
【００２１】
一般に、ｐ（ｐは２以上の整数）個のデータ区分から１個のデータ区分を選択的に切り換えて出力するｐ：１−ＭＵＸを実現するために必要な２：１−ＭＵＸの個数および２：１−ＭＵＸの段数は、それぞれ下記式（１），（２）によって算出される。
【００２２】
【数１】
2015154400.tif 000003
【００２３】
例えば、図２は、２：１−ＭＵＸによって構成された４：１−ＭＵＸを示す図、つまりｐ＝４のマルチプレクサ回路の２：１−ＭＵＸ構成を示す図である。図２に示す４：１−ＭＵＸは、４個のデータ区分Ａ１，Ａ２，Ａ３，Ａ４のうちのいずれか一つを１個のデータ区分Ｘとして出力する。４：１−ＭＵＸを実現するために必要な２：１−ＭＵＸの個数および２：１−ＭＵＸの段数は、上記式（１），（２）や図２から明らかなように、それぞれ３および２となる。
【００２４】
上述したように、任意のマルチプレクサは、複数の２：１−ＭＵＸの組み合わせによって実現されるので、当該マルチプレクサの回路量は、２：１−ＭＵＸの個数に換算することができる。そこで、後述するごとく、本実施形態において、設計対象のマルチプレクサ回路における第１選択回路および第２選択回路（図４や図１０の符号３４，３５参照）の回路量は、後述する回路量換算式（６）や（１４）を用いて、２：１−ＭＵＸの個数Ｔに換算される。
【００２５】
ところで、図１３を参照しながら前述したように、大容量データをＬＳＩ等で処理する場合、Ｍバイトのデータ全体をレジスタに格納してから、任意のオフセットに配置されているＮバイトのフィールドデータに対するアクセスが一度に（１クロックサイクルで）行なわれる。
【００２６】
図３では、Ｍ個のデータ区分を格納する入力レジスタ（第１レジスタ）３１から、任意のデータ区分を先頭とするＮ個のデータ区分を、出力レジスタ（第２レジスタ）３２へ直接的にロードするＭＵＸ木３６ａ〜３６ｄの例が示されている。特に、図３では、Ｍ＝１６，Ｎ＝４の例が示されている。図３に示すように、入力レジスタ３１は、１６個のデータ区分をそれぞれ格納する入力レジスタ＃０〜＃１５を有し、出力レジスタ３２は、入力レジスタ３１からロードされたＮ個のデータ区分をそれぞれ格納する出力レジスタ＃０〜＃３を有している。
【００２７】
この場合、入力レジスタ３１と出力レジスタ３２との間には、４つのＭＵＸ木（選択回路）３６ａ〜３６ｄが形成される。つまり、出力レジスタ＃０と１３個の入力レジスタ＃０〜＃１２との間にＭＵＸ木３６ａが形成され、出力レジスタ＃１と１３個の入力レジスタ＃１〜＃１３との間にＭＵＸ木３６ｂが形成される。同様に、出力レジスタ＃２と１３個の入力レジスタ＃２〜＃１４との間にＭＵＸ木３６ｃが形成され、出力レジスタ＃３と１３個の入力レジスタ＃３〜＃１５との間にＭＵＸ木３６ｄが形成される。
【００２８】
図３に示す４つのＭＵＸ木３６ａ〜３６ｄを実現するために必要な２：１−ＭＵＸの個数および２：１−ＭＵＸの段数は、それぞれ下記式（３），（４）によって算出される。つまり、Ｍ＝１６，Ｎ＝４の場合、ＭＵＸ木３６ａ〜３６ｄを実現するために必要な２：１−ＭＵＸの個数は、下記式（３）から４８となり、２：１−ＭＵＸの段数は、下記式（４）から４となる。
【００２９】
【数２】
2015154400.tif 000004
【００３０】
このように、データを入力レジスタ３１から出力レジスタ３２へ直接的にロードするＭＵＸ木３６ａ〜３６ｄでは、必要となる２：１−ＭＵＸの個数が極めて多く、マルチプレクサ回路の回路規模（回路量）が大きくなる。
【００３１】
そこで、マルチプレクサ回路の回路量を削減すべく、以下に説明する第１実施形態のマルチプレクサ回路３０では、図４に示すように、入力レジスタ３１からのデータを、中間レジスタ３３経由で出力レジスタ３２へ間接的にロードする構成が採用されている。なお、図４は、本発明の第１実施形態での設計対象マルチプレクサ回路３０の構成を説明する図である。
【００３２】
図４に示すように、マルチプレクサ回路３０は、Ｍ個のデータ区分を格納する第１レジスタ３１から、任意のデータ区分を先頭とするＮ個のデータ区分を、第２レジスタ３２へロードする。つまり、マルチプレクサ回路３０は、入力レジスタ３１に格納されるＭバイト長のデータにおいて、任意のオフセットからＮ（Ｎ＜Ｍ）バイト長のフィールドデータ（部分データ）を、一度に（即ち１クロックサイクルで）出力レジスタ３２にロードする。図４では、Ｍ＝１６，Ｎ＝４の例が示されている。
【００３３】
図４に示すマルチプレクサ回路３０は、中間レジスタ３３，第１選択回路３４および第２選択回路３５を有している。
【００３４】
中間レジスタ（中間ゲート）３３は、入力レジスタ３１と出力レジスタ３２との間において、前記Ｍ個のデータ区分のうちの、前記Ｎ個のデータ区分を含むＬ（ＬはＮ＜Ｌ＜Ｍの整数）個のデータ区分（Ｌバイト長のデータ）を、一時的に格納する。
【００３５】
第１選択回路（第１段ＭＵＸ木）３４は、入力レジスタ３１から中間レジスタ３３へ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を選択的にロードする。特に、第１実施形態の第１選択回路３４は、前記Ｍ個のデータ区分の先頭から所定個数Ｂ（Ｂ≦Ｎ）毎のデータ区分を先頭とする前記Ｌ個のデータ区分を、中間レジスタ３３へ選択的にロードして格納する。中間レジスタ３３に格納されるデータのデータ長（中間レジスタ３３のサイズに対応する値）Ｌは、下記式（５）によって与えられる。
Ｌ＝Ｎ＋Ｂ−１      （５）
ここで、所定個数Ｂは、中間レジスタ３３のサイズＬを決定するパラメータであり、図４では、Ｂ＝４，Ｌ＝７の例が示されている。なお、以下では、所定個数Ｂを、入力・中間レジスタ間隔Ｂという場合がある。
【００３６】
第２選択回路（第２ＭＵＸ木）３５は、中間レジスタ３３から出力レジスタ３２へ、前記Ｌ個のデータ区分のうちの前記Ｎ個のデータ区分を選択的にロードする。
【００３７】
図４に示す例では、入力レジスタ３１は、１６個のデータ区分をそれぞれ格納する入力レジスタ＃０〜＃１５を有している。また、中間レジスタ３３は、第１選択回路３４によって入力レジスタ３１からロードされたＬ個のデータ区分をそれぞれ格納する中間レジスタ＃０〜＃６を有している。さらに、出力レジスタ３２は、第２選択回路３５によって中間レジスタ３３からロードされたＮ個のデータ区分をそれぞれ格納する出力レジスタ＃０〜＃３を有している。
【００３８】
そして、入力レジスタ３１と中間レジスタ３３との間の第１段ＭＵＸ木３４において、中間レジスタ３３の各バイト（各データ区分）は、入力レジスタ３１上でＢバイト間隔にＭＵＸ木３４ａ〜３４ｇを構成する。つまり、中間レジスタ＃０と４個の入力レジスタ＃０，＃４，＃８，＃１２との間にＭＵＸ木３４ａが形成され、中間レジスタ＃１と４個の入力レジスタ＃１，＃５，＃９，＃１３との間にＭＵＸ木３４ｂが形成される。同様に、中間レジスタ＃２と４個の入力レジスタ＃２，＃６，＃１０，＃１４との間にＭＵＸ木３４ｃが形成され、中間レジスタ＃３と４個の入力レジスタ＃３，＃７，＃１１，＃１５との間にＭＵＸ木３４ｄが形成される。また、中間レジスタ＃４と３個の入力レジスタ＃４，＃８，＃１２との間にＭＵＸ木３４ｅが形成され、中間レジスタ＃５と３個の入力レジスタ＃５，＃９，＃１３との間にＭＵＸ木３４ｆが形成され、中間レジスタ＃６と３個の入力レジスタ＃６，＃１０，＃１４との間にＭＵＸ木３４ｇが形成される。
【００３９】
さらに、中間レジスタ３３と出力レジスタ３２との間の第２段ＭＵＸ木３５において、４つのＭＵＸ木３５ａ〜３５ｄが形成される。つまり、出力レジスタ＃０と４個の中間レジスタ＃０〜＃３との間にＭＵＸ木３５ａが形成され、出力レジスタ＃１と４個の中間レジスタ＃１〜＃４との間にＭＵＸ木３５ｂが形成される。同様に、出力レジスタ＃２と４個の入力レジスタ＃２〜＃５との間にＭＵＸ木３５ｃが形成され、出力レジスタ＃３と４個の入力レジスタ＃３〜＃６との間にＭＵＸ木３５ｄが形成される。
【００４０】
図４に示すマルチプレクサ回路３０では、第１段ＭＵＸ木３４の機能により、中間レジスタ３３には、入力レジスタ３１の下記４つの区間のいずれかにおけるデータが格納される。下記区間のデータは、入力レジスタ３１における、４（＝Ｂ）バイト置きの７（＝Ｂ＋Ｎ−１）バイト長のデータであり、４つ目の区間のデータだけ４バイト長である。
［＃０〜＃６］，［＃４〜＃１０］，［＃８〜＃１４］，［＃１２〜＃１５］
【００４１】
そして、第２段ＭＵＸ木３５の機能により、中間レジスタ３３における、連続する任意の４バイト長のデータが出力レジスタ３２へ読み出される。
【００４２】
上述した第１段ＭＵＸ木３４および第２段ＭＵＸ木３５の機能により、出力レジスタ３２に、入力レジスタ３１における任意オフセットから４（＝Ｎ）バイト長のデータを格納することができる。
【００４３】
ここで、図４に示す第１段ＭＵＸ木３４を実現するために必要な２：１−ＭＵＸの個数は、上記式（３）を用いて算出すると１８となる。また、図４に示す第２段ＭＵＸ木３４を実現するために必要な２：１−ＭＵＸの個数は、上記式（３）を用いて算出すると１２となる。したがって、Ｍ＝１６，Ｎ＝４，Ｂ＝４（つまりＬ＝７）の場合、マルチプレクサ回路３０を実現するために必要な２：１−ＭＵＸの個数は、１８＋１２＝３０となり、図３に示した例の個数４８と比べ大幅に削減される。
【００４４】
〔２〕第１実施形態
第１実施形態では、図４に示す構成のマルチプレクサ回路３０において選択回路３４，３５の回路量を最小にする入力・中間レジスタ間隔Ｂの値を算出し、当該値Ｂに基づき選択回路３４，３５を設計する方法および装置について、図５〜図９を参照しながら説明する。ここで、入力レジスタ３１のサイズに対応する値Ｍと、出力レジスタ３２のサイズに対応する値Ｎとは、予め与えられているが、入力・中間レジスタ間隔Ｂの値、つまりは中間レジスタ３３のサイズに対応する値Ｌ（＝Ｂ＋Ｎ−１）の値は、未定とする。
【００４５】
図５に示すフローチャート（ステップＳ１〜Ｓ７）に従って、本発明の第１実施形態としてのマルチプレクサ回路３０の設計手順について説明する。なお、当該設計手順は、図６を参照しながら後述するマルチプレクサ回路設計装置１の処理部（コンピュータ）１０によって実行される。
【００４６】
第１実施形態では、図４に示す構成のマルチプレクサ回路３０について、入力レジスタ３１のサイズＭと出力レジスタ３２のサイズＮとから、中間レジスタ３３の最適なサイズＬが求められる。実際には、前述した通り、最適なサイズＬを決める入力・中間レジスタ間隔Ｂの最適な値が求められる。
【００４７】
このため、まず、入力レジスタ３１のサイズ（入力バイト数）Ｍと出力レジスタ３２のサイズ（出力バイト数）Ｎとが取得される（ステップＳ１）。このとき、サイズＭ，Ｎは、予め記憶部２０（図６参照）に設定保存されているものを読み出して取得してもよいし、設計者等によってキーボード等の入力装置から入力されたものを受信して取得してもよい。
【００４８】
そして、入力バイト数Ｍ，出力バイト数Ｎおよび入力・中間レジスタ間隔Ｂを変数にとり、且つ、第１段ＭＵＸ木３４および第２段ＭＵＸ木３５の回路量を２：１−ＭＵＸの個数に換算する関数Ｔ（Ｍ，Ｎ，Ｂ）が、下記換算式（６）の通り生成される（ステップＳ２）。
【００４９】
【数３】
2015154400.tif 000005
【００５０】
この後、上記換算式（６）によって得られる値Ｔ（Ｍ，Ｎ，Ｂ）が最小になるＢの値Ｂ′が、下記式（７）で求められる（ステップＳ３）。一般に、値Ｂ′は実数となる。
【００５１】
【数４】
2015154400.tif 000006
【００５２】
そして、上記式（７）によって求められた値Ｂ′が整数値であるか否かが判定される（ステップＳ４）。値Ｂ′が整数値である場合（ステップＳ４のＹＥＳルート）、値Ｂ′が入力・中間レジスタ間隔Ｂとして決定される（ステップＳ５）。
【００５３】
一方、上記式（７）によって求められた値Ｂ′が整数値でない場合（ステップＳ４のＮＯルート）、値Ｂ′が整数化され、整数化された値が入力・中間レジスタ間隔Ｂとして決定される（ステップＳ６）。
【００５４】
このとき、値Ｂ′の整数化は、下記式（８）を満たす整数ｋまたはｋ＋１のいずれか一方を値Ｂとして決定することによって実行される。つまり、ｋおよびｋ＋１が、それぞれ上記換算式（６）にＢの値として代入して２：１−ＭＵＸの個数Ｔ（Ｍ，Ｎ，ｋ）とＴ（Ｍ，Ｎ，ｋ＋１）とが得られる。そして、Ｔ（Ｍ，Ｎ，ｋ）＜Ｔ（Ｍ，Ｎ，ｋ＋１）の場合、整数ｋが、２：１−ＭＵＸの個数つまりは第１段ＭＵＸ木３４および第２段ＭＵＸ木３５の回路量を最小にするＢの値として決定される。また、Ｔ（Ｍ，Ｎ，ｋ＋１）＜Ｔ（Ｍ，Ｎ，ｋ）の場合、整数ｋ＋１が、２：１−ＭＵＸの個数つまりは第１段ＭＵＸ木３４および第２段ＭＵＸ木３５の回路量を最小にするＢの値として決定される。
【００５５】
【数５】
2015154400.tif 000007
【００５６】
ステップＳ５またはＳ６で決定された入力・中間レジスタ間隔Ｂに基づき中間レジスタ３３のサイズＬ＝Ｎ＋Ｂ−１が得られる。そして、得られた中間レジスタ３３のサイズＬと、入力レジスタ３１のサイズＭと、出力レジスタ３２のサイズＮとを用いて、設計対象のマルチプレクサ回路３０の生成が行なわれる（ステップＳ７）。
【００５７】
次に、図６を参照しながら、図５に示す設計手順でマルチプレクサ回路３０の設計を行なうマルチプレクサ回路設計装置１のハードウエア構成および機能構成について説明する。図６は、マルチプレクサ回路設計装置１のハードウエア構成および機能構成を示すブロック図である。
【００５８】
図６に示すように、マルチプレクサ回路設計装置１は、図４に示す構成のマルチプレクサ回路３０を設計する装置である。マルチプレクサ回路設計装置１は、少なくとも、ＣＰＵ（Central Processing Unit），ＭＰＵ（Micro-Processing Unit），コンピュータ等の処理部１０と、ＲＡＭ（Random Access Memory），ＨＤＤ（Hard Disk Drive），ＳＳＤ（Solid State Device）等の記憶部２０とを有している。
【００５９】
処理部１０は、記憶部２０から所定のアプリケーションプログラム（マルチプレクサ回路の設計プログラム）を読み出して実行することで、後述する取得部１１，入力・中間レジスタ間隔計算部１２およびマルチプレクサ回路生成部１３としての機能を果たす。なお、前記所定のアプリケーションプログラムは、例えばフレキシブルディスク，ＣＤ（ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷなど），ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−ＲＡＭ，ＤＶＤ−Ｒ，ＤＶＤ−ＲＷ，ＤＶＤ＋Ｒ，ＤＶＤ＋ＲＷなど），ブルーレイディスク等のコンピュータ読取可能な記録媒体に記録された形態で提供される。この場合、処理部１０は、当該記録媒体からプログラムを読み取って内部記憶装置または外部記憶装置としての記憶部２０に転送し格納して用いる。
【００６０】
記憶部２０は、前記所定のアプリケーションプログラムを保存するほか、処理部１０による処理に必要な各種情報等を保存する。例えば、記憶部２０は、前記各種情報等として、後述する取得部１１によって取得された入力レジスタ３１のバイト数（サイズ）Ｍおよび出力レジスタ３２のバイト数（サイズ）Ｎを保存する。また、記憶部２０は、前記各種情報等として、後述する入力・中間レジスタ間隔計算部１２によって求められた入力・中間レジスタ間隔Ｂ（もしくは当該間隔Ｂによって得られる中間レジスタ３３のバイト数（サイズ））Ｌを保存する。さらに、記憶部２０は、前記各種情報等として、後述するマルチプレクサ回路生成部１３によって生成されるマルチプレクサ回路３０の設計情報を保存する。
【００６１】
以下、処理部１０によって実現される、取得部１１，入力・中間レジスタ間隔計算部１２およびマルチプレクサ回路生成部１３としての機能を、図５に示すフローチャートの各ステップＳ１〜Ｓ７を対応付けて説明する。
【００６２】
取得部１１は、上述したステップＳ１の処理を実行するもので、入力レジスタ３１のサイズ（入力バイト数）Ｍと出力レジスタ３２のサイズ（出力バイト数）Ｎとを取得する。このとき、取得部１１は、前述したように、予め記憶部２０に設定保存されているサイズＭ，Ｎを読み出して取得してもよいし、設計者等によってキーボード等の入力装置（図示略）から入力されたサイズＭ，Ｎを受信して取得してもよい。
【００６３】
入力・中間レジスタ間隔計算部（算出部）１２は、上述したステップＳ２〜Ｓ６の処理を実行するもので、第１段ＭＵＸ木３４および第２段ＭＵＸ木３５の回路量を最小にする入力・中間レジスタ間隔Ｂの値を、サイズＭおよびＮの値に基づいて算出する。そして、入力・中間レジスタ間隔計算部１２またはマルチプレクサ回路生成部１３は、算出された入力・中間レジスタ間隔Ｂの値に基づき、中間レジスタ３３のサイズＬ（＝Ｎ＋Ｂ−１）の値を決定する。
【００６４】
入力・中間レジスタ間隔計算部１２は、第１段ＭＵＸ木３４および第２段ＭＵＸ木３５の回路量を２：１−ＭＵＸの個数に換算する関数Ｔ（Ｍ，Ｎ，Ｂ）を、上記換算式（６）の通り生成する（ステップＳ２）。そして、入力・中間レジスタ間隔計算部１２は、上記換算式（６）によって得られる値Ｔ（Ｍ，Ｎ，Ｂ）が最小になるＢの値Ｂ′を、上記式（７）で求める（ステップＳ３）。
【００６５】
また、入力・中間レジスタ間隔計算部１２は、上記式（７）によって求められた値Ｂ′が整数値であるか否かを判定する（ステップＳ４）。入力・中間レジスタ間隔計算部１２は、値Ｂ′が整数値であると判定した場合、値Ｂ′を入力・中間レジスタ間隔Ｂとして決定する（ステップＳ５）。
【００６６】
一方、入力・中間レジスタ間隔計算部１２は、上記式（７）によって求められた値Ｂ′が整数値でないと判定した場合、値Ｂ′を整数化し、整数化された値を入力・中間レジスタ間隔Ｂとして決定する（ステップＳ６）。値Ｂ′の整数化は、前述した通り、上記式（８）を満たす整数ｋまたはｋ＋１のいずれか一方を値Ｂとして決定することによって実行される。
【００６７】
マルチプレクサ回路生成部１３は、上述したステップＳ７の処理を実行するもので、入力・中間レジスタ間隔Ｂに基づき中間レジスタ３３のサイズＬ＝Ｎ＋Ｂ−１を決定する。そして、マルチプレクサ回路生成部１３は、中間レジスタ３３のサイズＬと、入力レジスタ３１のサイズＭと、出力レジスタ３２のサイズＮとを用いて、設計対象のマルチプレクサ回路３０（ＭＵＸ木３４，３５）の設計情報の生成を行なう。
【００６８】
例えば、Ｍ＝１６，Ｎ＝４のマルチプレクサ回路３０については、図７に示すように、Ｂ＝４が得られ、中間レジスタ３３のサイズＬとしてはＬ＝４＋４−１＝７が得られる。そして、第１段ＭＵＸ木３４は、１８個の２：１−ＭＵＸ木によって構築され、第２段ＭＵＸ木３５は、１２個の２：１−ＭＵＸ木によって構築される。なお、図７は、図６に示すマルチプレクサ回路設計装置１によって生成設計されたマルチプレクサ回路３０の一例を示す図である。
【００６９】
第１実施形態によれば、大容量データを格納する入力レジスタ３１と部分データを保持する出力レジスタ３２との間に、レジスタ３１，３２間の回路量（２：１−ＭＵＸの個数に換算した値）を最小にするサイズＬの中間レジスタ３３が配置される。これにより、回路量を大幅に削減したマルチプレクサ回路３０が生成設計される。つまり、大容量データに対するランダムアクセス可能なマルチプレクサ回路３０の回路量が大幅に削減される。
【００７０】
ここで、２：１−ＭＵＸの個数に基づく第１実施形態の回路量削減効果を、図８に示す。図８は、入力・中間レジスタ間隔Ｂと２：１−ＭＵＸの個数との関係を示すグラフである。なお、図８に示すグラフは、Ｍ＝１０２４でありＮ＝８，１６，３２，６４，１２８，２５６，５１２である場合における、入力・中間レジスタ間隔Ｂと２：１マルチプレクサの個数との関係を示している。図８に示されるように、Ｎ＝６４以上では、２：１−ＭＵＸの個数が最小となるＢの値は、自明でなく、第１実施形態で説明した手順によって最適なＢの値を決定することの必然性が示されている。
【００７１】
また、図９は、入力・中間レジスタ間隔Ｂと２：１−ＭＵＸの段数との関係を示すグラフである。なお、図９に示すグラフは、Ｍ＝１０２４でありＮ＝８，１６，３２，６４，１２８，２５６，５１２である場合における、入力・中間レジスタ間隔Ｂと２：１マルチプレクサの段数との関係を示している。図４や図７に示す構成のマルチプレクサ回路３０におけるＭＵＸ木の段数は、第１段ＭＵＸ木３４および第２段ＭＵＸ木３５の段数を合計することにより下記式（９）によって算出される。下記式（９）の近似式は、下記式（１０）で与えられる。
【００７２】
【数６】
2015154400.tif 000008
【００７３】
上記式（１０）で算出される、第１実施形態のマルチプレクサ回路３０における２：１−ＭＵＸの段数は、図３に示す構成のマルチプレクサ回路について上記式（４）で算出される２：１−ＭＵＸの段数と同等になる。また、２：１−ＭＵＸの段数は、図９に示すように、Ｂの値に依ることなく、９〜１０であり、第１実施形態のマルチプレクサ回路３０でも、図３に示す構成のマルチプレクサ回路と同じ段数が実現されている。つまり、第１実施形態のマルチプレクサ回路３０の処理速度は、図３に示す構成のマルチプレクサ回路の処理速度と同等になる。したがって、第１実施形態のマルチプレクサ回路３０の速度性能は、図３に示す構成のマルチプレクサ回路の速度性能と同等である。
【００７４】
〔３〕第２実施形態
次に、第２実施形態では、第１実施形態で説明した手法を拡張した手法について説明する。第２実施形態のマルチプレクサ回路３０Ａでも、図１０に示すように、入力レジスタ３１Ａからのデータを、中間レジスタ３３Ａ経由で出力レジスタ３２Ａへ間接的にロードする構成が採用されている。なお、図１０は、本発明の第２実施形態での設計対象マルチプレクサ回路３０Ａの構成を説明する図である。
【００７５】
図１０に示すように、マルチプレクサ回路３０Ａは、Ｍ個のデータ区分を格納する第１レジスタ３１Ａから、任意の第１データ区分を先頭とするＮ１個のデータ区分、および、任意の第２データ区分を先頭とするＮ２個のデータ区分を、第２レジスタ３２Ａへロードする。ここで、Ｎ１はＮ１＜Ｍの整数であり、Ｎ２はＮ２＜Ｍの整数であり、第２レジスタ３２Ａのサイズは、Ｎ１＋Ｎ２バイトである。つまり、マルチプレクサ回路３０Ａは、入力レジスタ３１Ａに格納されるＭバイト長のデータにおいて、任意のオフセットからＮ１およびＮ２バイト長のフィールドデータ（部分データ）を同時に（即ち１クロックサイクルで）出力レジスタ３２Ａにロードする。図１０では、Ｍ＝１６，Ｎ１＝４，Ｎ２＝４，Offset＝１の例が示されている。なお、Offsetは、Ｎ１個のデータ区分とＮ２個のデータ区分との、入力レジスタ３１Ａ上での配置間隔を表す定数（０≦Offset≦Ｍ−Ｎ１−Ｎ２）である。
【００７６】
図１０に示すマルチプレクサ回路３０Ａは、中間レジスタ３３Ａ，第１選択回路３４Ａおよび第２選択回路３５Ａを有している。
【００７７】
中間レジスタ（中間ゲート）３３Ａは、入力レジスタ３１Ａと出力レジスタ３２Ａとの間において、前記Ｍ個のデータ区分のうちの、前記Ｎ１個のデータ区分および前記Ｎ２個のデータ区分を含むＬ個のデータ区分（Ｌバイト長のデータ）を一時的に格納する。ＬはＮ１＋Ｎ２＜Ｌ＜Ｍの整数である。
【００７８】
第１選択回路（第１段ＭＵＸ木）３４Ａは、入力レジスタ３１Ａから中間レジスタ３３Ａへ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を、選択的にロードする。特に、第２実施形態の第１選択回路３４Ａは、前記Ｍ個のデータ区分の先頭から所定個数Ｂ（Ｂ≦Ｎ１かつＢ≦Ｎ２）毎のデータ区分を先頭とする前記Ｌ個のデータ区分を、中間レジスタ３３Ａへ選択的にロードして格納する。中間レジスタ３３Ａに格納されるデータのデータ長（中間レジスタ３３Ａのサイズに対応する値）Ｌは、下記式（１１）によって与えられる。ここで、所定個数（入力・中間レジスタ間隔）Ｂは、中間レジスタ３３ＡのサイズＬを決定するパラメータで、図１０では、Ｂ＝４，Ｌ＝１２の例が示されている。
Ｌ＝Ｂ＋Ｎ１＋Ｎ２＋Offset%Ｂ−１    （１１）
ただし、Offset%Ｂは、Offsetの値をＢの値で除算して得られる余りである。
【００７９】
第２選択回路（第２ＭＵＸ木）３５Ａは、中間レジスタ３３Ａから出力レジスタ３２Ａへ、前記Ｌ個のデータ区分のうちの、前記Ｎ１個のデータ区分および前記Ｎ２個のデータ区分を前記Ｎ個のデータ区分を選択的にロードする。
【００８０】
図１０に示す例では、入力レジスタ３１Ａは、１６個のデータ区分をそれぞれ格納する入力レジスタ＃０〜＃１５を有している。また、中間レジスタ３３Ａは、第１選択回路３４Ａによって入力レジスタ３１ＡからロードされたＬ個のデータ区分をそれぞれ格納する中間レジスタ＃０〜＃１１を有している。さらに、出力レジスタ３２Ａは、第２選択回路３５Ａによって中間レジスタ３３ＡからロードされたＮ１＋Ｎ２個のデータ区分をそれぞれ格納する出力レジスタ＃０〜＃３，＃０′〜＃３′を有している。なお、出力レジスタ＃０〜＃３は前半の前記Ｎ１個のデータ区分を格納し、出力レジスタ＃０′〜＃３′は、後半の前記Ｎ２個のデータ区分を格納する。
【００８１】
そして、入力レジスタ３１Ａと中間レジスタ３３Ａとの間の第１段ＭＵＸ木３４Ａにおいて、中間レジスタ３３Ａの各バイト（各データ区分）は、入力レジスタ３１Ａ上でＢバイト間隔にＭＵＸ木を構成する。つまり、中間レジスタ＃０と４個の入力レジスタ＃０，＃４，＃８，＃１２との間にＭＵＸ木が形成され、中間レジスタ＃１と４個の入力レジスタ＃１，＃５，＃９，＃１３との間にＭＵＸ木が形成される。同様に、中間レジスタ＃２と４個の入力レジスタ＃２，＃６，＃１０，＃１４との間にＭＵＸ木が形成され、中間レジスタ＃３と４個の入力レジスタ＃３，＃７，＃１１，＃１５との間にＭＵＸ木が形成される。また、中間レジスタ＃４と３個の入力レジスタ＃４，＃８，＃１２との間にＭＵＸ木が形成され、中間レジスタ＃５と３個の入力レジスタ＃５，＃９，＃１３との間にＭＵＸ木が形成され、中間レジスタ＃６と３個の入力レジスタ＃６，＃１０，＃１４との間にＭＵＸ木が形成され、中間レジスタ＃７と３個の入力レジスタ＃７，＃１１，＃１５との間にＭＵＸ木が形成される。さらに、中間レジスタ＃８と２個の入力レジスタ＃８，＃１２との間にＭＵＸ木が形成され、中間レジスタ＃９と２個の入力レジスタ＃９，＃１３との間にＭＵＸ木が形成され、中間レジスタ＃１０と２個の入力レジスタ＃１０，＃１４との間にＭＵＸ木が形成され、中間レジスタ＃１１と２個の入力レジスタ＃１１，＃１５との間にＭＵＸ木が形成される。
【００８２】
さらに、中間レジスタ３３Ａと出力レジスタ３２Ａとの間の第２段ＭＵＸ木３５Ａにおいて、８つのＭＵＸ木が形成される。つまり、出力レジスタ＃０と５個の中間レジスタ＃０〜＃４との間にＭＵＸ木が形成され、出力レジスタ＃１と５個の中間レジスタ＃１〜＃５との間にＭＵＸ木が形成される。また、出力レジスタ＃２と５個の入力レジスタ＃２〜＃６との間にＭＵＸ木が形成され、出力レジスタ＃３と５個の入力レジスタ＃３〜＃７との間にＭＵＸ木が形成される。同様に、出力レジスタ＃０′と５個の中間レジスタ＃４〜＃８との間にＭＵＸ木が形成され、出力レジスタ＃１′と５個の中間レジスタ＃５〜＃９との間にＭＵＸ木が形成される。また、出力レジスタ＃２′と５個の入力レジスタ＃６〜＃１０との間にＭＵＸ木が形成され、出力レジスタ＃３′と５個の入力レジスタ＃７〜＃１１との間にＭＵＸ木が形成される。
【００８３】
図１０に示すマルチプレクサ回路３０Ａでは、前半の前記Ｎ１個のデータ区分について、第１段ＭＵＸ木３４Ａの機能により、中間レジスタ＃０〜＃６には、入力レジスタ３１Ａの下記４つの区間のいずれかにおけるデータが格納される。
［＃０〜＃６］，［＃４〜＃１０］，［＃８〜＃１４］，［＃１２〜＃１５］
【００８４】
また、図１０に示すマルチプレクサ回路３０Ａでは、後半の前記Ｎ２個のデータ区分について、第１段ＭＵＸ木３４Ａの機能により、中間レジスタ＃６〜＃１１には、入力レジスタ３１Ａの下記２つの区間のいずれかにおけるデータが格納される。
［＃６〜＃１１］，［＃１０〜＃１５］
【００８５】
そして、第２段ＭＵＸ木３５Ａの機能により、中間レジスタ３３Ａにおける２組の４バイト長データが、出力レジスタ３２Ａの前半側レジスタ＃０〜＃３および後半側レジスタ＃０′〜＃３′へ読み出される。
【００８６】
上述した第１段ＭＵＸ木３４Ａおよび第２段ＭＵＸ木３５Ａの機能により、出力レジスタ３２Ａに、入力レジスタ３１における任意オフセットからＮ１バイト長のデータと、当該Ｎ１バイト長のデータの後に所定間隔Offsetだけあけて続くＮ２バイト長のデータとを格納することができる。
【００８７】
なお、図１０では、入力レジスタ＃２〜＃５のデータ区分と入力レジスタ＃７〜＃１０のデータ区分とが、中間レジスタ３３Ａ経由で、それぞれ出力レジスタ＃０〜＃３および出力レジスタ＃０′〜＃３′へ出力される例が、太破線矢印および太実線矢印によって示されている。また、出力レジスタ＃０〜＃３と出力レジスタ＃０′〜＃３′とのそれぞれにロードされるＮ１個のデータ区分およびＮ２個のデータ区分は、第１段ＭＵＸ木３４Ａおよび第２段ＭＵＸ木３５Ａをなす各２：１−ＭＵＸへの制御信号Ｃ（図１参照）の値を切り換えることによって変更される。
【００８８】
第２実施形態では、図１０に示す構成のマルチプレクサ回路３０Ａにおいて選択回路３４Ａ，３５Ａの回路量を最小にする入力・中間レジスタ間隔Ｂの値を算出し、当該値Ｂに基づき選択回路３４Ａ，３５Ａを設計する方法および装置について説明する。ここで、入力レジスタ３１Ａのサイズに対応する値Ｍと、出力レジスタ３２Ａのサイズに対応する値Ｎと、配置間隔を表す定数Offsetとは、予め与えられているが、入力・中間レジスタ間隔Ｂの値、つまりは中間レジスタ３３Ａのサイズに対応する値Ｌ（＝Ｂ＋Ｎ１＋Ｎ２＋Offset%Ｂ−１）の値は、未定とする。
【００８９】
図１１に示すフローチャート（ステップＳ１１〜Ｓ１４）に従って、本発明の第２実施形態としてのマルチプレクサ回路３０Ａの設計手順について説明する。なお、当該設計手順も、図６を参照しながら前述したマルチプレクサ回路設計装置１の処理部（コンピュータ）１０によって実行される。
【００９０】
第２実施形態では、図１０に示す構成のマルチプレクサ回路３０Ａについて、入力レジスタ３１ＡのサイズＭと出力レジスタ３２ＡにロードされるデータのサイズＮ１およびＮ２と、前記定数Offsetとから、中間レジスタ３３Ａの最適なサイズＬが求められる。実際には、前述した通り、最適なサイズＬを決める入力・中間レジスタ間隔Ｂの最適な値が求められる。
【００９１】
このため、まず、入力レジスタ３１Ａのサイズ（入力バイト数）Ｍと、出力レジスタ３２にロードされるデータのサイズＮ１およびＮ２と、前記定数Offsetとが取得される（ステップＳ１１）。このとき、サイズＭ，Ｎ１，Ｎ２および定数Offsetは、予め記憶部２０（図６参照）に設定保存されているものを読み出して取得してもよいし、設計者等によってキーボード等の入力装置から入力されたものを受信して取得してもよい。
【００９２】
そして、入力バイト数Ｍ，出力バイト数Ｎ１，Ｎ２，定数Offsetおよび入力・中間レジスタ間隔Ｂを変数にとり、且つ、第１段ＭＵＸ木３４Ａおよび第２段ＭＵＸ木３５Ａの回路量を２：１−ＭＵＸの個数に換算する関数Ｔ（Ｍ，Ｎ１，Ｎ２，Offset，Ｂ）が、以下のように生成される（ステップＳ１２）。
【００９３】
第１段ＭＵＸ木３４Ａを実現しうる２：１−ＭＵＸの個数（第１段ＭＵＸ個数）は下記式（１２）によって算出される。
【００９４】
【数７】
2015154400.tif 000009
【００９５】
また、第２段ＭＵＸ木３５Ａを実現しうる２：１−ＭＵＸの個数（第２段ＭＵＸ個数）は下記式（１３）によって算出される。
第２段ＭＵＸ個数＝（Ｎ１＋Ｎ２）*（Ｂ−１）      （１３）
【００９６】
したがって、第１段ＭＵＸ木３４Ａおよび第２段ＭＵＸ木３５Ａの回路量を２：１−ＭＵＸの個数に換算する関数Ｔ（Ｍ，Ｎ１，Ｎ２，Offset，Ｂ）は、上記式（１２）と上記式（１３）とを加算することで、下記換算式（１４）として与えられる。
【００９７】
【数８】
2015154400.tif 000010
【００９８】
この後、上記換算式（１４）によって得られる値Ｔ（Ｍ，Ｎ１，Ｎ２，Offset，Ｂ）が最小になるＢの値が求められる（ステップＳ１３）。このとき、１≦Ｂ≦Ｎ１＋Ｎ２＋Offsetの範囲内の整数のうち、当該整数を上記回路量換算式（１４）に代入して得られる２：１−ＭＵＸの個数Ｔ（Ｍ，Ｎ１，Ｎ２，Offset，Ｂ）が最小になる整数が、Ｂの値として決定される。
【００９９】
ステップＳ１３で決定された入力・中間レジスタ間隔Ｂに基づき中間レジスタ３３ＡのサイズＬ＝Ｂ＋Ｎ１＋Ｎ２＋Offset%Ｂ−１が得られる。そして、得られた中間レジスタ３３ＡのサイズＬと、入力レジスタ３１ＡのサイズＭと、出力レジスタ３２ＡのサイズＮ１＋Ｎ２とを用いて、設計対象のマルチプレクサ回路３０Ａの生成が行なわれる（ステップＳ１４）。
【０１００】
図１１に示す設計手順でマルチプレクサ回路３０Ａの設計を行なうマルチプレクサ回路設計装置１は、図６に示した第１実施形態のマルチプレクサ回路設計装置１のハードウエア構成および機能構成と同様に構成される。そして、上述したステップＳ１１の処理は、第１実施形態と同様、取得部１１によって実行される。また、上述したステップＳ１２およびＳ１３の処理は、入力・中間レジスタ間隔計算部１２によって実行される。そして、上述したステップＳ１４の処理は、マルチプレクサ回路生成部１３によって実行される。
【０１０１】
第２実施形態によれば、第１実施形態と同様、大容量データを格納する入力レジスタ３１Ａと２組の部分データを保持する出力レジスタ３２Ａとの間に、レジスタ３１Ａ，３２Ａ間の回路量（２：１−ＭＵＸの個数に換算した値）を最小にするサイズＬの中間レジスタ３３Ａが配置される。これにより、回路量を大幅に削減したマルチプレクサ回路３０Ａが生成設計される。つまり、大容量データに対するランダムアクセス可能なマルチプレクサ回路３０Ａの回路量が大幅に削減される。特に、第２実施形態では、出力レジスタ３２Ａに、入力レジスタ３１における任意オフセットからＮ１バイト長のデータと、当該Ｎ１バイト長のデータの後に所定間隔Offsetだけあけて続くＮ２バイト長のデータとを格納することができる。
【０１０２】
〔４〕その他
以上、本発明の好ましい実施形態について詳述したが、本発明は、係る特定の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲内において、種々の変形、変更して実施することができる。
【０１０３】
なお、上述した実施形態では、一つのデータ区分のデータ幅が８ビット（１バイト）である場合について説明したが、本発明は、これに限定されるものではない。同様に、上述した実施形態では、Ｍ＝１６，Ｎ＝Ｎ１＝Ｎ２＝４，Offset＝１である場合について説明したが、本発明は、これらの数値に限定されるものではない。
【０１０４】
また、上述した実施形態では、本発明の技術を、入力レジスタ３１，３１Ａから出力レジスタ３２，３２Ａへのデータロードを行なうマルチプレクサ回路３０，３０Ａに適用した場合について説明した。これとは逆に出力レジスタ３２，３２Ａから入力レジスタ３１，３１Ａへのデータロードを行なう回路にも本発明の技術を適用することができ、この場合も、上述した実施形態と同様の作用効果を得ることができる。
【０１０５】
〔５〕付記
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
（付記１）
Ｍ（Ｍは２以上の整数）個のデータ区分を格納する第１レジスタから、任意のデータ区分を先頭とするＮ（ＮはＮ＜Ｍの整数）個のデータ区分を、第２レジスタへロードするマルチプレクサ回路であって、
前記第１レジスタと前記第２レジスタとの間において、前記Ｍ個のデータ区分のうちの、前記Ｎ個のデータ区分を含むＬ（ＬはＮ＜Ｌ＜Ｍの整数）個のデータ区分を、一時的に格納する中間レジスタと、
前記第１レジスタから前記中間レジスタへ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を選択的にロードする第１選択回路と、
前記中間レジスタから前記第２レジスタへ、前記Ｌ個のデータ区分のうちの前記Ｎ個のデータ区分を選択的にロードする第２選択回路と、を有し、
前記第１選択回路および前記第２選択回路は、前記ＭおよびＮの値に応じて算出された、前記第１選択回路および前記第２選択回路の回路量を最小にするＬの値に基づいて設計されている、マルチプレクサ回路。
【０１０６】
（付記２）
前記第１選択回路は、前記Ｍ個のデータ区分の先頭から所定個数Ｂ（Ｂ≦Ｎ）毎のデータ区分を先頭とする前記Ｌ（ただし、Ｌ＝Ｎ＋Ｂ−１）個のデータ区分を、前記中間レジスタへ選択的にロードして格納する、
付記１に記載のマルチプレクサ回路。
【０１０７】
（付記３）
前記第１選択回路および前記第２選択回路の回路量が、前記Ｍ，Ｎ，Ｂの値と下記回路量換算式とに基づいて、２個のデータ区分から１個のデータ区分を選択的に切り換えて出力する２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）によって換算され、
下記回路量換算式（１５）によって換算される前記２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）を最小にするＢの値が、下記式（１６）を満たす整数ｋまたはｋ＋１として決定されている、
付記２に記載のマルチプレクサ回路。
【０１０８】
【数９】
2015154400.tif 000011
【０１０９】
（付記４）
前記ｋおよび前記ｋ＋１のうち、前記ｋおよび前記ｋ＋１をそれぞれ上記回路量換算式（１５）に前記Ｂの値として代入して得られる前記２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）が小さくなる方が、前記２：１マルチプレクサの個数を最小にするＢの値として決定されている、
付記３に記載のマルチプレクサ回路。
【０１１０】
（付記５）
Ｍ（Ｍは２以上の整数）個のデータ区分を格納する第１レジスタから、任意の第１データ区分を先頭とするＮ１（Ｎ１はＮ１＜Ｍの整数）個のデータ区分、および、任意の第２データ区分を先頭とするＮ２（Ｎ２はＮ２＜Ｍの整数）個のデータ区分を、第２レジスタへロードするマルチプレクサ回路であって、
前記第１レジスタと前記第２レジスタとの間において、前記Ｍ個のデータ区分のうちの、前記Ｎ１個のデータ区分および前記Ｎ２個のデータ区分を含むＬ（ＬはＮ１＋Ｎ２＜Ｌ＜Ｍの整数）個のデータ区分を、一時的に格納する中間レジスタと、
前記第１レジスタから前記中間レジスタへ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を選択的にロードする第１選択回路と、
前記中間レジスタから前記第２レジスタへ、前記Ｌ個のデータ区分のうちの、前記Ｎ１個のデータ区分および前記Ｎ２個のデータ区分を選択的にロードする第２選択回路と、を有し、
前記第１選択回路および前記第２選択回路は、前記Ｍ，Ｎ１，Ｎ２の値に応じて算出された、前記第１選択回路および前記第２選択回路の回路量を最小にするＬの値に基づいて設計されている、マルチプレクサ回路。
【０１１１】
（付記６）
前記第１選択回路は、前記Ｍ個のデータ区分の先頭から所定個数Ｂ（Ｂ≦Ｎ１かつＢ≦Ｎ２）毎のデータ区分を先頭とする前記Ｌ（Ｌの値は下記式（１７）によって決定される）個のデータ区分を、前記中間レジスタへ選択的にロードして格納する、
付記４に記載のマルチプレクサ回路。
Ｌ＝Ｂ＋Ｎ１＋Ｎ２＋Offset%Ｂ−１    （１７）
ただし、Offsetは、前記Ｎ１個のデータ区分と前記Ｎ２個のデータ区分との、前記第１レジスタ上での配置間隔を表す定数（０≦Offset≦Ｍ−Ｎ１−Ｎ２）であり、Offset%Ｂは、Offsetの値をＢの値で除算して得られる余りである。
【０１１２】
（付記７）
前記第１選択回路および前記第２選択回路の回路量が、前記Ｍ，Ｎ１，Ｎ２，Offset，Ｂの値と下記回路量換算式（１８）とに基づいて、２個のデータ区分から１個のデータ区分を選択的に切り換えて出力する２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ１，Ｎ２，Offset，Ｂ）によって換算され、
下記回路量換算式（１８）によって換算される前記２：１マルチプレクサの個数を最小にする値Ｂが算出されている、
付記６に記載のマルチプレクサ回路。
【０１１３】
【数１０】
2015154400.tif 000012
【０１１４】
（付記８）
１≦Ｂ≦Ｎ１＋Ｎ２＋Offsetの範囲内の整数のうち、当該整数を上記回路量換算式（１８）に代入して得られる前記２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ１，Ｎ２，Offset，Ｂ）が最小になる整数が、Ｂの値として決定されている、
付記７に記載のマルチプレクサ回路。
【０１１５】
（付記９）
Ｍ（Ｍは２以上の整数）個のデータ区分を格納する第１レジスタから、任意のデータ区分を先頭とするＮ（ＮはＮ＜Ｍの整数）個のデータ区分を、第２レジスタへロードするマルチプレクサ回路であって、前記第１レジスタと前記第２レジスタとの間において、前記Ｍ個のデータ区分のうちの、前記Ｎ個のデータ区分を含むＬ（ＬはＮ＜Ｌ＜Ｍの整数）個のデータ区分を、一時的に格納する中間レジスタと、前記第１レジスタから前記中間レジスタへ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を選択的にロードする第１選択回路と、前記中間レジスタから前記第２レジスタへ、前記Ｌ個のデータ区分のうちの前記Ｎ個のデータ区分を選択的にロードする第２選択回路と、を有する前記マルチプレクサ回路を設計するコンピュータに、
前記ＭおよびＮの値を取得し、
前記第１選択回路および前記第２選択回路の回路量を最小にする前記Ｌの値を、前記ＭおよびＮの値に基づいて算出し、
前記第１選択回路および前記第２選択回路を、算出された前記Ｌの値に基づいて生成する、
処理を実行させる、マルチプレクサ回路の設計プログラム。
【０１１６】
（付記１０）
前記第１選択回路は、前記Ｍ個のデータ区分の先頭から所定個数Ｂ（Ｂ≦Ｎ）毎のデータ区分を先頭とする前記Ｌ（ただし、Ｌ＝Ｎ＋Ｂ−１）個のデータ区分を、前記中間レジスタへ選択的にロードして格納する、
付記９に記載のマルチプレクサ回路の設計プログラム。
【０１１７】
（付記１１）
前記第１選択回路および前記第２選択回路の回路量を、前記Ｍ，Ｎ，Ｂの値と下記回路量換算式（１９）とに基づいて、２個のデータ区分から１個のデータ区分を選択的に切り換えて出力する２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）によって換算し、
下記回路量換算式（１９）によって換算される前記２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）を最小にするＢの値を、下記式（２０）を満たす整数ｋまたはｋ＋１として決定する、
処理を前記コンピュータに実行させる、付記１０に記載のマルチプレクサ回路の設計プログラム。
【０１１８】
【数１１】
2015154400.tif 000013
【０１１９】
（付記１２）
前記ｋおよび前記ｋ＋１のうち、前記ｋおよび前記ｋ＋１をそれぞれ上記回路量換算式（１９）に前記Ｂの値として代入して得られる前記２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）が小さくなる方を、前記２：１マルチプレクサの個数を最小にするＢの値として決定する、
処理を前記コンピュータに実行させる、付記１１に記載のマルチプレクサ回路の設計プログラム。
【０１２０】
（付記１３）
Ｍ（Ｍは２以上の整数）個のデータ区分を格納する第１レジスタから、任意の第１データ区分を先頭とするＮ１（Ｎ１はＮ１＜Ｍの整数）個のデータ区分、および、任意の第２データ区分を先頭とするＮ２（Ｎ２はＮ２＜Ｍの整数）個のデータ区分を、第２レジスタへロードするマルチプレクサ回路であって、前記第１レジスタと前記第２レジスタとの間において、前記Ｍ個のデータ区分のうちの、前記Ｎ１個のデータ区分および前記Ｎ２個のデータ区分を含むＬ（ＬはＮ１＋Ｎ２＜Ｌ＜Ｍの整数）個のデータ区分を、一時的に格納する中間レジスタと、前記第１レジスタから前記中間レジスタへ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を選択的にロードする第１選択回路と、前記中間レジスタから前記第２レジスタへ、前記Ｌ個のデータ区分のうちの、前記Ｎ１個のデータ区分および前記Ｎ２個のデータ区分を選択的にロードする第２選択回路と、を有する前記マルチプレクサ回路を設計するコンピュータに、
前記Ｍ，Ｎ１，Ｎ２の値を取得し、
前記第１選択回路および前記第２選択回路の回路量を最小にする前記Ｌの値を、前記Ｍ，Ｎ１，Ｎ２の値に基づいて算出し、
前記第１選択回路および前記第２選択回路を、算出された前記Ｌの値に基づいて生成する、
処理を実行させる、マルチプレクサ回路の設計プログラム。
【０１２１】
（付記１４）
前記第１選択回路は、前記Ｍ個のデータ区分の先頭から所定個数Ｂ（Ｂ≦Ｎ１かつＢ≦Ｎ２）毎のデータ区分を先頭とする前記Ｌ（Ｌの値は下記式（２１）によって算出される）個のデータ区分を、前記中間レジスタへ選択的にロードして格納する、
付記１３に記載のマルチプレクサ回路の設計プログラム。
Ｌ＝Ｂ＋Ｎ１＋Ｎ２＋Offset%Ｂ−１    （２１）
ただし、Offsetは、前記Ｎ１個のデータ区分と前記Ｎ２個のデータ区分との、前記第１レジスタ上での配置間隔を表す定数（０≦Offset≦Ｍ−Ｎ１−Ｎ２）であり、Offset%Ｂは、Offsetの値をＢの値で除算して得られる余りである。
【０１２２】
（付記１５）
前記第１選択回路および前記第２選択回路の回路量を、前記Ｍ，Ｎ１，Ｎ２，Offset，Ｂの値と下記回路量換算式（２２）とに基づいて、２個のデータ区分から１個のデータ区分を選択的に切り換えて出力する２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ１，Ｎ２，Offset，Ｂ）によって換算し、
下記回路量換算式（２２）によって換算される前記２：１マルチプレクサの個数を最小にする値Ｂを算出する、
処理を前記コンピュータに実行させる、付記１４に記載のマルチプレクサ回路の設計プログラム。
【０１２３】
【数１２】
2015154400.tif 000014
【０１２４】
（付記１６）
１≦Ｂ≦Ｎ１＋Ｎ２＋Offsetの範囲内の整数のうち、当該整数を上記回路量換算式（２２）に代入して得られる前記２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ１，Ｎ２，Offset，Ｂ）が最小になる整数を、Ｂの値として決定する、
処理を前期コンピュータに実行させる、付記７に記載のマルチプレクサ回路の設計プログラム。
【０１２５】
（付記１７）
Ｍ（Ｍは２以上の整数）個のデータ区分を格納する第１レジスタから、任意のデータ区分を先頭とするＮ（ＮはＮ＜Ｍの整数）個のデータ区分を、第２レジスタへロードするマルチプレクサ回路であって、前記第１レジスタと前記第２レジスタとの間において、前記Ｍ個のデータ区分のうちの、前記Ｎ個のデータ区分を含むＬ（ＬはＮ＜Ｌ＜Ｍの整数）個のデータ区分を、一時的に格納する中間レジスタと、前記第１レジスタから前記中間レジスタへ、前記Ｍ個のデータ区分のうちの前記Ｌ個のデータ区分を選択的にロードする第１選択回路と、前記中間レジスタから前記第２レジスタへ、前記Ｌ個のデータ区分のうちの前記Ｎ個のデータ区分を選択的にロードする第２選択回路と、を有する前記マルチプレクサ回路を設計する装置であって、
前記ＭおよびＮの値を取得する取得部と、
前記第１選択回路および前記第２選択回路の回路量を最小にする前記Ｌの値を、前記ＭおよびＮの値に基づいて算出する算出部と、
前記第１選択回路および前記第２選択回路を、前記算出部によって算出された前記Ｌの値に基づいて生成する生成部と、有する、マルチプレクサ回路の設計装置。
【０１２６】
（付記１８）
前記第１選択回路は、前記Ｍ個のデータ区分の先頭から所定個数Ｂ（Ｂ≦Ｎ）毎のデータ区分を先頭とする前記Ｌ（ただし、Ｌ＝Ｎ＋Ｂ−１）個のデータ区分を、前記中間レジスタへ選択的にロードして格納する、
付記１７に記載のマルチプレクサ回路の設計装置。
【０１２７】
（付記１９）
前記算出部は、
前記第１選択回路および前記第２選択回路の回路量を、前記Ｍ，Ｎ，Ｂの値と下記回路量換算式とに基づいて、２個のデータ区分から１個のデータ区分を選択的に切り換えて出力する２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）によって換算し、
下記回路量換算式（２３）によって換算される前記２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）を最小にするＢの値を、下記式（２４）を満たす整数ｋまたはｋ＋１として決定する、
付記１８に記載のマルチプレクサ回路の設計装置。
【０１２８】
【数１３】
2015154400.tif 000015
【０１２９】
（付記２０）
前記算出部は、前記ｋおよび前記ｋ＋１のうち、前記ｋおよび前記ｋ＋１をそれぞれ上記回路量換算式（２３）に前記Ｂの値として代入して得られる前記２：１マルチプレクサの個数Ｔ（Ｍ，Ｎ，Ｂ）が小さくなる方を、前記２：１マルチプレクサの個数を最小にするＢの値として決定する、
付記１９に記載のマルチプレクサ回路の設計装置。
【符号の説明】
【０１３０】
１    マルチプレクサ回路設計装置
１０    処理部（ＣＰＵ，コンピュータ）
１１    取得部
１２    入力・中間レジスタ間隔計算部（算出部）
１３    マルチプレクサ回路生成部（生成部）
２０    記憶部（メモリ）
３０，３０Ａ    マルチプレクサ回路
３１，３１Ａ    入力レジスタ（第１レジスタ）
３２，３２Ａ    出力レジスタ（第２レジスタ）
３３，３３Ａ    中間レジスタ
３４，３４Ａ    第１段ＭＵＸ木（第１選択回路）
３４ａ〜３４ｇ    ＭＵＸ木
３５，３５Ａ    第２段ＭＵＸ木（第２選択回路）
３５ａ〜３５ｄ，３６ａ〜３６ｄ    ＭＵＸ木
【図１】
2015154400.tif 000017
【図２】
2015154400.tif 000018
【図３】
2015154400.tif 000019
【図４】
2015154400.tif 000020
【図５】
2015154400.tif 000021
【図６】
2015154400.tif 000022
【図７】
2015154400.tif 000023
【図８】
2015154400.tif 000024
【図９】
2015154400.tif 000025
【図１０】
2015154400.tif 000026
【図１１】
2015154400.tif 000027
【図１２】
2015154400.tif 000028
【図１３】
2015154400.tif 000029