(57)【特許請求の範囲】
【請求項１】
コンパイラが、シングルスレッドソフトウェアアプリケーションを特定用途向けスーパーコンピュータへ自動的に変換するための方法であって、
ａ．前記コンパイラが、前記シングルスレッドソフトウェアアプリケーションからのコードフラグメントを前記特定用途向けスーパーコンピュータのカスタマイズされたハードウェアへと自動的に変換するステップであって、前記ハードウェアの実行が前記コードフラグメントのソフトウェア実行に機能的に相当するステップと、
ｂ．前記コンパイラが、前記シングルスレッドソフトウェアアプリケーションのハードウェア部分およびソフトウェア部分にインタフェースを生成するステップであって、前記インタフェースが、ランタイムに、
ｉ．前記コードフラグメントへの入口でソフトウェア−ハードウェアプログラム状態転送を行い、
ｉｉ．前記コードフラグメントからの出口でハードウェア−ソフトウェアプログラム状態転送を行い、
ｉｉｉ．前記シングルスレッドソフトウェアアプリケーションのソフトウェアメモリとハードウェアのメモリとの間のメモリコヒーレンスを維持する、ステップと、
ｃ．前記コンパイラが、ステップａ及びｂにおいて得た前記特定用途向けスーパーコンピュータの前記カスタマイズされたハードウエアを複数のモジュールに分割するステップと、
を備える方法。
【請求項２】
ａ．前記コンパイラが、前記コードフラグメントの領域階層内のリーフ領域をハードウェア有限状態機械へと自動的に変換するステップと、
ｂ．前記コンパイラが、前記リーフ領域のための前記ハードウェア有限状態機械の少なくとも１つのコピーを形成して、前記ハードウェア有限状態機械の前記少なくとも１つのコピーと通信のためのネットワークとを組み合わせ、それにより、組み合わされた前記ハードウェア有限状態機械の前記少なくとも１つのコピーと前記通信のためのネットワークとが、前記リーフ領域の機能を実行するためのパイプラインプリミティブオペレーションとして振る舞うようにするステップと、
を更に備える請求項１に記載の方法。
【請求項３】
前記コンパイラが、請求項２の方法を前記コードフラグメントの前記領域階層に対して再帰的に適用し、それにより、前記コードフラグメントの前記ソフトウェア実行において親領域が子領域を呼び出すそれぞれのポイントで、前記コードフラグメントのハードウェアの実行において前記親領域のための前記ハードウェア有限状態機械が前記子領域のための前記パイプラインプリミティブオペレーションを始めるようにするステップを更に備える請求項２に記載の方法。
【請求項４】
前記コードフラグメントの前記ソフトウェア実行においてメモリ命令インスタンスＩ２がメモリ命令インスタンスＩ１に依存している場合に、前記コードフラグメントの前記ハードウェアの実行において前記メモリ命令インスタンスＩ２が前記メモリ命令インスタンスＩ１の後に実行されるようにするために、前記コンパイラが、カスタマイズされたハードウェア同期化ユニットを形成するステップを更に備える請求項３に記載の方法。
【請求項５】
ａ．並列にアクセスされる複数のロード／ストアポートをサポートする、および、
ｂ．前記同期化ユニットをサポートするために、前記複数のロード／ストアポートの各ロード／ストアポートから出される各メモリ命令の完了を信号で送る、
コヒーレントメモリ階層を前記コンパイラが形成するステップを更に備える請求項４に記載の方法。
【請求項６】
コンパイラが、複数のコンポーネントと前記複数のコンポーネントを接続する複数のネットワークとを備える特定用途向けスーパーコンピュータのハードウェア構造を複数のモジュールへと分割するための方法であって、
ａ．前記コンパイラが、クロスモジュール通信を可能にするスケーラブルネットワークを形成するステップと、
ｂ．前記コンパイラが、前記特定用途向けスーパーコンピュータの前記ハードウェア構造を複数のモジュールへと分割し、それにより、前記複数のコンポーネントの各コンポーネントが前記複数のモジュールの特定のモジュール内へ配置されるようにするステップと、
ｃ．前記コンパイラが、クロスモジュール通信を可能にするために、Ｉ／Ｏコントローラを前記複数のモジュールの各モジュール内に配置するステップと、
ｄ．前記複数のモジュールの各モジュールにおいて、
前記モジュール内に配置される少なくとも１つの前記コンポーネントに当初から取り付けられる各ネットワークｘのために、
前記コンパイラが、前記ネットワークｘに専用のローカルＩ／Ｏコントローラのポートに接続されるとともに前記ネットワークｘに当初から接続されるローカルコンポーネントにも接続される前記ネットワークｘのローカルサブネットワークを形成するステップと、
ｅ．ｉ．メッセージソースモジュールにおいて、メッセージソースコンポーネントにより前記ネットワークｘの前記ローカルサブネットワークを介して前記メッセージソースモジュールのローカルＩ／Ｏコントローラへメッセージを送る、
ｉｉ．前記メッセージソースモジュールの前記ローカルＩ／Ｏコントローラによって、前記メッセージを、前記メッセージソースモジュール外へ送り、前記メッセージがメッセージ送り先モジュールに達するまで、クロスモジュール通信を可能にするために前記スケーラブルネットワーク内で前記メッセージをルーティングする、及び、
ｉｉｉ．前記メッセージを、前記ネットワークｘのローカルサブネットワークを介して、前記メッセージ送り先モジュールのローカルＩ／Ｏコントローラによって受け入れるとともに前記メッセージ送り先モジュール内のメッセージ送り先コンポーネントへ配信する、
ことにより、各ネットワークｘのために、前記コンパイラの手段により、あたかも前記特定用途向けスーパーコンピュータの前記ハードウェア構造が分割されなかったかのように、前記ネットワークｘ上の任意のコンポーネントから同じ前記ネットワークｘ上の任意の他のコンポーネントへのメッセージの配信を可能にするステップと、
を備える方法。
【請求項７】
前記コンパイラが、前記特定用途向けスーパーコンピュータの前記ハードウェア構造の前記分割により生成される複数のモジュールのいずれかを実現できる統合モジュールを形成するステップを更に備える請求項６に記載の方法。
【請求項８】
請求項５の方法を用いてシングルスレッドソフトウェアアプリケーションから得られる特定用途向けスーパーコンピュータ。
【請求項９】
ａ．前記コンパイラが、クロスモジュール通信を可能にするスケーラブルネットワークを形成するステップと、
ｂ．前記コンパイラが、前記特定用途向けスーパーコンピュータのハードウェア構造を複数のモジュールへと分割し、それにより、複数のコンポーネントの各コンポーネントが前記複数のモジュールの特定のモジュール内へ配置されるようにするステップと、
ｃ．前記コンパイラが、クロスモジュール通信を可能にするために、Ｉ／Ｏコントローラを前記複数のモジュールの各モジュール内に配置するステップと、
ｄ．前記複数のモジュールの各モジュールにおいて、
前記モジュール内に配置される少なくとも１つの前記コンポーネントに当初から取り付けられる各ネットワークｘのために、
前記コンパイラが、前記ネットワークｘに専用のローカルＩ／Ｏコントローラのポートに接続されるとともに前記ネットワークｘに当初から接続されるローカルコンポーネントにも接続される前記ネットワークｘのローカルサブネットワークを形成するステップと、
ｅ．ｉ．メッセージソースモジュールにおいて、メッセージソースコンポーネントにより前記ネットワークｘの前記ローカルサブネットワークを介して前記メッセージソースモジュールのローカルＩ／Ｏコントローラへメッセージを送る、
ｉｉ．前記メッセージソースモジュールの前記ローカルＩ／Ｏコントローラによって、前記メッセージを、前記メッセージソースモジュール外へ送り、前記メッセージがメッセージ送り先モジュールに達するまで、クロスモジュール通信を可能にするために前記スケーラブルネットワーク内で前記メッセージをルーティングする、及び、
ｉｉｉ．前記メッセージを、前記ネットワークｘのローカルサブネットワークを介して、前記メッセージ送り先モジュールのローカルＩ／Ｏコントローラによって受け入れるとともに前記メッセージ送り先モジュール内のメッセージ送り先コンポーネントへ配信する、
ことにより、前記コンパイラの手段によって、各ネットワークｘのために、あたかも前記特定用途向けスーパーコンピュータの前記ハードウェア構造が分割されなかったかのように、前記ネットワークｘ上の任意のコンポーネントから同じ前記ネットワークｘ上の任意の他のコンポーネントへのメッセージの配信を可能にするステップと、
により、
前記コンパイラが、前記複数のコンポーネントと前記複数のコンポーネントを接続する複数のネットワークとを備える特定用途向けスーパーコンピュータの前記ハードウェア構造を複数のモジュールへと分割するステップを更に備える、請求項５に記載の方法。
【請求項１０】
前記コンパイラが、前記特定用途向けスーパーコンピュータの前記ハードウェア構造の前記分割により生成される複数のモジュールのいずれかを実現できる統合モジュールを形成するステップを更に備える請求項９に記載の方法。
【請求項１１】
請求項１０の方法を用いてシングルスレッドソフトウェアアプリケーションから得られる特定用途向けスーパーコンピュータ。
【請求項１２】
そのハードウェアの実行がシングルスレッドソフトウェアアプリケーション内のコードフラグメントのソフトウェア実行に機能的に相当する特定用途向けスーパーコンピュータであって、
ａ．前記コードフラグメントの領域階層から導かれる階層ソフトウェアパイプラインを実装するパイプラインプリミティブオペレーションの１又は複数の階層レベルと、
ｂ．前記コードフラグメントの前記ソフトウェア実行においてメモリ命令インスタンスＩ２がメモリ命令インスタンスＩ１に依存している場合に、前記コードフラグメントの前記ハードウェアの実行において前記メモリ命令インスタンスＩ２が前記メモリ命令インスタンスＩ１の後に実行されるようにするための、少なくとも１つのカスタマイズされたハードウェア同期ユニットと、
ｃ．ｉ．並列にアクセスされる複数のロード／ストアポートをサポートし、
ｉｉ．同期化ユニットをサポートするために、前記複数のロード／ストアポートの各ロード／ストアポートから出される各メモリ命令の完了を信号で送る、
少なくとも１つのコヒーレントメモリ階層と、
を備え、
スケーラブルネットワーク接続とともにＡＳＩＣテクノロジーで実装された統合モジュールの複数のコピーとして実装され、
ＡＳＩＣテクノロジーで実装された前記統合モジュールは、前記特定用途向けスーパーコンピュータのハードウェア構造を分割した結果生じる複数のモジュールのいずれかの機能を実行可能である、
特定用途向けスーパーコンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
引用される文献：
共に継続し、共に所有される関連米国特許：
非仮出願番号１３／１５６，８８１
米国特許一覧：
７，１１１，２７４  Ｂ１
７，３１５，９９１  Ｂ１
７，４０９，６７０  Ｂ１
７，２１９，３４２  Ｂ２
７，７６１，６８７  Ｂ２
７，５７７，８２２  Ｂ２
２００８／０１２０４９７
２００９／０００６７６９
５，７６１，５１５
６，０３１，９９２
５，５４２，０７５
５，３８６，５６２
他の文献一覧
[1]M.V. Wilkes, J.B. Stringer, 1953. Microprogramming and the design of the control circuits in an electronic digital computer. Proc. Cambridge Phil. Soc., pt. 2, vol. 49, pp. 230-238, April, 1953.  http://research.microsoft.com/en-us/um/people/gbell/computer_structures_principles_and_examples/csp0174.htm 
[2]Joseph A. Fisher, 1979. Optimization of horizontal microcode within and beyond basic blocks. An application of processor scheduling with resources. Courant Mathematics and Computing Laboratory. Department of Energy report COO-1077-161. October 1979.  http://www.archive.org/stream/optimizationofho00fish 
[3]P.P. Chang, S.A. Mahlke, W.Y. Chen, N.J. Warter,  and W.W. Hwu,  "IMPACT: An Architectural Framework for Multiple-Instruction-Issue Processors",  in Proc. ISCA, 1991, pp.266-275. 
[4]Scott A. Mahlke, David C. Lin, William Y. Chen, Richard E. Hank, Roger A. Bringmann. Effective compiler support for predicated execution using the hyperblock. In Proceedings of MICRO'1992. pp.45~54 
[5]M. Budiu, G. Venkataramani, T. Chelcea,  and S.C. Goldstein,  "Spatial computation",  in Proc. ASPLOS, 2004, pp.14-26.  
[6]G.S. Sohi, S.E. Breach,  and T.N. Vijaykumar,  "Multiscalar Processors",  in Proc. ISCA, 1995, pp.414-425.
[7]K. Ebcioglu. A Compilation Technique for Software Pipelining of Loops with Conditional Jumps. Proc. 20th Workshop on Microprogramming, pp. 69-79, ACM Press, December 1987.
[8]K. Ebcioglu. Some Design Ideas for a VLIW Architecture for Sequential Natured Software. Parallel Processing (Proc. IFIP WG 10.3 Working Conference on Parallel Processing), M. Cosnard, M.H. Barton, M. Vanneschi (eds.), pp. 3-21, North Holland, 1988. http://global-supercomputing.com/people/kemal.ebcioglu/pdf/Ebcioglu-IFIP88.pdf
[9]K. Ebcioglu and R. Groves, Some Global Compiler Optimizations and Architectural Features for Improving Performance of Superscalars, Research Report no. RC16145, IBM T.J. Watson Research Center, Yorktown Heights, NY, 1990. (Presented at the ICCD-1990 conference). http://global-supercomputing.com/people/kemal.ebcioglu/pdf/RC16145.pdf 
[10]S.M. Moon, K. Ebcioglu. Parallelizing Non-Numerical Code with Selective Scheduling and Software Pipelining. ACM Transactions on Programming Languages and Systems, November 1997, Vol. 19, No. 6, pp. pp. 853-898, ACM Press.
[11]K. Ebcioglu and T. Nakatani, A New Compilation Technique for Parallelizing Loops with Unpredictable Branches on a VLIW Architecture. In Languages and Compilers for Parallel Computing, D. Gelernter, A. Nicolau, and D. Padua (eds.), Research Monographs in Parallel and Distributed Computing, pp. 213-229, MIT Press, 1990.
[12]Joao M. P. Cardoso, Pedro C. Diniz. Compilation Techniques for Reconfigurable Architectures. Springer, 2008. 223 p.
[13]R.M. Tomasulo. An Efficient Algorithm for Exploiting Multiple Arithmetic Units, IBM Journal of Research and Development, 11(1):25-33, January 1967
[14]K. Sankaralingam, R. Nagarajan, P. Gratz, R. Desikan, D. Gulati, H. Hanson, C. Kim, H. Liu, N. Ranganathan, S. Sethumadhavan, S. Sharif, P. Shivakumar, W. Yoder, R. McDonald, S.W. Keckler, and D.C. Burger. "The Distributed Microarchitecture of the TRIPS Prototype Processor," 39th International Symposium on Microarchitecture (MICRO), December, 2006.
[15]Keith D. Cooper and John Lu. Register Promotion in C Programs. Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation (PLDI-97), 1997,  pp. 308-319,  ACM Press.
[16]Kevin B. Theobald, Guang R. Gao, and Laurie Hendren. On the limits of program parallelism and its smoothability. Proc. MICRO-25, 1992, pp. 10-19.
[17]K. Ebcioglu, E.R. Altman, S. Sathaye, and M. Gschwind. Optimizations and Oracle Parallelism with Dynamic Translation. Proc. MICRO-32, Haifa, Israel, December 1999. 
[18]Lawrence Livermore National Labs POSIX threads tutorial. https://computing.llnl.gov/tutorials/pthreads/ 
[19]C-to-HDL. Wikipedia article. http://en.wikipedia.org/wiki/C_to_HDL
[20]David J. Kuck. The structure of computers and computations. Wiley, 1978. 511 p.
[21]D.A. Padua, D.J. Kuck,  and D.H. Lawrie,  "High-Speed Multiprocessors and Compilation Techniques", IEEE Trans. Computers, 1980, pp.763-776. 
[22]Milind Girkar and Constantine D. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs. IEEE transactions on parallel and distributed systems, Vol. 3, No. 2, March 1992, pp. 166-178.
[23]E. Dijkstra. Cooperating Sequential Processes. 1965. EWD 123. http://www.cs.utexas.edu/~EWD/transcriptions/EWD01xx/EWD123.html
[24]G. Lee, C.P. Kruskal,  and D.J. Kuck,  "The Effectiveness of Automatic Restructuring on Nonnumerical Programs",  in Proc. ICPP, 1985, pp.607-613.
[25]Frances Allen, Michael Burke, Ron Cytron, Jeanne Ferrante, Wilson Shieh, Vivek Sarkar, A framework for  determining useful parallelism. Proc. Second International Conference on Supercomputing, ICS 88, ACM, New York. Pp. 207-215.
[26]J. Ferrante, K. Ottenstein, and K. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems. Pp. 319-349. July 1987.
[27]J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero. Swing Modulo Scheduling: a lifetime-sensitive approach. Proc. PACT '96. 
[28]Wikipedia. Prefix Sum article. http://en.wikipedia.org/wiki/Prefix_sum
[29]Wikipedia. Loop Splitting article. http://en.wikipedia.org/wiki/Loop_splitting 
[30]Wikipedia. Hypergraph article. http://en.wikipedia.org/wiki/Hypergraph 
[31]Engin Demir, Cevdet Aykanat, B. Barla Cambazoglu. Clustering spatial networks for aggregate query processing: A hypergraph approach. Information Systems 33 (2008) 1-17. http://www.cs.bilkent.edu.tr/~aykanat/papers/08IS.pdf 
[32]High Performance Fortran Forum. High Performance Fortran Language Specification.  Version 2.0. January 31, 1997. http://hpff.rice.edu/versions/hpf2/hpf-v20.pdf 
[33]Emre Ozer, Sanjeev Banerjia, Thomas M. Conte. Unified assign and schedule: A new approach to scheduling for clustered register file architectures. MICRO 1998, pp. 308-315
[34]Krishnan Kailas, Kemal Ebcioglu, Ashok Agrawala: A New Code Generation Framework for Clustered ILP Processors. Proc. Seventh International Symposium on High Performance Computer Architecture (HPCA-7), pp. 133-143, Monterrey, Mexico, January 2001.
[35]Wikipedia, Dominator article.  http://en.wikipedia.org/wiki/Dominator_(graph_theory)
[36]Judea Pearl. Asymptotic properties of minimax trees and game-searching procedures. Artificial Intelligence, 14 (2), pages 113-138, September 1980.
[37]Bradley C. Kuszmaul, Synchronized MIMD computing, PhD thesis, MIT, May 1994.
[38]J. M. Borkenhagen, R. J. Eickemeyer, R. N. Kalla, and S. R. Kunkel. 2000. A multithreaded PowerPC processor for commercial servers. IBM J. Res. Dev. 44, 6 (November 2000), 885-898.
[39]Supercomputing Technologies Group.  Cilk 5.4.6 Reference Manual. Supercomputing Technologies Group. MIT Laboratory for Computer Science. Copyright 1998, MIT. http://supertech.lcs.mit.edu/cilk
[40]G.M. Silberman and K. Ebcioglu, An Architectural Framework for Supporting Heterogeneous Instruction-Set Architectures. IEEE Computer, Vol. 26, No. 6, June 1993, pp. 39-56.
[41]K. Ebcioglu and E. Altman. DAISY: Dynamic VLIW Compilation for 100% Architectural Compatibility, Research Report RC20538, IBM T.J. Watson Research Center, Yorktown Heights, August 1996. 82 p.  http://global-supercomputing.com/people/kemal.ebcioglu/pdf/RC20538.pdf 
[42]K. Ebcioglu and E. Altman. DAISY: Dynamic VLIW Compilation for 100% Architectural Compatibility, pp. 26-37, Proc. International Symposium on Computer Architecture (ISCA) 1997, ACM press.
[43]V.H. Allan, B. Su, P. Wijaya,  and J. Wang,  "Foresighted Instruction Scheduling Under Timing Constraints",  IEEE Trans. Computers, 1992, pp.1169-1172. 
[44]A.D. Kshemkalyani, M. Singhal, Distributed Computing: Principles, Algorithms, and Systems, ISBN: 9780521189842, paperback edition, Cambridge University Press, March 2011. 756 pages.
[45]Silicon Graphics Inc. Origin(tm) and Onyx2(tm) Theory of Operations Manual. Document Number 007-3439-002. Copyright 1997 Silicon Graphics Inc. 108 p. http://www.futuretech.blinkenlights.nl/origin/007-3439-002.pdf 
[46]MESI Protocol. Article in Wikipedia. http://en.wikipedia.org/wiki/MESI_protocol
【背景技術】
【０００２】
［０００１］
本発明は、シングルスレッドソフトウェアプログラムの特定用途向けスーパーコンピュータへの変換に関する。
［０００２］
書き込み並列プログラムの困難性
幾つかの理由により、シーケンシャルアプリケーションよりも並列アプリケーションを書き込むことの方がかなり困難である。第１に、アプリケーションにおいて利用できる並列度を特定するには、アプリケーションにおける命令文とこれらの命令文を並列に実行するセマンティク効果との間の全ての想定し得る相互作用の完全な理解を要する。また、並列に実行するアプリケーションの部分を特定するだけでは十分でなく、並列プログラミング構成概念を使用してアプリケーションを書き換えるという問題もある。アプリケーションの並列バージョンが得られた後でさえ、この新たなバージョンがシーケンシャルバージョンと同じように振る舞うことを検証する必要がある。また、生成された並列アプリケーションが実際にシーケンシャルアプリケーションと全く同じセマンティクスを有することを検証することも困難な作業である。マニュアル並列プログラミングにおけるこれらの困難性は、コンパイラ技術の進歩と共に、シーケンシャルアプリケーションの自動並列化の考えをもたらしてきた。
【０００３】
［００１０］
「スーパーコンピュータ」は、時として、不正確なマーケティング用語として使用されるため、この用語をそれが本明細書中で使用される文脈において正確に規定することが望ましい。本明細書および添付の特許請求の範囲において使用されるように、本発明者らは、かなりの並列度を成し且つ少なくとも１つのチップを備えるハードウェアシステムを意味するようにスーパーコンピュータという用語を規定し、この場合、システム内のチップは、ネットワークにより相互接続されるとともに、階層的に編成されるエンクロージャ内に配置される。
・幾つかのラックを伴い、各ラックが幾つかのボード／ラックモジュールを含み、各ボード／ラックモジュールがスケーラブルネットワークにより全てが相互接続される幾つかのチップを含む、マシンルーム内を満たす大型ハードウェアシステムは、スーパーコンピュータの１つの特定の例である。そのような大型ハードウェアシステムの単一ラックは、スーパーコンピュータの他の例である。かなりの並列度を成し且つ幾つかのハードウェアコンポーネントを含む単一チップも同様にスーパーコンピュータであると考えられ得る。これは、特徴サイズが将来的に減少するにつれて、単一チップに組み込まれ得るハードウェアの量も増大し続けると思われるからである。
【０００４】
［００２３］
本発明は、（ｉ）シングルスレッドソフトウェアプログラムを特定用途向けスーパーコンピュータへ自動的に変換するためのコンパイレーション方法と、（ｉｉ）この方法を適用する結果として生成されるスーパーコンピュータシステム構造とを備える。コンパイレーション方法は、
ａ．アプリケーションからの任意のコードフラグメントをカスタマイズされたハードウェアへと変換するステップであって、ハードウェアの実行がコードフラグメントのソフトウェア実行に機能的に相当するステップと、
ｂ．アプリケーションのハードウェア部分およびソフトウェア部分にインタフェースを生成するステップであって、インタフェースが、
ｉ．コードフラグメントの入口でソフトウェア−ハードウェアプログラム状態転送を行う、
ｉｉ．コードフラグメントの出口でハードウェア−ソフトウェアプログラム状態転送を行う、
ｉｉｉ．ソフトウェアメモリとハードウェアメモリとの間のメモリコヒーレンスを維持する、
ステップと、を備える。
方法の重要な段階が以下に要約される。
【図面の簡単な説明】
【０００５】
【図１】チップレベルのスーパーコンピュータシステム階層を示す。
【図２】ラックモジュールレベルのスーパーコンピュータシステム階層を示す。
【図３】ラックレベルのスーパーコンピュータシステム階層を示す。
【図４】全システムレベルのスーパーコンピュータシステム階層を示す。
【図５】１つのチップ内のコンポーネント、ネットワーク、および、外部通信デバイスを示す。また、マスターポートおよびスレーブポートも示す。
【図６】標準的な８入力８出力バタフライサブネットワーク（従来技術）を示す。
【図７】本発明により使用される不完全バタフライサブネットワークの一例を示す。
【図８】１次元トーラスとして編成されるタスクサブネットワークを示す。
【図９】２次元トーラスとして編成されるタスクサブネットワークを示す。
【図１０】送信ＦＩＦＯインタフェースおよび受信ＦＩＦＯインタフェースを示す。
【図１１】静止検出回路のビルディングブロックを示す。
【図１２】内側ループの複数のインスタンスを生じさせる外側ループのための静止検出回路を示す。
【図１３】スーパーコンピュータ内のカスタムネットワークのリクエストパケットフォーマットを示す。
【図１４】スーパーコンピュータ内のカスタムネットワークのレスポンスパケットフォーマットを示す。
【図１５】階層的ソフトウェアパイプライニング構想の一例を示す。
【図１６】コヒーレントプライベートＬ１キャッシュを伴うメモリ階層例を示す。
【図１７】照会のローカル性が低いアプリケーションに適した、Ｌ１キャッシュを伴わずバンクインターリーブＬ２キャッシュを伴うメモリ階層例を示す。
【図１８】起動例として示されるランダムアクセスＣプログラムを与える。
【図１９】分割前のランダムアクセスのための完全フラット構造を示す。
【図２０】ホストアクセラレータ通信プロトコルを記載する。
【図２１】ランダムアクセス内側ループのためのシーケンシャルな中間コードおよびＣコードを与える。
【図２２】エンハンスドパイプラインスケジューリング（ＥＰＳ）段階１の後のランダムアクセス内側ループを示す。
【図２３】エンハンスドパイプラインスケジューリング（ＥＰＳ）段階２の後のランダムアクセス内側ループを示す。
【図２４】エンハンスドパイプラインスケジューリング（ＥＰＳ）段階３（最終段階）の後のランダムアクセス内側ループを示す。
【図２５】条件付き実行を伴うランダムアクセス内側ループ最終ツリーＶＬＩＷを示す。
【図２６】ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール１／７部分（モジュールのＩ／Ｏピン）を示す。
【図２７】ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール２／７部分（レジスタ宣言）を示す。
【図２８】ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール３／７部分（有限状態機械）を示す。
【図２９】ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール４／７部分（継続有限状態機械）を示す。
【図３０】ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール５／７部分（継続有限状態機械）を示す。
【図３１】ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール６／７部分（有限状態機械、組み合わせＦＩＦＯハンドシェーキング出力）を示す。
【図３２】ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール７／７部分（メモリおよび親ループネットワークのための静止検出回路）を示す。
【図３３】ランダムアクセス内の分割０／２を示す。
【図３４】ランダムアクセス内の分割１／２を示す。
【図３５】ランダムアクセス内の分割２／２を示す。
【図３６】分割されたランダムアクセス例に適用されるチップ統合の結果を示す。
【図３７】ランダムアクセス統合チップ内のグローバルコンポーネント−ローカルコンポーネントマップを与える。
【図３８】ランダムアクセス統合チップ内で使用されるべきルーティングテーブルを与える。
【図３９】書き込み更新キャッシュコヒーレンスプロトコルに基づくレジスタプロモーションにおける一例を示す。
【図４０】階層的メモリ分割のためのコード例を示す。
【図４１】コード例におけるメモリアドレス空間階層を示す。
【図４２】プライベートコヒーレントキャッシュを伴うメモリノード実装を示す。
【図４３】共有バンクインターリーブキャッシュを伴うメモリノード実装を示す。
【図４４】共有バンクインターリーブキャッシュ（外部データアレイ）を伴うメモリノード実装を示す。
【図４５】メモリ階層例の実施を示す。
【図４６】列車衝突危険防止回路のパート１／２を示す。
【図４７】列車衝突危険防止回路のパート２／２を示す。
【図４８】シリアライゼーション回路のパート１／２を示す。
【図４９】シリアライゼーション回路のパート２／２を示す。
【図５０】ダイナミックスレッド連続番号を使用するプログラム例を示す。
【図５１】ダイナミックスレッド連続番号を使用するプログラム例のハードウェア実装を示す。
【図５２】エラトステネスの篩プログラムを示す。
【図５３】エラトステネスの篩プログラムのハードウェア実装を示す。
【図５４】バブルソートプログラムを示す。
【図５５】列車衝突同期化のみを伴うバブルソートのハードウェア実装を示す。
【図５６】カスケード型フィルタを用いて実施されるべきバブルソートアルゴリズムを示す。
【図５７】カスケード型フィルタを伴うバブルソートの実装を示す。
【図５８】Ｆ機能とＧ機能とを１つにまとめる前のリソース共有例を示す。
【図５９】Ｆ機能とＧ機能とを１つにまとめた後のリソース共有例を示す。
【図６０】コンパイラに適した汎用スーパーコンピュータのためのフラット構造。
【図６１】コンパイラに適した汎用スーパーコンピュータのための統合チップ。
【図６２】再帰的Ｎ−クイーンを伴うプログラム例を示す。
【図６３】再帰的Ｎ−クイーンのハードウェア実装を示す。
【図６４】アルファ−ベータ枝刈りのための再帰的シーケンシャルアルゴリズム。
【図６５】アルファ−ベータ枝刈りのハードウェア実装。
【図６６】ディーププロファイラのステップを示す。
【図６７】ハードウェアソフトウェア分割のための部分的なインライニングプロセスを示す。
【図６８】ハードウェアソフトウェア分割アルゴリズムを示す。
【図６９】記号実行のためのアルゴリズムを示す。
【図７０】記号実行が行われるコード例を示す。
【図７１】依存性解析アルゴリズムを示す。
【発明を実施するための形態】
【０００６】
［００２９］
本発明者らは、シングルスレッドソフトウェアプログラムを特定用途向けスーパーコンピュータへ自動的に変換するための方法の詳細を正に説明しようとしており、方法は、
ａ．アプリケーションからの任意のコードフラグメントをカスタマイズされたハードウェアへと変換するステップであって、ハードウェアの実行がコードフラグメントのソフトウェア実行に機能的に相当するステップと、
ｂ．アプリケーションのハードウェア部分およびソフトウェア部分にインタフェースを生成するステップであって、インタフェースが、
ｉ．コードフラグメントの入口でソフトウェア−ハードウェアプログラム状態転送を行う、
ｉｉ．コードフラグメントの出口でハードウェア−ソフトウェアプログラム状態転送を行う、
ｉｉｉ．ソフトウェアメモリとハードウェアメモリとの間のメモリコヒーレンスを維持する、
ステップと、を備える。
また、本発明者らは、方法によって生み出される特定用途向けスーパーコンピュータシステムについても詳しく説明する。任意のシングルスレッドソフトウェアを特定用途向けスーパーコンピュータにコンパイルする分野は新しいため、本発明者らは、この文書において多くの詳細な内容を与えている。
【０００７】
［００３０］
好ましい実施形態は、以下のように、４つの主要な部分で編成される。
１．カスタマイズされたスーパーコンピュータハードウェアの構造：本発明者らは、以下を含む本発明者らのベースライン特定用途向けスーパーコンピュータアーキテクチャを構造レベルで説明する。
〇全スーパーコンピュータシステム、
〇１９インチラック、
〇ラック内の１９インチボード／モジュール、
〇モジュール上のＦＰＧＡ／ＡＳＩＣチップ、
〇チップ内のそれぞれの種類のハードウェアユニットのピンアウト・内部作業（インターナル・オペレーション）、
・不完全バタフライサブネットワーク、
・タスクサブネットワーク、
・静止検出回路、
・カスタマイズされたスレッドユニット、
・データキャッシュユニットおよびメモリ階層、
・クロスチップ通信のためのＩ／Ｏコントローラおよび不完全ハイパーキューブネットワーク、
・ホストプロセッサ−アクセラレータ通信のためのＰＣＩ  Ｅｘｐｒｅｓｓインタフェース、
〇ホストプロセッサ通信インタフェース、
また、本発明者らは、シーケンシャルプログラムのカスタマイズされたスレッドユニットが入力として与えられるとコンポーネントをトップレベルでインスタンス化して接続するアルゴリズムについても説明する。これは、シーケンシャルプログラムのためのカスタマイズされたハードウェア階層のトップレベルの構造設計を完了する。
２．カスタマイズされたハードウェアスレッドユニットへのシーケンシャルコードのコンパイリング：本発明者らは、次に、カスタマイズされたパイプラインスレッドユニットを所定のプログラムから形成するためのアルゴリズムについて説明する。
〇本発明者らは、並列度の基本的な正確さ規則、すなわち、シーケンシャルプログラムの並列ハードウェアバージョンが満たすべきシーケンシャルプログラム内のプログラム依存性を与える。
〇本発明者らは、その後、並列ハードウェア実行が全てのプログラムの依存性を満たし且つ同じシーケンシャルプログラムのソフトウェア実行の機能的に１００％適合する置き換えであるように、前述したパラダイム内でシーケンシャルプログラムから特定用途向けスーパーコンピュータを形成するための階層的ソフトウェアパイプライニング、すなわち、コンパイレーション技術について説明する。
〇本発明者らは、任意のシーケンシャルソフトウェアプログラム内の階層領域から、レジスタ転送レベルでスーパーコンピュータハードウェアのカスタマイズされたパイプラインスレッドユニットを得るためのコンパイラ技術について説明する。
先のトップレベル構造設計アルゴリズムと共に、これは、ベースライン特定用途向けスーパーコンピュータ設計およびそのコンパイレーションの説明を完了する。しかしながら、この構造は非常に大きすぎて単一チップ上に適合できない。
３．大型構造の分割（パーティション）：単一チップ上に適合しない構造を取り扱うために、本発明者らは、
〇大型構造を複数のチップへ分割する、および、
〇最終的に、ハードウェアを構築する際に、ＡＳＩＣマスク費用などの開発費の低減を達成するために、構造の分割（パーティション）のうちのいずれか１つを実現できる「統合」チップを形成する、ための技術について説明する。
これは、シーケンシャルプログラムをベースライン特定用途向けスーパーコンピュータへ変換するための全てのステップを完了する。
４．最適化：本発明者らは、その後、ベースライン特定用途向けスーパーコンピュータシステムおよび関連するコンパイレーション技術の多くの最適化および更なる用途について説明する。
カスタマイズされたスーパーコンピュータハードウェアの構造。
スーパーコンピュータシステムアーキテクチャ。
【０００８】
［００３１］
この文書中の方法を適用する結果として、特に用途のニーズにしたがって構成されるスーパーコンピュータシステムが構築される。スーパーコンピュータシステム階層は、葉から根元まで、
ｉ．論理チップ（ＦＰＧＡまたはＡＳＩＣ）およびＤＲＡＭユニット（例えば、デュアルインラインメモリモジュール内に編成される、ＤＤＲｎ標準規格に従うＤＲＡＭメモリチップ）と、
ｉｉ．１９インチラックモジュールと、
ｉｉｉ．１９インチラックと、
ｉｖ．完全スーパーコンピュータシステムと、から成る。
本発明者らは、ここでは、高性能計算を達成することに関連する重要なハードウェアモジュールのみについて説明しており、それを機能させるためのシステムの一部であるべき通常の既知の構成要素（コンポーネント）、例えば電源については説明しない。
【０００９】
［００３２］
図１を参照すると、ＦＰＧＡチップまたはＡＳＩＣチップの内側では、スレッドユニットと呼ばれる有限状態機械（１０１）内で主要な計算が行われる。タスク・同期化ネットワーク（１０２）は、有限状態機械を接続するとともに、スレッドを送って作業（オペレーション）を正しい順序で実行するために使用される。多層分割オンチップキャッシュ階層（１０３，１０４）がメモリネットワーク（１０５，１０６）を使用してアクセスされる。オフチップメモリは、メモリコントローラ（１０７）とオフチップメモリネットワーク（１０８）とを使用してアクセスされる。Ｉ／Ｏコントローラ（１０８）は、構造が単一の論理チップに適合しないときにはクロスチップ通信のために使用される。
【００１０】
［００３３］
図２を参照すると、ラックモジュール内には、メインアクセラレータメモリを構成する１つ以上のＤＲＡＭユニット（２０２）に接続される複数のＦＰＧＡチップまたはＡＳＩＣチップ（２０１）が存在する。各ＦＰＧＡ／ＡＳＩＣチップは、差動高速信号送信（２０３）を伴うボード上のワイドバスを使用してその隣接するＦＰＧＡ／ＡＳＩＣチップに接続される。また、各ＦＰＧＡ／ＡＳＩＣチップは、少なくとも１つの高速シリアル通信ケーブルに接続される。
【００１１】
［００３４］
図３および図４を参照すると、ラックにおけるラックモジュール間では、全システムを通じたラックにわたって、高速シリアル光ケーブルまたは銅ケーブル（３０１，４０１）が、拡張可能な場合により不完全なハイパーキューブネットワーク１（１本発明者らは、この文書では、提示を簡単にするために、不完全なハイパーキューブネットワークのみに焦点を合わせるが、単一のＦＰＧＡチップまたはＡＳＩＣチップは、大型スーパーコンピュータのためのハイパーキューブネットワークを形成できる十分な通信リンクを有さなくてもよい。この場合、キューブ接続サイクル技術が解決策を与える。ラックモジュール上のＦＰＧＡ／ＡＳＩＣチップの小さいグループは、各グループの外部リンクの総数が単一チップと比べて増大されるように、単一のハイパーキューブノードとして作用できる。例えば、グループがラックモジュール上にチップＡ，Ｂ，Ｃ，Ｄを含み、内部差動ワイドバスがＡ，Ｂ，Ｃ，Ｄをトーラス編成で接続するものとする。ラックモジュールを外部に接続する１２個のシリアル通信ケーブルが存在するものとする。ラックモジュール上のチップＡはシリアル通信ケーブル０，１，２に接続し、チップＢはケーブル３，４，５に接続し、チップＣは６，７，８に接続し、また、チップＤは９，１０，１１に接続する。その結果、ラックモジュールを構成するグループ全体｛Ａ，Ｂ，Ｃ，Ｄ｝は、最大で２１２＝４０９６個のラックモジュール（１６３８４個のＦＰＧＡ／ＡＳＩＣチップ）を伴って、スーパーコンピュータシステム内にハイパーキューブノードを形成できる。チップＡがメッセージをグループ｛Ａ，Ｂ，Ｃ，Ｄ｝のリンク４で送信するために、メッセージは、最初に、オンボード差動ワイドバス接続によってチップＢへと経路付けられなければならない。チップＡへ向かうことになっているリンク４でグループ｛Ａ，Ｂ，Ｃ，Ｄ｝へ達する（すなわち、Ｂに達する）メッセージも、最初に、グループ｛Ａ，Ｂ，Ｃ，Ｄ｝内で内的に正しい送り先チップ（Ａ）へ経路付けられなければならない。無論、他のサイズの並列スーパーコンピュータシステムも同様に想定し得る。）を実現するために使用される。アクセラレータのＦＰＧＡ／ＡＳＩＣチップのうちの１つは、ＰＣＩ−Ｅｘｐｒｅｓｓ接続（４０２）によってホストシステムに接続される。ホストシステムは、アプリケーションのソフトウェア部分が実行されるホストマイクロプロセッサ（４０３）と、アクセラレータ上のメモリとコヒーレントに維持される１つ又はそれ以上のホストメモリＤＲＡＭユニット（４０４）から成るメモリとを備える。ホストシステムは、ラックのうちの１つのラック上の別個の１９インチモジュールであってもよく、または、スーパーコンピュータの１９インチモジュールのうちの１つと一体であってもよい。
【００１２】
［００３５］
ハイパーキューブネットワークは、ノードの数が任意の数となり得て必ずしも２の累乗とは限らないという意味において、場合により不完全である。
【００１３】
［００３６］
この文書の方法によってもたらされるスーパーコンピュータは、ホストユニプロセッサに取り付けられるコプロセッサ／アクセラレータとして作用する。スーパーコンピュータは、ハードウェア−ソフトウェア分割アルゴリズムを使用して、アプリケーション内の１つ以上のプログラムフラグメントをハードウェアにマッピングすることにより、このホストユニプロセッサで起動するシーケンシャルシングルスレッドアプリケーションの実行を加速するために使用される。スーパーコンピュータハードウェアは、それが置き換えるソフトウェアコードフラグメントに機能的に１００％適合する。
各システムチップ内のコンポーネント、ネットワーク、および、通信デバイス：
【００１４】
［００３７］
図５を参照すると、システム内の各ＦＰＧＡチップまたはＡＳＩＣチップは、コンポーネント、ネットワーク、および、外部通信デバイスと呼ばれるハードウェアモジュールから成る。これらは、チップ機能を成すためにそこにあるべき通常の回路に加えた、計算モジュール、例えばチップ内の様々なクロックを駆動させるためのフェーズロックドループである。
【００１５】
［００３８］
コンポーネントは、場合によりメモリも含む任意同期デジタル回路を含むとともに、その送信ＦＩＦＯインタフェースおよび受信ＦＩＦＯインタフェースを介してメッセージと通信する。コンポーネントの例としては、
・以下を繰り返して行うことによって、特定の内側ループまたは外側ループ或いはプログラムのｂｅｇｉｎ−ｅｎｄブロックを実行するための最適化された有限状態機械であるスレッドユニット。
〇新たなタスクリクエスト（ループ起動）がその親ループから到達するのを待つ。
〇タスクに取り組む（場合により、メモリロード／ストアリクエストをデータキャッシュユニットへ送信し、或いは別個のスレッドユニットで実施される更なるタスクリクエストをその内側ループへ送信する）。
〇結果（タスクレスポンス）が必要とされる場合には、タスクのレスポンスをリクエスタへ送り戻す。
・新たなロードまたはストアリクエストを受け入れる（依存関係が許容するときにはサイクルごとに）、ロードまたはストアを実行する、必要に応じてラインミスおよびラインフラッシュを処理する、および、ロードデータまたはストアの肯定応答をレスポンスとして送り戻すパイプラインデータキャッシュ。
・サイクルごとに被除数および除数を受けて、その後の所定数のサイクルごとに商および余りを戻すパイプライン整数除算ユニット。
・クロスチップメッセージトラフィックを方向付けるためのＩ／Ｏコントローラが挙げられる。
【００１６】
［００３９］
サブネットワークは、１つ以上の入力（幾つかのコンポーネントの送信ＦＩＦＯに接続される）から１つ以上の出力（幾つかのコンポーネントの受信ＦＩＦＯに接続される）へとメッセージを経路付けるための非常に簡単な高周波ルータである。サブネットワークの例としては、基本高周波から形成される不完全なバタフライサブネットワーク、２入力２出力コアクロスバースイッチ（ここでサブネットワークの特にアドレス指定された出力ポートへメッセージが送られる）、または、タスクサブネットワーク（メッセージを自由に受け入れることができる、すなわち、その受信ｆｉｆｏが一杯でない、任意のサブネットワーク出力ポートへ入力メッセージを送る）が挙げられる。図８および図９を参照すると、良好なロードバランシングのため、タスクネットワークは、１次元、２次元、または、それ以上の次元のトーラスとして実施することができ、それにより、タスクは、それらが自由なスレッドユニットを見出すまで、ネットワーク内で循環する。タスクサブネットワークのビルディングブロックは、１つのサイクル内で左から右への順序で要求する入力（そのＦＩＦＯが空でない入力）を利用可能な出力（そのＦＩＦＯが一杯でない出力）に効率的に接続するタスククロスバースイッチである。
【００１７】
［００４０］
不完全なバタフライサブネットワークは、ネットワークの入力および出力の数が２の累乗である必要がない、すなわち、それらの数が任意の数となり得るという意味において不完全である。標準的な８入力８出力バタフライサブネットワークは、図６の従来技術への言及のために与えられる。しかしながら、図７を参照すると、この文書により使用される５入力３出力不完全バタフライサブネットワークは、不必要なグラフエッジおよびグラフノードを下層の伝統的な８入力８出力完全バタフライサブネットワークから削除することによって得られる。
ネットワークは通常は２つのサブネットワークから形成され、一方のサブネットワークはリクエストを順方向で送るためのものであり、他方のサブネットワークはレスポンスを逆方向で受けるためのものである。
【００１８】
［００４１］
外部通信デバイスは、チップの外側のＰＣＩ  Ｅｘｐｒｅｓｓレーンに接続されるＰＣＩ  Ｅｘｐｒｅｓｓ  ＩＰコアから成ってもよい。または、外部通信デバイスは、不完全ハイパーキューブネットワーク内で高速双方向シリアル通信リンクの一端を実装する高速光または銅シリアル通信ＩＰコアであってもよい。または、外部通信デバイスは、２つの隣接するＦＰＧＡ／ＡＳＩＣチップを接続する差動信号送信を伴うボード上の高帯域幅高速ワイドバスに接続されるＩＰコアであってもよい。または、外部通信デバイスは、隣接するダイナミックメモリユニットに接続されるＤＤＲｎメモリコントローラＩＰコアであってもよい。全ての通信デバイスは、チップの内側に面する１つの送信ＦＩＦＯと１つの受信ＦＩＦＯとを有する。外部通信デバイスの一部はおそらく生産者固有のＩＰコアであるが、コンポーネントおよびネットワークは、スクラッチからコンパイラによって形成される、或いは、専門のエンジニアにより設計される（コンパイラが出荷される前に１回設計される。システムのユーザに要求される手作業のハードウェア設計作業は存在しない）再使用可能／パラメータ化可能なＶｅｒｉｌｏｇモジュールのライブラリからコンパイラによってインスタンス化される、レジスタ転送レベルで設計される技術非依存型ユニットからのみ構成される。コンポーネントおよびネットワークのＲＴＬ記述は、想定し得る範囲で生産者プラットフォームにわたって移動できる。
【００１９】
［００４２］
コンポーネント（またはネットワーク）の送信ＦＩＦＯインタフェース（すなわち、一群のピン）は、他のネットワーク（またはコンポーネント）の受信ＦＩＦＯインタフェースにポイントツーポイントで取り付く。コンポーネントは、常に、他のコンポーネントと通信するためにネットワークを通過する。この重要な特性のおかげで、所定のネットワークに接続される多くのコンポーネントをＩ／Ｏコントローラ（クロスチップ通信のためのコンポーネントである）を介して複数のチップにわたって広げることによって、任意の大きな構造を分割することができる。
【００２０】
［００４３］
外部通信デバイスは、コンポーネントと同様に、チップの内側に面するそれらの信号上でネットワークにも接続する。チップの外側に面するそれらの信号は、例えばボード上のＰＣＩ  Ｅｘｐｒｅｓｓレーンに接続することによって外部通信機能を果たすべく使用される。
【００２１】
［００４４］
特別なケースとして、そのエンドポイントコンポーネントが同じチップ上にある単一入力、単一出力ネットワークを最終的な分割およびチップ統合段階の後のネットワーク削除最適化によって削除することができ（すなわち、配線接続に置き換えることができ）、それにより、１つのコンポーネントの送信ＦＩＦＯ配線が他のコンポーネントの受信ＦＩＦＯ配線に直接に接続できる。
【００２２】
［００４５］
コンポーネント、ネットワーク、および、通信デバイスに共通の名前、すなわち、ユニットを与えることとする。
【００２３】
［００４６］
全てのコンポーネントおよびネットワークは同じシステムクロックによって起動し、また、全てのユニットは１つの共通のリセット信号を共有する。それらの後側および前側のために異なるクロックを使用する内部ＦＩＦＯのおかげで、外部通信デバイスのためのＩＰコアは、それが異なる固有周波数を有するときに、システムの残りの部分とは異なるクロック速度により起動してもよいが、チップの内側に面するその送信ＦＩＦＯインタフェースおよび受信ＦＩＦＯインタフェースは共通のシステムクロックを使用する。
【００２４】
［００４７］
図１０を参照すると、本発明者らは、ここで、明確にするためにＦＩＦＯインタフェースを特定する。ここに、１つのユニットの送信ＦＩＦＯ  Ｉ／Ｏピンセットのための信号インタフェースを示す。
・ｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔ：出力、１ビット／／このユニットの送信ｆｉｆｏは空でない。
・ｏｕｔｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅ：入力、１ビット／／他のユニットの受信ｆｉｆｏは一杯でない。
・ｏｕｔｐｕｔ＿ｑｕｉｅｓｃｅｄ：随意入力、１ビット／／ここで根付いたスパニングサブツリーが静止した。
・ｏｕｔｐｕｔ＿ｐａｙｌｏａｄ：出力、Ｎビット／／他のユニットへ送信されるべきデータ。
【００２５】
［００４８］
ｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔおよびｏｕｔｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅのいずれも所定のサイクルで１であるときには、次の立ち上がりクロックエッジで、出力ペイロードが、このユニットの送信ｆｉｆｏの前から除去されて、接続されたユニットの受信ｆｉｆｏの後に配置される。全ての立ち上がりクロックエッジで転送が行われ、その間、ｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔおよびｏｕｔｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅはいずれも１のままである。ｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔおよびｏｕｔｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅのうちの少なくとも一方が所定のサイクルで０のときには、次の立ち上がりクロックエッジで転送が行われない。
【００２６】
［００４９］
ｏｕｔｐｕｔ＿ｑｕｉｅｓｃｅｄは、このＦＩＦＯインタフェースに接続される一群のユニットがアクティビティを有さないことを示す随意的な信号（静止検出回路上にある特定のＦＩＦＯインタフェースにのみ存在する）である。静止検出回路はネットワークでもコンポーネントでもなく、その代り、それらの静止検出回路は、スパニングツリー２（ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ．／ｗｉｋｉ／Ｓｐａｎｎｉｎｇ＿ｔｒｅｅ）の形態を成す接続によって、そのアクティビティが監視されているネットワークおよびコンポーネントを通り抜ける小さいゲート・フリップフロップ回路である。十分な数のバックツーバックサイクルにおいてｏｕｔｐｕｔ＿ｑｕｉｅｓｃｅｄ信号が１のときには、指定された一群のユニットが静止した、すなわち、全てのアクティビティを停止したことが推測される。静止検出については段落［００７４］付近で更に説明する。
【００２７】
［００５０］
再び図１０を参照すると、ここには、１つのユニットの受信ＦＩＦＯ  Ｉ／Ｏピンセットのための信号インタフェースがある。ピンは、他のユニットの送信ＦＩＦＯインタフェースにおける対応するピンにポイントツーポイントで取り付く。
・ｉｎｐｕｔ＿ｒｅｑｕｅｓｔ：入力、１ビット／／他のユニットの送信ｆｉｆｏは空でない。
・ｉｎｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅ：出力、１ビット／／このユニットの受信ｆｉｆｏは一杯でない。
・ｉｎｐｕｔ＿ｑｕｉｅｓｃｅｄ：随意出力、１ビット／／ここで根付いたスパニングサブツリーが静止した。
・ｉｎｐｕｔ＿ｐａｙｌｏａｄ：入力、Ｎビット／／受信されるべきデータ。
【００２８】
［００５１］
ｉｎｐｕｔ＿ｒｅｑｕｅｓｔおよびｉｎｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅのいずれも所定のサイクルで１であるときには、次の立ち上がりクロックエッジで、入力ペイロードが、他のユニットの送信ｆｉｆｏの前から除去されて、このユニットの受信ｆｉｆｏの後に配置される。全ての立ち上がりクロックエッジで転送が行われ、その間、ｉｎｐｕｔ＿ｒｅｑｕｅｓｔおよびｉｎｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅはいずれも１のままである。ｉｎｐｕｔ＿ｒｅｑｕｅｓｔおよびｉｎｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅのうちの少なくとも一方が所定のサイクルで０のときには、次の立ち上がりクロックエッジで転送が行われない。
【００２９】
［００５２］
ｉｎｐｕｔ＿ｑｕｉｅｓｃｅｄは、このＦＩＦＯインタフェースに接続される一群のユニットが全てのアクティビティを停止したことを示す随意的な出力信号（静止検出回路上にある特定のＦＩＦＯインタフェースにのみ存在する）である。ｏｕｔｐｕｔ＿ｑｕｉｅｓｃｅｄの説明の場合と同様、十分な数のバックツーバックサイクルにおいてこの信号が１であるときには、指定された一群のユニットが全てのアクティビティを停止したことが推測され得る。
【００３０】
［００５３］
Ｎ、すなわち、ペイロードビットの数は、ネットワークのリクエストペイロードサイズまたはネットワークのレスポンスペイロードサイズである。それぞれがＮ−１ビット長のマルチワード可変長メッセージをネットワークが使用するときには、可変長メッセージの最後のパケットを示すためにペイロードの最上位ビット（エンドオブデータビットまたはｅｏｄビットと呼ばれる）がリザーブされる。エンドオブデータビットは、マルチワードメッセージの最後のワードを除く全てにおいて０であるが、最後のワードでは、エンドオブデータビットが１である。ペイロードビットは、一般に、オペコード、アドレス、および、メモリオペレーションのための或いはメモリリードオペレーションにより戻されるデータのための或いはループ起動のレジスタ入力のための或いはループ起動のレジスタ結果のための書き込みデータフィールドから成る。
【００３１】
［００５４］
コンポーネントの送信ＦＩＦＯおよび受信ＦＩＦＯは、しばしば、スレーブポートまたはマスターポートと呼ばれる一対のＦＩＦＯとして働く。マスターポートは、ＦＩＦＯのその対の送信ＦＩＦＯからリクエストを送るとともに、その対の受信ＦＩＦＯでレスポンスを受ける。スレーブポートは、ＦＩＦＯのその対の受信ＦＩＦＯでリクエストを受けるとともに、その対の送信ＦＩＦＯからレスポンスを送り戻す。１つ以上のマスターポートと１つ以上のスレーブポートとを有するネットワークは、以下の一対のサブネットワークとして実施される。
・任意のマスターポートの送信ＦＩＦＯから任意のスレーブポートの受信ＦＩＦＯへリクエストを送る順方向サブネットワーク。このサブネットワークは、ループを呼び出すときにはタスクネットワークであり、それ以外のときには不完全バタフライネットワークである。
・任意のスレーブポートの送信ＦＩＦＯから任意のマスターポートの受信ＦＩＦＯへレスポンスを送る逆方向サブネットワーク。このサブネットワークは不完全バタフライネットワークである。
【００３２】
［００５５］
例えば、コンポーネントＡおよびコンポーネントＢが同じネットワークＹに接続されると仮定する。Ａ（例えば、ループＬ０のためのカスタマイズされたスレッドユニット）がリクエストメッセージ（内側ループ起動のレジスタパラメータなど）をＢ（例えば、Ｌ０の内側ループＬ１のためのスレッドユニット）へ送る必要があり、また、ＡがネットワークＹを介してＢからレスポンス（内側ループＬ１の結果）を受けるものとする。一連のイベントを以下に示す。
・ネットワークＹ上のコンポーネントＡのマスターポートがその送信ＦＩＦＯからリクエストを送る。
・リクエストは、Ｙの順方向サブネットワークを介して、Ｂのスレーブポートの受信ＦＩＦＯに達する。
・Ｂは、リクエストを受け入れて、所定のリクエストパラメータのためのレスポンスを用意する。
・Ｂは、そのスレーブポートの送信ＦＩＦＯから、Ｙの逆方向サブネットワークを介して、コンポーネントＡのマスターポートの受信ＦＩＦＯへレスポンスを送り戻す。
【００３３】
［００５６］
ネットワークのリクエストおよびレスポンスのペイロードのビット幅は一般に異なってもよい。
【００３４】
［００５７］
リクエストルーティング：ペイロードボディの第１のワード内のｌｏｇ２（スレーブポートの番号）ビット（ネットワークに応じて、コンパイル時定数ビット位置にある）はスレーブポート番号を示す。例えば、バンクインターリーブキャッシュが実装されたメモリにおいて、これらのビットは、アドレス内のバンク選択ビットである。タスクリクエストは送り先スレーブポートフィールドを必要とせず、それらのタスクリクエストをビジー状態でない（その受信ＦＩＦＯが一杯でない）スレッドユニットの任意のスレーブポートへ送ることができる。ネットワークが１つのスレーブポートのみを有するときには、送り先スレーブポート番号も必要とされない。
【００３５】
［００５８］
マルチワードメッセージを送る際には、第１のワードのみが、スレーブポート番号、マスターポート番号、および、タグを含む。すなわち、残りのワードを必要に応じてペイロードにより利用できる。
【００３６】
［００５９］
レスポンスルーティング：リクエストメッセージのペイロード部分は、ペイロードボディに加えて、２つの初期フィールド、すなわち、マスターポート番号またはリクエスタｉｄ（リクエストを送るネットワークのマスターポートの番号を特定する）、および、これがいずれの未解決リクエストであるのかを特定する番号を伴うタグをその最下位部分に含む。タグは、例えばマスターポートの送信ＦＩＦＯからタグ０を伴う第１のリクエストを送った後にタグ１を伴う第２のリクエストを送ることによって、第１のリクエストのためのレスポンスが戻ってくるのを待つことなく、複数の未解決リクエスト（レスポンスが受けられなかったリクエスト）がシステム内に共存できるようにする。また、スレーブポートは、入ってくるリクエストメッセージをそれが受け入れる際に、マスターポート番号およびタグを思い出し、レスポンスの準備ができているときにそのレスポンスの最下位ビットにこれらのフィールドを加える。マスターポート番号により、レスポンスメッセージは、逆方向不完全バタフライサブネットワーク内のリクエスタマスターポートへ戻るその方法を見出すことができる。その後、入ってくるレスポンスのタグは、これがいずれの未解決レスポンスであるのかを特定するためにリクエスタコンポーネントで使用される。レスポンスは、一般的に、バラバラの順序で戻り得る（例えば、所定のマスターポートからのリクエスト０がバンク０を使用するキャッシュに見当たらないときにはバンクインターリーブキャッシュ内、および、同じマスターポートからの以後のリクエスト１はバンク３を使用するキャッシュでヒットする）。
【００３７】
［００６０］
慣例により、ＰＣＩ  ＥｘｐｒｅｓｓまたはＤＤＲｎコントローラまたはチップツーチップシリアルまたはパラレル通信デバイスなどの外部通信デバイスは、チップの内側に面するスレーブポートを有するように規定される。
【００３８】
［００６１］
なお、ネットワークへの並列アクセスが有利であるときにはコンポーネントが同じネットワークへの複数のマスターポート接続を有してもよいことに留意されたい。コンパイラまたはライブラリモジュールの設計エンジニアは、ネットワークのための内部マスターポート番号からコンポーネントが送受信するためのＶｅｒｉｌｏｇコード（Ｖｅｒｉｌｏｇモジュールのピン名）を形成する。コンポーネントのインスタンスがトップレベルでインスタンス化されるときには、内部マスターポートがコンポーネントの外側の実ネットワークマスターポートに接続される。例えば、スレッドユニットコンポーネントは、ネットワークｎへの接続を目的とする内部マスターポート０，１を有してもよい。スレッドユニットの２つのコピーがトップレベルでインスタンス化されてもよく、それにより、ネットワークｎのための第１のスレッドユニットの内部マスターポート０，１が実ネットワークｎのマスターポート０，１にそれぞれ接続されるとともに、ネットワークｎのための第２のスレッドユニットの内部マスターポート０，１が実ネットワークｎのマスターポート２，３にそれぞれ接続される。同様に、コンポーネントは、同じネットワークへの複数のスレーブポートを有してもよく、これらのスレーブポートは、そのネットワークのための内部スレーブポート番号としてコンポーネント内で特定される。
【００３９】
［００６２］
図１３および図１４は、スーパーコンピュータの１つのチップ内の様々なカスタマイズされたネットワークのリクエストパケットフォーマットおよびレスポンスパケットフォーマットをそれぞれそれらの最も一般的な形態で示す。なお、特定用途向けのスーパーコンピュータにおけるカスタマイズされたネットワークは、既存の汎用ネットワークまたはオンチップネットワークとは異なる。すなわち、それらのカスタマイズされたネットワークは、リクエスト／レスポンスの１つのクラスのみ（例えば、ロードのみ、ストアのみ、整数除算／余りのみ、Ｌ１キャッシュミスのみ）を実現するようにカスタマイズされる。この文書のネットワークは、それらの高度に分化した性質および効率的なハードウェア実装により、ディープパイプラインされたＬ１キャッシュからのロードと同じくらい重大な機能のために使用され得る。
【００４０】
［００６３］
ネットワークパケットフォーマットに関する想定し得るカスタム最適化は以下を含む。
・メッセージがマルチワードフォーマットを成していなければ、エンドオブデータ（Ｅｏｄ）ビットが使用されず、その結果、メッセージは単一ペイロードワードから成る。
・時として、コンポーネントＡのマスターポートとコンポーネントＢのスレーブポートとの間の通信は双方向である必要がない。例えば、外側ループが内側ループを呼び出すが、外側ループが内側ループからのレジスタ結果を何ら必要としないときには、通信が一方向である（外側ループは、せいぜい、内側ループが静止したかどうかを知れば十分である）。通信が所定のネットワークにおいて決して双方向でないときには、そのネットワークに関してマスターポート番号およびタグは必要とされない。
・また、１つの未解決リクエストしか存在し得ない場合には、タグが必要とされない。
・リクエストが推測的に出されず（すなわち、とられていない経路に関する推測的なリクエストの場合と同様に、レスポンスを有する全てのリクエストに関して、そのレスポンスが明示的に受けられて決して捨てられない）且つレスポンスが順序正しく戻る場合には、ディープパイプラインされたコンポーネントと通信するときであってもタグが必要とされない。
・ネットワークが１つのマスターポートだけを有するときには、マスターポート番号も必要とされない。
・パケットペイロード内の１つのビットが常に一定である、または、デッドである、または、常に他のビットの冗長なコピーであるときには、そのビットは、パケットを送る間にパケットから削除することができ、また、パケットを受ける間に再び形成することができる。例えば、形式（ｃ１，ｃ２，ｘ，ｘ，ｄ，ｙ）のメッセージは、情報の損失を何ら伴わずに、カスタムネットワークを介して（ｘ，ｙ）として送ることができ、その後、それが受信コンポーネントに達するときに（ｃ１，ｃ２，ｘ，ｘ，［ｎｏｔ  ｃｏｎｎｅｃｔｅｄ］，ｙ）となることができる。ここで、ｃ１，ｃ２は一定のビットであり、ｄは、受信コンポーネントにより使用されないデッドビットを示し、また、ｘ，ｙは一定でないビットである。非常に包括的なプロファイリングフィードバックに基づき、ビットの「一定性」または冗長性を推測することさえでき、それにより、一定である或いは冗長であると想定されるビットが送られている間にその期待値と一致しないときにはエラーが引き起こされる。この稀なエラーからの回復は、最適化の節の最適化３にも記載されるように、アクセラレータ結果を取り消してソフトウェア実行に戻ることによって達成され得る。
【００４１】
［００６４］
周波数考慮：これらのＦＩＦＯインタフェースにおけるリクエスト信号、肯定応答信号、および、ペイロード信号は、配線遅延のためにサイクルのほぼ全体をリザーブしなければならず、また、それらの計算は、良好な全システム周波数を得るのに役立つべく、非常に僅かな論理しか含まないようにすべきである。異なるユニット間の往復遅延が存在すべきではなく、信号は、せいぜい、１つのユニットからその接続された隣接ユニットへと進むだけにすべきである。
【００４２】
［００６５］
ＦＩＦＯインタフェースは優れた周波数改善能力を有する。ユニットＡの送信ＦＩＦＯインタフェースがユニットＢの受信ＦＩＦＯインタフェースと通信しており、また、ＡおよびＢが必然的に遠く離れて配置されなければならない（例えば、大型のバタフライネットワークでは、離れたモジュール間の通信は避けられない）場合、長い配線に起因して起こり得る周波数減少を改善するための簡単な方法は、Ａの送信ＦＩＦＯインタフェースとＢの受信ＦＩＦＯインタフェースとの間で長い配線上に１つ以上の小さい２要素ＦＩＦＯを加えることであり、これは完全設計のセマンティクスを変えない（幾つかの経路の待ち時間を増大させるだけである）。そのような余分なＦＩＦＯの付加は、最初のコンパイレーション結果からフィードバックを受けた後に行うことができ、または、最初のコンパイレーション中に先制して行うことがでる。
【００４３】
［００６６］
更なる周波数考慮については最適化の節の最適化番号４において述べられている。
【００４４】
［００６７］
別の実施
この節において、本発明者らは、別の実施の幾つかの例を挙げる。
【００４５】
［００６８］
この好ましい実施形態は、大規模な並列ハードウェアシステムに合わせてシングルスレッドコードをコンパイルするという課題を解決するが、この文書の方法は、例えば以下のより小型の並列ハードウェアシステムを構築するために適用することもできる。
・部門の用途ニーズをサポートする、１つのラックだけから成る特定用途向けミニスーパーコンピュータ、または、
・アプリケーションが加速される際のバッテリー寿命を向上させるための、かなりの並列度を成すモバイル機器における単一の低周波、低電力チップ（低い周波数を並列度で補う）。
【００４６】
［００６９］
この好ましい実施形態において、本発明者らは、不完全バタフライサブネットワークとトーラス形状のタスクサブネットワークとから形成されるネットワーク、および、コンポーネントをネットワークに接続するためのＦＩＦＯインタフェースに焦点を合わせるが、同じチップ上のコンポーネント間の同等の通信機能性（Ｎ−Ｍ順方向ルーティングおよびＭ−Ｎ逆方向ルーティング）は、本発明者らの好ましいネットワークのそれぞれを例えばカスタマイズされた高速シリアルまたはパラレルオンチップバス（そのバスプロトコルがＦＩＦＯインタフェースに取って代わる）或いはカスタマイズされたファットツリーネットワークと置き換えることによって達成され得る。チップツーチップネットワークの不完全ハイパーキューブ編成は、ファットツリーまたは３Ｄトーラスなどの別のネットワーク編成に置き換えることもできる。また、本発明者らは、エネルギー消費量が低い特定用途向けスレッドユニットを形成するための有限状態機械に焦点を合わせるが、有限状態機械に取って代わることができる代替物としては、カスタマイズされた特定用途向けデータフロー回路［５］、または、必要とされる特徴のみを含む汎用プロセッサが挙げられ、この場合、スレッドユニットプログラムは、予めデコードされた形態でＲＯＭにストアされる。勿論、それぞれの代替物においては、コンポーネントおよびネットワークの低レベルハードウェアの細部が、エネルギー消費量が低い高性能特定用途向けスーパーコンピュータシステムを得るために極めて重要である。
【００４７】
［００７０］
スレッドユニットおよび階層的ソフトウェアパイプラインのイントロダクション。
任意の制御フローを伴う入力プログラムフラグメント（本発明者らは、混同が生じないときには「プログラム」と呼ぶ）を考えると、プログラムのネスト化されたループ階層（所定のループの任意の内側ループを含まない）におけるおよびプログラムの最外領域における各ループは、周波数が最適化された有限状態機械へと、すなわち、スレッドユニットと呼ばれるコンポーネントへと変換される。スレッドユニットは、それをポイントツーポイント送受信ＦＩＦＯ接続によってシステムの残りの部分に接続するネットワークと通信する。本発明者らは、最初に、スレッドユニットがここで行うことについて説明し、その後、本発明者らは、段落［００１１３］付近で、プログラム領域のためのシーケンシャルコードからスレッドユニットＶｅｒｉｌｏｇモジュールを形成する方法を示す。スレッドユニットは、以下を繰り返して行う有限状態機械を実装する。
・有限状態機械は、ループ起動リクエストがその親ループ／領域からその唯一のスレーブポートの受信ＦＩＦＯへと到達するのを待つ（このリクエストのパラメータは、ループのトップに存続してループの内側で使用されるレジスタである）。
・その後、有限状態機械は、所定のパラメータを用いてこのループ起動をパイプライン態様で実行し、それにより、ループ繰り返しを重ね合わせる。有限状態機械は、全ての経路でオペレーションを推測的に実行し、それにより、依存関係およびリソースが許容すればいつでも、繰り返しｎが終了される前に、繰り返しｎ＋１，ｎ＋２，...からオペレーションを発行する。しかしながら、電力を節約するために、有限状態機械は、経路がとられていないことが知られると直ぐに、経路上の残りのオペレーションの実行を停止する。また、有限状態機械は、複数の経路に共通の同一のオペレーションも認識して、それらのオペレーションを１回だけ実行する。有限状態機械は、より長い依存型サイクルを有する経路が所定の繰り返しで選択されるときはいつでも余分なサイクルを動的にとることによって可変繰り返し発行速度をサポートできる。これらの特性を得るためにエンハンスドパイプラインスケジューリングアルゴリズム［１１］［１０］が使用される。
・有限状態機械は、最後に、ループ起動レスポンス、すなわちレジスタ結果（ループ内に設定されるがループの出口ポイントで存続するレジスタ）を、その親ループ／領域へ、そのスレーブポートの送信ＦＩＦＯを介して送り戻す。ループが副次的効果（ストアなど）のためだけに実行される場合には、ループ起動レスポンスが送り戻されない。
【００４８】
［００７１］
スレッドユニットがプログラム領域でオペレーションをどのように実行するのかを以下に示す。
・１つのサイクルまたはそれよりも少ないサイクルをとるオペレーション：（例えば、加算演算、シフト演算、論理演算）これらは、ネットワークと何ら相互作用することなく、中心にクロックされた有限状態機械によりまとめられるように、それぞれの別個の簡単なオペレーションごとに異なるカスタム機能ユニットを割り当てることによってループスレッドユニットの内側で行われる。複数の依存的オペレーションは、それらの全てがサイクルに適合するときには、オペレーションの組み合わせチェーンを形成することによって同じサイクルで実行され得る。例えば、
〇一定量だけシフトさせる或いは回転させること、
〇ビット順列、
〇一定のマスクを伴う論理演算（ＡＮＤ、ＯＲ）、
〇レジスタコピーオペレーション、
〇値をメモリにストアした後、それを元の位置へロードする（ロードストアテレスコーピング［１７］またはレジスタプロモーション［１５］を使用して、これがレジスタコピーに等しくなる）こと、
〇ビット位置が一定のときにレジスタ内の任意のビットを検査すること、
・特に、符号付きの数字がゼロよりも小さいかどうかをチェックする、
〇狭い変数を幅広いサイズまでゼロ拡張する或いは符号拡張すること、
〇および、他の同様の簡単なオペレーションは、ゲート遅延を必要とせず（配線遅延だけ）、また、ハードウェアではほぼゼロ時間を要する。したがって、これらのオペレーションのうちの幾つかは単一サイクルにまとめられ得る。また、排他的ＯＲなどのビット単位の論理演算は、１サイクルの一部と僅かなゲートだけを必要とする。また、初期の逐次プログラムでビット幅減少最適化を使用して、所要のオペランド幅のみを有する機能ユニットが形成される。結果として、細粒度命令レベル並列度が増大されて、オペレーション待ち時間が減少され、電力が低減される。
・マルチサイクル複合オペレーション：スレッドユニットは、以下の種類のマルチサイクルオペレーションを行うことができる。
・メモリ階層のポートでのロード、ストア、または、更新オペレーション、
・Ｖｅｒｉｌｏｇライブラリモジュールをインスタンス化することによって実施される標準的なマルチサイクルオペレーション（整数除算または浮動小数点演算など）、
・カスタマイズされたパイプラインスレッドユニットとして実装されるこのループの内側ループ自体。
【００４９】
［００７２］
それぞれの種類の複合オペレーションは、それ自体の別個のネットワークを有する。そのようなネットワークには、リクエスタスレッドユニットの１つ又は２つ以上のマスターポートと、この種のオペレーションを実施するレスポンダコンポーネントの１つ又は２つ以上のスレーブポートとが接続される。１つのオペレーション種における所定のリクエスタスレッドユニットからのマスターポートの番号は、コンパイラによって見出される並列度によって上側が境界付けられる（例えば、バンクインターリーブメモリ階層のための一領域内のメモリへのＮ個の同時並列ロードは、せいぜい、Ｌ１キャッシュバンクのスレーブポートのいずれかへリクエストを送ることができるこのスレッドユニットからのＮ個のマスターポートをもたらす）。
【００５０】
［００７３］
所定の種類のマルチサイクル複合オペレーションを行うために、スレッドユニットは、該スレッドユニットのマスターポートの送信ＦＩＦＯからリクエストメッセージを専用のネットワークへ送る。オペレーションがレスポンスを必要とする場合には、少なくとも予測された数のサイクル（予測がプロファイラフィードバックまたは静的情報に基づく場合）を待った後、スレッドユニットは、同じマスターポートの受信ＦＩＦＯでレスポンスを受けようと試みる。リクエストはパイプライン化され得る。すなわち、例えば、リクエストｎ＋１，ｎ＋２，...．ｎ＋ｋ−１は、リクエストｎへのレスポンスが戻ってくる前に発行され得る。
【００５１】
［００７４］
副次的効果（メモリへのストアなど）のみのために実行される内側ループは、レスポンスを送り戻さない。しかしながら、そのような応答しない内側ループネストを開始したリクエストに起因する全てのアクティビティの完了は、リクエストのためのマスターポートと関連付けられる静止フリップフロップによって監視され得る。静止フリップフロップは最初は１である。ループネストを呼び出すための任意の新たなリクエストがマスターポートによって送られると、そのマスターポートと関連付けられたフリップフロップがゼロに設定される。所定のマスターポートからループネストへの過去のリクエストに起因する全てのアクティビティ（内側−内側...．内側ループおよびそれらへのストアを含む）が静止検出回路により決定されるように完了すると、マスターポートの静止フリップフロップが再び１になる。
【００５２】
［００７５］
図１１および図１２は、外側ループと内側ループのｋ個のコピーとから成るループネストのための静止回路を示す。図１８に描かれるランダムアクセスプログラムは、１つのそのようなループネストである。外側ループは、それぞれの繰り返しで新たな内側ループを生み出して（タスクネットワークがそれを受け入れる場合）、維持し続ける。内側ループは、並列して行われ得る幾つかのストアを実行する。回路の目的は、外側ループおよび全ての内側ループコピーの両方内の全てのアクティビティの完了を検出することである。図１１を参照すると、各スレッドユニット内のＱｕｎｉｔ回路およびタスクネットワークはスパニングツリーの形態で接続される。十分な数のバックツーバックサイクルにおいてＱｕｎｉｔの出力が１のときに、このＱｕｎｉｔで根付いたタスクサブネットワークおよびスレッドユニットのスパニングサブツリーが静止したことが知らされ得る。図１２を参照すると、システムリセット時間にカウンタ（１２０１）が−１に初期化される。「依然としてビジー状態」信号がループネストの静止検出回路（Ｑｕｎｉｔから形成される）からくるたびに、または、新たなタスクがループネストへ送られるときに、カウンタは、サイクルにおけるスパニングツリーの最大伝搬遅延に等しい遅延値＋安全係数に設定される。カウンタが元の−１へデクリメントされると、それは、全ループネスト内の全てのスレッドユニット、ストア、および、タスクネットワークが静止したことを意味する。したがって、カウンタ値の符号ビットは、ループネストのための静止フリップフロップとしての機能を果たす。なお、大型タスクサブネットワークの静止の検出は、大型スーパーコンピュータ実施において多くの数千のサイクルを取得してもよい。
【００５３】
［００７６］
ストアのみの静止は、検出することがループネストよりも容易である。未解決ストアカウンタがそれぞれのメモリマスターポートごとに形成され、その場合、カウンタは最初は−１である。各ストアリクエストがカウンタをインクリメントする。メモリ階層から戻ってきた各ストア肯定応答は、カウンタをデクリメントする。カウンタが元の−１へデクリメントされると、全ての過去のストアリクエストが全て完了したことが推測され得る。したがって、未解決ストアカウンタの符号ビットは、ストアマスターポートの静止フリップフロップとしての機能を果たす。ストア肯定応答は、ストアの完了を検出するためだけに使用される。
【００５４】
［００７７］
無論、内側ループのための単一のスレッドユニットは、複数のループ起動の実行をパイプライン態様で達成するのに不十分である。これは、１つの単一内側ループの繰り返しのパイプライン実行により内側ループスレッドユニットがビジー状態になる可能性が高いからである。しかしながら、本発明者らは、あたかも内側ループがパイプライン乗算器のようなプリミティブパイプラインオペレーションユニットであったかのように新たな完全内側ループ起動を連続して（Ｂａｃｋ  ｔｏ  ｂａｃｋ）送りたい。ループ起動のこの種のパイプライン実行は、内側ループの複数のコピーを形成してそれらをタスクネットワークへ接続することによって達成される。内側ループの内側ループは再帰的に複製される。ｉ，ｊ，ｋループネストの図１５におけるコード例およびそのハードウェア実施を参照すると、ｉループの１つのコピー、ｊループのＮ個のコピー、および、ｊループごとにｋループのＭ個のコピーが存在することができ、それにより、システムにおいてｋループのＮ×Ｍ個のコピーがもたらされる。本発明者らは、この技術を階層的ソフトウェアパイプライニングと呼ぶ。ｊループスレッドユニットアレイのおかげで、ｊループは、ｉループに対してプリミティブパイプラインオペレーションユニットのように見える。同様に、ｋループは、それぞれのｊループに対してプリミティブパイプラインオペレーションユニットのように見える。図１５におけるこの例を参照すると、本発明者らは、ここで既に、シングルスレッドコードフラグメントを以下のステップを備える並列ハードウェア構造へと変換するための基本的な階層的ソフトウェアパイプライニング技術を述べることができる。
・コードフラグメントの領域階層内のリーフ領域をハードウェア有限状態機械へ変換する、
・前記領域のための有限状態機械の少なくとも１つのコピーを形成して、状態機械との通信のためのネットワークを加え、それにより、組み合わされた有限状態機械コピーとネットワークとが領域の機能を実行するための単一のパイプラインプリミティブオペレーションとして振る舞うようにする、
・先の２つのステップをプログラムの領域階層に対して再帰的に適用し、それにより、ソフトウェア実行において親領域が子領域を呼び出すそれぞれのポイントで、ハードウェア実行において親領域のための有限状態機械が子領域のためのプリミティブパイプラインオペレーションを始めるようにする、
【００５５】
［００７８］
前述した階層的ソフトウェアパイプライニングパラダイムとの関連で、コンパイラは、ハードウェアを形成できるように以下のパラメータを更に推定する必要がある。
（ｉ）それぞれの内側ループごとのサイクルにおける予測待ち時間（レジスタ結果が内側ループによって戻される場合）、
（ｉｉ）各ループの複製カウント
（ｉｉｉ）メモリ階層編成に応じた、サイクルにおけるメモリロードオペレーションの待ち時間、
（ｉｖ）除算器／乗算器などの他の複合オペレーションの待ち時間および複製カウント
これらは、プロファイリングフィードバックまたは静的情報を使用して推定される。
【００５６】
［００７９］
メモリ階層。
カスタマイズされたスーパーコンピュータのメモリ階層の重要な要件は、（ｉ）それが、ハードウェア同期化ユニットを用いて、個々のメモリポートから出されるメモリ命令間のポイントツーポイント同期化をサポートしなければならないこと、および（ｉｉ）それが、多数の同時ロード／ストアオペレーションまで拡大しなければならないことである。ポートＰ２から出されるメモリ命令Ｉ２のインスタンスがポートＰ１から出されるメモリ命令Ｉ１の論理的に先のインスタンスに依存する場合には、（このときＩ２がＩ１を決して上回らないように）Ｉ１が完全であることを示す信号をＩ１のそのインスタンスが同期化ユニットへ送るための手段が存在すべきである。これは、ストアリクエストのための肯定応答レスポンスによって達成される。なお、ストア命令は、通常、汎用マイクロプロセッサで使用される通常のメモリ階層においてレスポンスを必要としない。一方、このメモリ階層構造では、シングルスレッドソフトウェアで生じないコンペア・アンド・スワップまたはメモリバリアなどのマルチプロセッサ命令を実施するための要件が存在しない。ベースラインスーパーコンピュータを簡単に維持するため、本発明者らは、最初に、ブラックボックスとして、同期化要件を満たし且つ並列してアクセスされ得る多くのポートを有する統合グローバルメモリを実装する、単一スーパーコンポーネントとしてのメモリ階層全体について説明する。メモリ階層ボックスのピンの詳細は以下の通りである。
・スレッドユニットに接続される１つ以上のスレーブメモリロード／ストアポート。各スレッドユニット上の各メモリロード／ストアマスターポートは、ワンツーワンネットワークを使用して、メモリ階層上の対応するメモリロード／ストアスレーブポートと接続する。スレッドユニットは、これらのポートを介してメモリリクエストを送る。幾つかの未解決リクエストを各ポートから出すことができ、また、リクエストのためのレスポンスは、この文書のネットワークインタフェース仕様にしたがって、バラバラの順序で戻ってくることができる。ロードリクエストと同様に、ストアが完全であることを同期化ユニットが検出するために、ストアリクエストもレスポンスを受ける。
・ライン読み取りリクエストおよびラインフラッシュリクエストなどのリクエストをホストコンピュータへ送って、ライン読み取りの場合にラインデータレスポンスを得るための１つ以上のホストマスターポート。これらはホスト通信ネットワークに接続される。ＰＣＩ  Ｅｘｐｒｅｓｓ外部通信デバイスは、ホスト通信ネットワーク上のスレーブポートであり、ホストアプリケーションに達するために使用される。ホストアプリケーションメモリはメモリ階層の根元である。
・ＤＤＲｎコントローラ外部通信デバイスを伴うワンツーワンネットワークと接続される１つ以上のＬ２データアレイマスターポート。これらは、各Ｌ２キャッシュラインのデータおよびタグの両方を含む外部ＤＲＡＭユニットに対して読み取りラインコマンドおよび書き込みラインコマンドを発する。
【００５７】
［００８０］
メモリ階層の効率的な実装は非常に重要である。最良の実装選択、すなわち、エネルギー効率および性能効率が最も良い実装選択は、カスタマイズされた特定用途向け分割メモリ階層である可能性が高く、その場合、最適化の節の最適化１に記載されるように、分割間でコヒーレンスは不要である。ベースラインスーパーコンピュータに関して、本発明者らは、メモリ分割をなしで済ませ、メモリ階層の以下の２つの拡張可能ベースライン実装について説明する。
・ディレクトリベースの書き込み更新プロトコルを伴うコヒーレントプライベートＬ１キャッシュ。おそらく、理想的なキャッシュは書き込み更新キャッシュであり、この場合、共有ラインへのストアにより、ラインの全ての共有コピーが更新される。書き込み更新キャッシュの考えは、過度な帯域幅要件に関する懸案事項に起因して、従来の拡張可能な商業システムではあまり知られていなかった。本発明者らのディレクトリベースのコヒーレンスプロトコルでは、ラインの共有者の組が常に正確に知られ、したがって、限られたネットワークトラフィックのみを使用して書き込み更新を行い易い。ディレクトリユニットは、対応するＬ２キャッシュとは別個である。キャッシュライン（すなわち、１つのラインを共有するキャッシュの組）のためにディレクトリ内に保持される情報も、そのラインを所有する少なくとも１つのキャッシュが存在するときにはいつでも、ディレクトリユニット内にキャッシュされる。このようにすると、１つのＬ１キャッシュにより要求されるラインが他のＬ１キャッシュ内に存在するときにはいつでも、Ｌ２へのアクセスが回避される（なお、本実施形態ではＬ２データおよびタグアレイが外部ＤＲＡＭ内にあるため、Ｌ２キャッシュはＬ１キャッシュよりもかなり遅い）。コンパイラは既に依存型メモリオペレーション間で同期を成すので、この構造では、Ｌ１キャッシュとディレクトリユニットとの並列オペレーションが大幅に簡略化される。すなわち、本発明者らの実施ではロールバックまたは「ＮＡＣＫ−否定応答」レスポンスが存在しない。図１６はこのキャッシュの構造を示す。
・バンクインターリーブ共有キャッシュは、より簡単な論理をもたらす他の想定し得るメモリ階層構造である。しかしながら、スレッドユニットとＬ１キャッシュとの間に挿入される付加的な不完全バタフライネットワークの追加に起因して、キャッシュヒットメモリレイテンシが増大される。バンクインターリーブキャッシュにおけるバンクは、アドレス空間の独立部分を反映し、そのため、コヒーレンスを必要としない。しかしながら、ネットワーク遅延に起因して、最小アクセス待ち時間は、コヒーレントプライベートキャッシュのそれよりも長い。（ランダムアクセス例のように）ローカル性を何ら伴わないプログラムに適した、Ｌ１キャッシュを伴わないバンクインターリーブＬ２キャッシュが図１７に示される。バンクインターリーブメモリは実施が容易であり、そのため、その詳細を説明するために付録が与えられない。
【００５８】
［００８１］
ホストコンピュータとの通信インタフェース。
ホストインタフェースは、ホストコンピュータに接続されるＰＣＩ  Ｅｘｐｒｅｓｓインタフェース外部通信デバイスから成る。チップの内側に面するユーザ論理側で、ホストインタフェースは、（チップの外部のＰＣＩ  Ｅｘｐｒｅｓｓレーンを介して）ホストからくるメッセージのためのＦＩＦＯ送信インタフェースと、（チップの外部のＰＣＩ  Ｅｘｐｒｅｓｓレーンを介して）ホストへと向かうメッセージのためのＦＩＦＯ受信インタフェースとを含む。メッセージは可変長マルチワードメッセージであり、その場合、それぞれのワードは３２ビットである。好ましい実施形態は、最大移植性のために、ソフトウェアベースの通信インタフェースをホストで使用する。すなわち、オリジナルソフトウェアアプリケーション内の加速されたコードフラグメントの入力命令の直前にサブルーチンｓｔａｒｔ＿ａｃｃｅｌｅｒａｔｏｒの呼び出しがなされ、それにより、後述するホストアクセラレータメッセージ交換機能が呼び出される。
【００５９】
［００８２］
ホストアクセラレータメッセージ交換機能は、以下のＣ／Ｃ＋＋ソフトウェアＡＰＩを伴うアクセラレータと通信する。
・ｉｎｔ  ｓｅｎｄ（ｃｏｎｓｔ  ｖｏｉｄ＊  ｂｕｆ，ｃｏｎｓｔ  ｉｎｔ  ｎ）、アドレスｂｕｆにｎバイトのメッセージを送信するとともに、送信がうまくいった場合にはｎを戻す。エラー時には−１を戻す。メッセージは、アクセラレータのＰＣＩ  Ｅｘｐｒｅｓｓ受信ＦＩＦＯに現れる。
・ｉｎｔ  ｒｅｃｅｉｖｅ（ｖｏｉｄ＊  ｂｕｆ，ｃｏｎｓｔ  ｉｎｔ  ｎ）、アクセラレータのＰＣＩ  Ｅｘｐｒｅｓｓ送信ＦＩＦＯに置かれたｎバイト以下のアドレスｂｕｆへのメッセージを受信して、受信されたバイト数を戻す。エラー時には−１を戻す。
【００６０】
［００８３］
アクセラレータ側で、ＰＣＩ  Ｅｘｐｒｅｓｓ送受信ＦＩＦＯは、メモリ階層の節で既に述べたホスト通信ネットワークの唯一のスレーブポートを構成する。このネットワークのマスターポートは以下である。
・トッププログラム領域スレッドユニットのためのタスクネットワークに接続されたトップタスクアダプタ。なお、慣例により、アクセラレータは、ホストと通信するときには常にマスターである。アプリケーションの初めに、本発明者らは、アプリケーションを開始するべくアクセラレータがｒｅｓｕｍｅ＿ｒｅｑｕｅｓｔメッセージをホストへ送り、また、このとき、アクセラレータがそこから続けるべき新たなレジスタ状態を受けるためにアクセラレータがｒｅｓｕｍｅ＿ｒｅｓｐｏｎｓｅメッセージを待っていると見せかける。トップタスクアダプタは、ホストからｒｅｓｕｍｅ＿ｒｅｓｐｏｎｓｅメッセージと共に初期のレジスタ状態を受けるとともに、最終的なレジスタ状態を、そのｒｅｓｕｍｅ＿ｒｅｑｕｅｓｔメッセージで、ホストメッセージングソフトウェアにより理解されるフォーマットを成して送り戻す。
・メモリ階層の節で述べたような、メモリ階層中のボトムレベル（例えばＬ２）キャッシュのホストマスターポート。それぞれのボトムレベルキャッシュからのライン読み取りリクエストまたはラインフラッシュリクエストはホストへ送られ、また、ライン読み取りの場合のため、ラインコンテンツがホストから受け戻される。
【００６１】
［００８４］
ホストアクセラレータメッセージ交換機能：ホストがアクセラレータとどのように通信するのかを以下に示す。シーケンシャルソフトウェアアプリケーション内の特定のプログラムフラグメントが、加速のために選択されて、並列ハードウェアへと変換されると仮定する。本発明者らは、以下のようにオリジナルアプリケーションから新たなプログラムを得る。
・選択されたコードフラグメントの初めにプログラムが達すると、該プログラムがｓｔａｒｔ＿ａｃｃｅｌｅｒａｔｏｒサブルーチンを呼び出し、ｓｔａｒｔ＿ａｃｃｅｌｅｒａｔｏｒサブルーチンは、初期レジスタ値およびプログラムカウンタをｒｅｓｕｍｅ＿ｒｅｓｐｏｎｓｅメッセージによってハードウェアアクセラレータへ送るとともに、アクセラレータからのレスポンスを待ち始める。
・空のキャッシュに端を発して、アクセラレータが起動する、
・アクセラレータが終了されると、アクセラレータは、そのキャッシュ内の全てのダーティエントリをホストアプリケーションメモリへフラッシングして、そのキャッシュを無効にする。
・その後、アクセラレータは、ｒｅｓｕｍｅ＿ｒｅｑｕｅｓｔメッセージを用いて、最終的なレジスタコンテンツおよび最終的なプログラムカウンタをホストへ送る。
・その後、ホストは、これらのレジスタを復元して、選択されたコードフラグメントの出口ポイントに対応する所定のプログラムカウンタにジャンプする。
・加速されたコードフラグメントは、ソフトウェアアプリケーションの実行中に、ゼロ回またはそれ以上の回数にわたって呼び出されてもよい。
・ホストアプリケーションが終了されると、アプリケーションは、アクセラレータアクティビティの完了を引き起こすためにｔｅｒｍｉｎａｔｅメッセージをアクセラレータへ送る。
〇例えば、ｔｅｒｍｉｎａｔｅメッセージの受信時、アクセラレータは「行われた」を示すＬＥＤを点灯させる。アプリケーションのプロセスと通信する第２のソフトウェアプロセス内でアクセラレータのＶｅｒｉｌｏｇシミュレーションが行われている場合、ｔｅｒｍｉｎａｔｅメッセージは、Ｖｅｒｉｌｏｇシミュレーションプロセスも終わらせる。
【表１】
0005817032.tif 000002
【００６２】
［００８５］
図２０はホストアクセラレータ通信プロトコルを示す。
【００６３】
［００８６］
別の実装形態：ホストアクセラレータ通信プロトコルの以下の別の実装形態も想定し得る。
・ダイレクトメモリアクセス（ＤＭＡ）ハードウェア能力を使用して、アクセラレータからのラインフラッシュが正しいバイトマスク下で正しいアプリケーションメモリ領域に書き込まれ、また、アクセラレータからのライン読み取りは、中間バッファリングまたはソフトウェア介入を伴うことなく、正しいアプリケーションメモリ領域から読み取る。アプリケーションへアクセスできない場所がアクセラレータによって読み取られるときにはゼロが戻される。
・完全対称コヒーレンスプロトコル（ここでアクセラレータが終了されるときにアクセラレータがそのラインをフラッシングしない場合には、要求に応じてホストがそれらを戻す）。これは、スーパーコンピュータのメモリ階層をシステムメモリにして、あたかもホストマイクロプロセッサがスレッドユニットの１つであったかのようにホストマイクロプロセッサを同じメモリ階層に取り付けることによって最も容易に行われる。この編成では、アクセラレータからのラインリードメッセージおよびラインフラッシュメッセージはもはや要求とされない（メモリコヒーレンスプロトコルがそれらに取って代わる）。
加速されたコードフラグメントを入力するための別の方法は、ｓｔａｒｔ＿ａｃｃｅｌｅｒａｔｏｒソフトウェアサブルーチン呼び出しの他に、以下を含む。
１．先に与えられたホストアクセラレータメッセージ交換ループを実行する軽量システム呼び出し
２．ハードウェア内で同じメッセージ交換ループを行う新たなハードウェア命令ｓｔａｒｔ＿ａｃｃｅｌｅｒａｔｏｒ  最適化の節の最適化番号１２で詳述されるように、少なくとも２つの手法が外部インタラプトをサポートすべきである。
【００６４】
［００８７］
複数の異なるアクセラレータ機能のサポート：ソフトウェアアプリケーションの互いに素な領域から抽出される複数の異なるプログラムフラグメントがハードウェアにマッピングされる場合には、要求されるプログラムフラグメントのためのトップレベル領域スレッドユニットへ初期タスクを送る１つのトップレベルタスクアダプタが存在する。ボトムレベルキャッシュは、プログラムフラグメント間で共有されてもよく、または、それぞれのプログラムフラグメントごとに異なってもよい。いずれにせよ、各ライン読み取りリクエスト内のリクエスタｉｄ／マスターポート番号は、いずれのキャッシュがラインをレスポンスとして受けるべきかを示す。初期レジスタを含む初期ｒｅｓｕｍｅ＿ｒｅｓｐｏｎｓｅメッセージをホストからアクセラレータへ送る際、ｒｅｓｕｍｅ＿ｒｅｓｐｏｎｓｅメッセージは正しいプログラムカウンタ（入力ポイント）アドレスも含む。トップタスクユニット内のカスタムデコーダは、入力ポイントアドレスの値に基づいて、正しいトップレベル領域スレッドユニットへメッセージを送る。コンポーネントおよびネットワークのためのトップレベル設計アルゴリズム
【００６５】
［００８８］
今や、本発明者らは、トップタスクアダプタ、メモリ階層、ＰＣＩ  Ｅｘｐｒｅｓｓ通信デバイス、および、ＤＤＲｎ通信デバイスが互いにどのように接続されるべきかを知っているため、本発明者らは、トップレベルコンポーネントの配線を完了するために、これらに対してスレッドユニットおよびタスクネットワークをいつでも加えることができる状態にある。
【００６６】
［００８９］
図１８はプログラム（ランダムアクセスと呼ばれるスーパーコンピュータアプリケーション）の一例である。図１９は、ランダムアクセスプログラムのためのフラット非分割構造を示す。この例では、トップ領域の１つのコピーと、ｉループの１つのコピーと、ｊループの８つのコピーとから成る階層的ソフトウェアパイプライニング構造がスレッドユニットを構成する。ホストプロセッサは、初期レジスタ値をＰＣＩ  Ｅｘｐｒｅｓｓ接続を介してトップタスクアダプタによりアクセラレータへ送るとともに、トップタスクアダプタからも最終的なレジスタ値を受ける。各スレッドユニットアクセスメモリは、マルチポートメモリ階層スーパーコンポーネントにおける別個のポートに接続される。外部ＤＲＡＭユニット（この例では６個）は、最も低いレベルのキャッシュをシステムに与える。ＤＲＡＭキャッシュユニットもミスを引き起こすと、ホスト通信ネットワークを介してＰＣＩ  Ｅｘｐｒｅｓｓ接続によりホストプロセッサからラインが得られる。アクセラレータが終了されると、アクセラレータは、そのダーティラインもＰＣＩ  Ｅｘｐｒｅｓｓ接続を介してソフトウェアアプリケーションアドレス空間へフラッシングする。
【００６７】
［００９０］
それぞれのループごとに複製カウントが与えられるとともに、プログラムの領域階層およびＤＤＲｎコントローラの総数が与えられると、非分割フラットスーパーコンピュータのトップレベルコンポーネントを形成してそれらを接続することによりランダムアクセス例における図１９に示される結果を得る。
【００６８】
［００９１］
このアルゴリズムは、単一チップのためのトップレベルフラット構造を完成する。この構造がチップ上に取り付けば、本発明者ら完了である。しかし、構造が面積の限界を越えれば、そのときには、メモリ階層をその内部コンポーネントおよびネットワークにエクスプロードした後に構造が分割されなければならない。シーケンシャルコードをカスタマイズされたハードウェアスレッドユニットへとコンパイルする
【００６９】
［００９２］
前の節において、本発明者らは、正しいカスタマイズされたスレッドユニットがインスタンス化するために既にコンポーネントとして利用できたと仮定して、完全特定用途向けスーパーコンピュータのためのフラット非分割構造を形成する方法について説明した。この節では、本発明者らは、ハードウェアへ変換されるべきソフトウェアアプリケーション内の入力コードフラグメント（本発明者らは、この場合も先と同様に、混同がないときにはこのコードフラグメントを「プログラム」と呼ぶ）を前提として、これらのカスタマイズされたスレッドユニットを形成する方法について説明する。スレッドユニットを理解するためには、オリジナルプログラムがなぜにどのようにして並列ハードウェアで正確に機能するのかを理解することが役に立つ。
【００７０】
［００９３］
並列化の正確さ規則。
本発明者らは最初に依存関係を規定しなければならない。
【００７１】
［００９４］
命令は、プログラムのオブジェクトコード／アセンブリリスト内のそのライン番号（または、１６進数命令アドレス）によって一意的に特定される。実行トレースは、（もしあれば）プログラムが終了するまで、所定のメモリおよびレジスタ状態に端を発してプログラムにより実行される動的な一連の命令である。一般に、実行トレースは、それぞれの異なる入力レジスタ／メモリ状態ごとに異なり得る。なお、特定の命令Ｉ１は、複数回実行されてもよく、すなわち、実行トレースにおいて複数回発生してもよい。これらの発生のそれぞれは、命令Ｉ１のインスタンスと呼ばれる。
【００７２】
［００９５］
実行トレースにおけるロード／ストア命令Ｉ１のインスタンスおよびロード／ストア命令Ｉ２のインスタンスは、Ｉ１，Ｉ２の前記インスタンスが同じデータオペランドアドレスを参照する場合にはメモリ依存性を有すると言われ、また、Ｉ１またはＩ２の少なくとも一方はストアである。
【００７３】
［００９６］
実行トレースにおける命令Ｉ１のインスタンスおよび命令Ｉ２のインスタンスは、Ｉ１の前記インスタンスがその後にＩ２の前記インスタンスにより使用されるレジスタを設定する場合にはレジスタ依存性を有する。本発明者らは、レジスタｒ１がＩ１によって書き込まれて再びＩ２により書き込まれ或いはＩ１により読み取られた後にＩ２により書き込まれる場合には依存性を無視できる。これは、場合により、既知のコンパイラ技術［１０］を用いて、新たなコピーｒ１＝ｒ１'命令の導入により、Ｉ２によって書き込まれるレジスタｒ１を例えばｒ１'に改名できるとともに、その使用もｒ１'に改名できるからである。
【００７４】
［００９７］
本発明者らは、命令Ｉ１のインスタンスと命令Ｉ２のインスタンスとの間にメモリ依存性またはレジスタ依存性またはこれらの両方が存在する場合には、命令Ｉ１のインスタンスと命令Ｉ２のインスタンスとが依存していると言う。
【００７５】
［００９８］
ソフトウェアプログラムの並列ハードウェアバージョンは、オリジナルシーケンシャルソフトウェアプログラムと同じ結果を与えなければならない。すなわち、このことは、メモリおよびレジスタの任意の初期状態とプログラムカウンタとが与えられると、並列ハードウェアバージョンが（ソフトウェア）プログラムと同じ最終的なメモリ、レジスタ、および、プログラムカウンタを生成しなければならないことを意味する。このことは、ハードウェアが並列化のための以下の正確さ規則を満たさなければならないことを意味する。すなわち、初期レジスタ／メモリ状態と対応する実行トレースとが与えられると、ハードウェアが同じ初期状態で起動されると、
１．ハードウェアは、実行トレース内で全ての命令インスタンスを実行しなければならない。
ａ．コメント：幾つかの命令（加算、シフトのような命令）は、１つ以下のサイクルを利用して、有限状態機械内で行われ、一方、他の命令（除算、ロードのような命令）は、複数のサイクルを利用することができ、ライブラリモジュールへメッセージを送ってレスポンスを受けることによって行われる、ことに留意されたい。
ｂ．コメント：コンパイラは、最初に、ハードウェア実装のための等価であるが更に高速のシーケンシャルコードを得るべくプログラムを最適化してもよい。例えば、ハードウェアがかなり多くのレジスタを有し、したがって、レジスタプロモーション［１５］を適用できる。結果のデッドビットまたは一定ビットをコンパイラ解析によって見つけて除去することができ、それにより、全ワード長よりも小さいレジスタおよびオペレーションがもたらされる。
２．実行トレースが命令Ｉ１のインスタンスと命令Ｉ２のインスタンスとを含んでいれば、Ｉ１，Ｉ２のこれらのインスタンスが依存している場合に、プログラムの並列ハードウェアバージョンは、Ｉ１の前記インスタンスの後にＩ２の前記インスタンスも実行しなければならない。
ａ．コメント：実際に、命令インスタンスの順序付けが並列ハードウェア実装においてどのように達成されるのかは、以下の通りである。Ｉ１，Ｉ２のインスタンスが共通のクロックを用いて同じチップ内で実行される場合には、Ｉ１のインスタンスが完了するサイクルの後にＩ２のインスタンスが１つのサイクル内で始まってもよい。Ｉ２は、場合により、レジスタまたはメモリの記憶場所に保持される或いはメッセージの一部として通されるＩ１の結果を使用する。或いは、Ｉ１およびＩ２が非常に簡単なオペレーションであれば、Ｉ２をＩ１の後に組み合わせ回路と同じサイクルで実行することができる。Ｉ１，Ｉ２のインスタンスが異なるチップＡ，Ｂで実行されれば、Ｉ１の実行の結果は、チップ−チップ相互接続を介してチップＡからチップＢへ送られるメッセージに寄与し、また、チップＢにおけるＩ２は、それが始まることができる前にそのメッセージを待つ。
３．依存していない命令インスタンスの場合、ハードウェアは、それらの命令インスタンスを任意の順序で或いは並行して同時に実行できる。
正確さ規則は、全ての実行トレースに関して、すなわち、全てのプログラム入力状態に関して満たされなければならない。先に与えられた３番目の規則は、並列度をもたらす規則である。先に与えられた重大な２番目の正確さ規則に関しては、メモリ依存性を強化することが最も重要な課題である。これは、２つの所定のメモリ命令間に依存性が存在するかどうかをコンパイラが（コンパイル時に）時として知らず、その一方で、レジスタ依存性に関しては、依存性がコンパイラに対して完全に明らかであるためである。
【００７６】
［００９９］
ハードウェア同期化ユニット：そのうちの一方がストアである２つのメモリ命令（Ｉ１，Ｉ２）間の依存性を扱うために、シーケンシャルシングルスレッドプログラムのハードウェアバージョンは、Ｉ２を実行するためのメモリ階層ポートとおよびＩ１を実行するためのメモリ階層ポートとも直接的に或いは間接的に通信する少なくとも１つのカスタマイズされた特定用途向けハードウェア同期化ユニットを組み込む（なお、一般に、Ｉ１，Ｉ２の複数のインスタンスが並列に実行できるため、複数のポートが使用される）。ハードウェア同期化ユニットの機能は以下で定められる。ハードウェア同期化ユニットの機能は、以下のハードウェア実行順序を確保することである。すなわち、メモリ命令インスタンスＩ２がソフトウェア実行において論理的に先のメモリ命令インスタンスＩ１に依存する場合には、Ｉ２の前記インスタンスは、ハードウェア実行においてＩ１の前記インスタンスの後に実行される。Ｉ１がストアで且つＩ２がロードである場合には、Ｉ１のインスタンスは、メモリを経由することなく、同期化ユニットを介してそのデータをＩ２のインスタンスへ直接に転送することもできる（Ｉ２のインスタンスがＩ１のインスタンスと同じアドレスにアクセスしている場合）。また、メモリ依存性をコンパイラが確信していない場合、同期化ユニットは、Ｉ１のインスタンスの前に推測的にＩ２のインスタンスが（誤データ推測をもって）実行できるようにしてもよい。この場合、例えばランタイムでＩ２およびＩ１のオペランドアドレスを比較することによって依存性が最終的に見出されると、Ｉ２のインスタンスは、Ｉ１のインスタンスが実行された後に同期化ユニットによって再実行されなければならない。本発明者らは、この好ましい実施形態におけるカスタマイズされた特定用途向けハードウェア同期化ユニットの幾つかの効率的な実装について説明する。すなわち、
・最適化６における静止検出回路。ここでは、Ｉ１がプログラム領域（ループネスト）Ａ内にあり、また、Ｉ２がプログラム領域（ループネスト）Ｂ内にある。Ｂのインスタンスは、それが始まる前に、Ａの論理的に先のインスタンスにおける全てのメモリ命令が完了するのを待つ。そのため、ＢにおけるＩ２のインスタンスは、ＡにおけるＩ１のインスタンスが完了するのを待つ。
・最適化の節の中の最適化２におけるシリアライゼーション同期化ユニット。これは、静止検出回路のより柔軟な変形である。
・最適化２における列車衝突同期化ユニット。ここでは、Ｉ１が領域Ａ内にあって、該領域ＡでＩ１が繰り返し実行され、また、Ｉ２が領域Ｂ内にあって、該領域ＢでＩ２が繰り返し実行される。Ｂ内のＩ２は、同期化ユニットを介して、「あなたは自由に進むことができる」または「あなたは自由に進むことができない」のいずれかを示す信号をＩ１の論理的に先のインスタンスから継続的に受け、したがって、Ｂは、Ａからの増分信号を監視することによりＡが完了する前に実行を開始できる。
・最適化２におけるＦＩＦＯ同期化ユニット。これは列車衝突同期化回路の特別なケースであり、この場合、データは、領域Ａ内のＩ１の一連のインスタンスのそれぞれの要素から領域Ｂ内のＩ２の一連のインスタンスの対応する依存要素へとポイントツーポイントでバイパスされる。
・最適化１におけるコンパイルされたスヌーピー書き込み更新キャッシュ同期化回路。ここでは、Ｉ２のインスタンスは、高度にカスタマイズされた論理を使用して、静止検出の場合と同様に中間回路を何ら伴うことなくＩ１のインスタンスと直接に同期化される。例えば、ロードＩ２のデータが既にレジスタ内にキャッシュされる際には、依存性が最終的に見出されると、ストアＩ１は、メモリアクセスを何ら引き起こすことなく、Ｉ２におけるキャッシュされたレジスタデータが更新されるようにする。
・最適化３におけるスレッドレベル推測実行をサポートする同期化回路。ここでは、Ｉ１が領域Ａ内にあり、Ｉ２が領域Ｂ内にある。同期化回路は、Ｉ１を含むＡの論理的に先のインスタンスが完了する前にＢのインスタンスを実行させる。その後、同期化回路は、依存性が最終的に見出されると、Ｂ（したがってＩ２）を再実行する。
本文書中に明示的に含まれない（例えば、無作為の順序でデータ構造を書き込む第１のスレッドＡおよび連続する順序で同じデータ構造を読み取る第２のスレッドＢの並列実行をサポートするための）カスタマイズされたハードウェア同期化ユニットの別の実施形態も想定し得る。
【００７７】
［００１００］
制御依存性の無視：実行トレースにおいて条件付き分岐に従うオペレーションが条件付き分岐後に実行されるべきことを本発明者らが言わなかったことに留意されたい。オペレーションをガードする（すなわち、そのオペレーションを実行すべきか否かを決定する）条件付きブランチとオペレーションそれ自体との間の依存性は、制御依存性［２６］と呼ばれる。制御依存性が無視されて、オペレーションをガードする条件付きブランチの前にオペレーションが実行されると、オペレーションは、制御推測（データ推測とは異なる）のインスタンスとして、推測的に実行されると言われる。推測的に実行されるオペレーションは、条件付きブランチの結果に応じて、無駄な計算になる場合がある。以下の例に示されるように、推測的実行は、より高い並列度を得るために不可欠である。
【表２】
0005817032.tif 000003
【００７８】
［００１０１］
ここで、ｙ＜０からｚ＝ｈ１（ｚ）またはｚ＝ｈ２（ｚ）までの制御依存性が重んじられ、したがって、ｙ＝ｆ（ｘ）、ｙ＜０、および、ｚ＝ｈ１（ｚ）またはｚ＝ｈ２（ｚ）のうちの一方が実行するのをｘ＝ｇ（ｚ）が待つ場合には、このループの実行中に並列度を殆ど利用できない。これは、ｙ＝ｆ（ｘ）→ｙ＜０であれば→ｚ＝ｈ１（ｚ）またはｚ＝ｈ２（ｚ）→ｘ＝ｇ（ｚ）→ｙ＝ｆ（ｘ）へ戻るという依存性のサイクルが存在するからである。しかし、制御依存性を重んじないことによって、また、ｙ＜０から生じるエッジをカットすることによって、サイクルが破壊される場合には、例えば、ｚの値が前の繰り返しｉ−１から利用できる直後に繰り返しｉ内でｈ１（ｚ）およびｈ２（ｚ）の両方を推測的に計算して、その後に、現在の繰り返しｉにおいてｙ＜０が最終的に計算されるときに正しい一方を選択することによって、より高い並列度を利用できるようになる。繰り返しｉがｚの新たな値を計算することを望むときまでに、繰り返しｉ−１においてさえもｙ＜０が未だに計算されなければ（そのため、繰り返しｉ−１からのｚの値が未知であり、それが複数の想定し得る値のうちの１つである）、繰り返しｉにおいてｚの値を計算することは、より深い推測を必要とする。ｚ'＝ｈ１（ｚ）およびｚ"＝ｈ２（ｚ）が繰り返しｉ−１においてｚの候補値であった場合には、繰り返しｉにおいてｈ１（ｚ'），ｈ２（ｚ'），ｈ１（ｚ"），ｈ２（ｚ"）の全てをｚの候補値として計算することができ、一方、繰り返しｉ−１におけるｘの想定し得る値を同時に推測的にｇ（ｚ'）およびｇ（ｚ"）として計算できる。そのような積極的な全経路推測は、指数関数的な数の推測的計算へと発展し得るが、推測的に実行されるオペレーションの総数は、多くの場合、ほぼ実現可能な数を超えない。これは、所定の繰り返しでｙ＜０が最終的に知られるときはいつでも、推測的に計算された全ての値の半分が捨てられるからである。オペレーションｆ，ｇ，ｈ１，ｈ２が単一のサイクルのみをとる場合には、推測が細粒である。それらのオペレーションが複合関数呼び出し或いは推測に適したオペレーションであれば、推測が粗粒である。しかし、このコードフラグメントなどの非常にシーケンシャルなコードフラグメントからスピードアップを得るためには、細粒推測実行および粗粒推測実行のいずれも重要である。ｆ，ｇ，ｈ１，ｈ２が確かに１つのサイクルをとる場合において、以下のツリーＶＬＩＷコード［７］は、適度な全経路推測を用いてこのループを繰り返しごとに１サイクルの速度で状態機械により実行できることを明らかにする。本発明者らが伝えたいポイントは、より高い並列度を得るためには推測的実行が不可欠であり且つ現実的であるという点である。なお、このコードの今日のスーパースケーラプロセッサ実行は、それぞれのブランチ予測ミスでシリアライゼーションオーバーヘッドに見舞われる。全経路推測は、ブランチ予測よりも良好な並列度を達成する。
【表３】
0005817032.tif 000004
【表４】
0005817032.tif 000005
【表５】
0005817032.tif 000006
本発明者らは、条件付き実行を伴うツリーＶＬＩＷをどのようにして状態機械へと変換できるのかを以下で示す。
【００７９】
［００１０２］
ループが多数回繰り返し、また、制御依存性がループの任意の依存性サイクル上にない場合には、既知のコンパイラ技術を使用する条件付き分岐の代わりに、１つ以上のｓｅｌｅｃｔ  ｚ＝ｃｃ，ｚ'，ｚ''命令を形成することによって、性能を損うことなく、制御依存性を重んじることができる。先に与えられた選択命令例の意味は、ｚ＝（ｃｃ？ｚ'：ｚ''）相当のＣコードである。選択命令へのこの変換は、コードエクスプロージョンを減少させるために有益である。選択命令は、ツリーＶＬＩＷ／状態内に２：１マルチプレクサオペレーションをもたらし、条件付きブランチがなし得るようにツリーＶＬＩＷ／状態の数を増大させない。
【００８０】
［００１０３］
推測的実行のための要件が簡単な１サイクルオペレーションにだけでなくメモリからのロードにも適用されるとともに、全領域起動にも適用されることを更に明らかにするため、本発明者らは、推測が行われないときに限られた並列度を有する、図６４におけるチェス遊びのためのアルファ−ベータ枝刈りアルゴリズムを与える。この場合には、このアプリケーションから高い並列度を得るために、全再帰的サブルーチン呼び出しが推測的に実行されなければならない。アルファ−ベータ枝刈りの詳細は、最適化の節の最適化７，８に記載される。
【００８１】
［００１０４］
階層的ソフトウェアパイプライニング。
それぞれの別個のオペレーションがほぼ１つの機能ユニットにマッピングされる、中央クロックを有するミーリー有限状態機械は、簡単で且つ最小の同期化オーバーヘッドを有する特定用途向け並列ハードウェアを形成するために非常に魅力的である。任意の所定のオペレーションのオペランドは、オペレーションが実行する状態および条件に有限状態機械が達するときに、オペレーションを実行する機能ユニットの近傍の例えばフリップフロップに予めある。すなわち、有限状態機械の機構自体を越えて、オペランドまたは同期化オーバーヘッドを待たない。有限状態機械手法は、その簡潔さに起因して、この好ましい実施形態によって選択された。
【００８２】
［００１０５］
任意の制御複雑性の大きなプログラム（例えば、２つ以上のループを有するプログラム、これらのループのそれぞれは、入力データに応じて異なる条件付きブランチを有する）は、その並列実行が単一の有限状態機械によって制御されるときにかなり多くの状態をもたらすことができる。プログラム全体は非常に大きいが、その内側ループ／開始−終了ブロックが単一の複合命令へと変換されるループなどのプログラムの階層領域は、しばしば、並列実行のための有限機械状態への変換にとって許容できるサイズを有する。一方、小さい基本ブロックなどのループ起動よりも小さい領域を状態機械にカバーさせると、その領域内の命令レベル並列度が小さくなり、依存領域にわたる同期化および通信が増大する。小さい領域に関しては、（メモリまたはレジスタ／タスクネットワークを介した）クロス領域通信は、エネルギーを不必要に浪費する可能性があり、また、場合によりグローバルクリティカルパスを延ばす場合がある。この理由のため、本発明者らの好ましい手法は、それぞれの内側領域（内側ループまたは開始−終了ブロック）が単一の複合命令へと折り畳まれる、グローバルシリアライゼーションポイントが生じないかなり長い実行トレースを有する階層的プログラム領域のための有限状態機械を構成するようになっていた。その命令が複合命令であって且つそれぞれの命令が命令レベル並列度を含む外側ループにおける命令レベル並列度、および、複合命令の再帰的ネスティング（階層的ソフトウェアパイプライニング）は、サイクルごとの全体の命令プリミティブに対して相乗効果をもたらし得る。そのため、再帰的ネスティングに起因して、各ループレベルにおける（場合により複合的な）命令レベル並列度が高ければ高いほど、命令レベル並列度に対する想定し得る相乗効果も高くなる。命令レベル並列度が低いプログラム領域のための状態機械の形成を回避するのに役立つように、一般にプロファイリングフィードバックにより決定される非常に少ない回数で実行される内側ループは、ループピーリング［２９］を用いて数回剥がされ得る。したがって、内側ループにおける繰り返し数が確かに少ないときには、内側ループが外側ループと一体になる。
【００８３】
［００１０６］
内側ループまたは開始−終了ブロックを表す複合命令の逐次的セマンティクスは、（加算またはストアなどのプリミティブオペレーションを表すアトミック命令とは対照的に）複合命令が、同じ初期状態で開始されるときに、オリジナルプログラム領域によって読み取られ或いは書き込まれた全てのレジスタおよびメモリの記憶場所を読み取って書き込むことである。複合命令の実行は、同じ開始状態における対応するオリジナルプログラム領域の実行に相当する。プログラム領域および対応する複合命令はいずれも、所定の入力（メモリおよびレジスタの状態）で同じ関数変換を達成する。
【００８４】
［００１０７］
領域が実行を開始する前の初期状態が与えられると、本発明者らは、一連の対、すなわち、（Ｉ，Ｔ）から成るようにその領域および入力のための階層的実行トレースを規定する。
ここで、Ｉは、その領域の直ぐ内側のアトミック命令または複合命令であり、また、Ｔは、Ｉが複合命令である場合にはＩに対応する階層的実行サブトレースであり、或いは、Ｉがアトミック命令である場合にはヌル（ＮＵＬＬ）である。
【００８５】
［００１０８］
階層的実行トレースのシーケンスは、特定の入力が与えられた領域により実行されるアトミック命令および複合命令のシーケンスである。階層的実行トレースを平坦化すると、領域および入力のための標準的な（階層的でない）アトミック命令トレースがもたらされる。
【００８６】
［００１０９］
領域は、アトミック命令および複合命令の両方をあたかもそれらが通常のパイプライン化オペレーションであったかのように考慮して、スケジューリングおよびソフトウェアパイプライニングアルゴリズムによってその階層レベルで並列処理され得る。しかし、任意の並列化が以下の規則に従わなければならない。
【００８７】
［００１１０］
本発明者らは、階層的ソフトウェアパイプライニング正確さ規則を述べる。
・所定の入力を伴うプログラム領域の任意の階層的実行トレースに関して、内側プログラム領域が複合命令へと折り畳まれる場合には、階層的実行トレースにおける２つのアトミック命令または複合命令が依存していれば、同じ入力を伴うこのプログラム領域の並列ハードウェア実行中にそれらの命令をリオーダすることができない。
【００８８】
［００１１１］
この規則は、プログラム領域の任意のオリジナル実行トレースにおける全ての依存性が重んじられるようにする。これは、複合命令のインスタンス内で深くネストされ得る２つのアトミック命令のインスタンスが実行中に依存すれば、複合命令も依存しなければならず、また、規則の結果として複合命令がリオーダされず、したがって、アトミック命令のオリジナルインスタンスがリオーダされないからである。そのため、段落［００９８］内の重要な正確さ規則２が満たされる。より良い並列度を引き出すために、階層的ループ実行トレース内のアトミック命令または複合命令の独立インスタンスを任意にリオーダでき或いは並列に実行できる。これを達成するための良好な方法は、複合命令を実行するためにカスタム機能ユニット（有限状態機械）の複数のコピーを形成するとともに、これらのコピーをネットワークに接続して、それにより、階層的ソフトウェアパイプライニング原理によって既に決定付けられるように、最終結果が内側ループ／複合命令を実施するプリミティブパイプラインオペレーション（パイプライン化された乗算演算または除算演算と同様）であるようにすることである。
【００８９】
［００１１２］
したがって、有限状態機械を構成するためのスケジューリング／ソフトウェアパイプライニングアルゴリズムが行うべき全てのことは、階層的ソフトウェアパイプライニング正確さ規則に従うことであり、依存する（場合により複合）命令をリオーダすることではない。
【００９０】
［００１１３］
スケジューリング・ソフトウェアパイプライニングアルゴリズム。
本発明者らは、前述した階層的ソフトウェアパイプライニング原理にしたがって、その内側ループが全て複合パイプラインオペレーション（パイプライン化された乗算演算または除算演算と同様な態様で振る舞う）へと折り畳まれたプログラムの１つのループだけをスケジュールする／ソフトウェアパイプライン化するための問題を減らしてきた。この１つのループは、ソフトウェアパイプライン化された後に周波数最適化された有限状態機械へと変換される必要があり、それにより、そのループのためのスレッドユニット（レジスタ転送レベルのＶｅｒｉｌｏｇモジュールまたは他のＨＤＬモジュール）になる。
【００９１】
［００１１４］
本文書の方法は、最適化されないプログラムを含む任意のシングルスレッドシーケンシャルプログラムで機能するが、最先端のコンパイラ技術を用いて最適化されるプログラムに端を発することが結果の質を向上させる。この好ましい実施形態において、本発明者らは、非常に最適化されたシーケンシャルプログラムから始める。
【００９２】
［００１１５］
１つのループのためのシーケンシャルコードに端を発すると、本発明者らは、Ｖｅｒｉｌｏｇなどのハードウェア記述言語で有限状態機械を得るはずである。これは、
・全てのロード／ストア、重要な算術オペレーション（除算など）、および、内側ループ起動を送受信オペレーションへ変換する、
・ダミー依存性レジスタおよび必要に応じて静止フリップフロップを導入することにより、階層的ソフトウェアパイプライニング正確さ規則にしたがって、場合により複合命令を含む階層的シーケンシャルプログラムにおける全ての必要とされる依存性を表す、
・シーケンシャルコードのソフトウェアパイプライン化バージョンを形成する、
・ソフトウェアパイプライン化されたコードから有限状態機械を形成し、ＦＩＦＯ  Ｉ／Ｏピンインタフェースを含む、Ｖｅｒｉｌｏｇなどのハードウェア記述言語のレジスタ転送レベルのスレッドユニットを出力する、
ことによって達成される。
【００９３】
［００１１６］
ダミーレジスタは、送信または受信オペレーションＯ１と送信または受信オペレーションＯ２との間の依存性（さもなければ存在しない）を形成するために使用されるレジスタである。Ｏ１は、ダミーレジスタを設定するために行われ、また、Ｏ２は、同じダミーレジスタを使用するために行われ、それにより、スケジューラは、Ｏ１がスケジュールされるサイクルの後のサイクルで、Ｏ２を強制的にスケジュールする。しかしながら、ダミーレジスタの内容は使用されないため、ダミーレジスタの幅はゼロである。すなわち、ダミーレジスタはハードウェアレジスタを何ら生成しない。Ｏ１が決して実行されない経路をプログラムがとる場合には、あたかもダミーレジスタが有効な初期値を有したかのように、Ｏ１を待つことなくＯ２を実行できる。
【００９４】
［００１１７］
段落［００７４］付近の先の節において、本発明者らは、静止フリップフロップのハードウェア実装について説明した。ここで、本発明者らは、コンパイラ／スケジューラアルゴリズムによって見られるように静止フリップフロップがどのように振る舞うのかについて説明する。ダミーレジスタと同様に、静止フリップフロップも、フリップフロップを設定する送信オペレーションＯ１とフリップフロップを使用する他の送信オペレーションＯ２との間の順序付けを強制する。しかしながら、ダミーレジスタとは異なり、静止フリップフロップは、Ｏ１のための（一般的には予測できない）待ち時間を課す。すなわち、Ｏ２は、Ｏ１の待ち時間が経過するまで始まることができない。静止フリップフロップは最初は１である。フリップフロップは、送信命令の送り先として使用されるときに、最初に直ちに０に設定され、その後、この送信命令の全ての先のインスタンスによって開始される全てのアクティビティ（内側ループ、内側の内側ループ、ストア、更新、...．を含む）が完了した後に自動的に１になる。この静止フリップフロップを使用する第２の命令は、進行前に、静止フリップフロップが１であるまで待つ。第１の命令の先の起動が存在しなかった場合には、第１の命令の静止フリップフロップが既に１であるため、第２の命令も直ちに進行できる。
【００９５】
［００１１８］
シーケンシャルコードでのメモリへの各ロードオペレーション（以下のｌｏａｄ＿ｓｈｏｒｔ＿ｕｎｓｉｇｎｅｄ命令など）は、以下に示されるようなｋ個（このロードのための予測最小遅延量）の単一サイクル遅延オペレーションを間に伴って、メモリのマスターポートからのロードリクエストおよびアドレスの送信へと変換され、その後、同じマスターポートからのロードレスポンスの受信が続く。
【表６】
0005817032.tif 000007
【００９６】
［００１１９］
送信オペレーションは、ｔ１で戻されるリクエストのための新たなタグを形成しつつ、アドレスレジスタｒａをメモリＭＥＭのネットワークへ送信する。ロードの結果を待っている間、その唯一の目的が送受信間に少なくともｋ個のサイクルの待ち時間を課すことである遅延オペレーションを伴って、タグがレジスタからレジスタ（場合により同じレジスタ，ｔ１）へとコピーされる。既に実行された依存性（アトミックまたは複合）メモリオペレーションによって、送信により使用される随意的なダミー入力レジスタｄ０が設定されてもよく、また、このダミー入力レジスタｄ０は、依存性オペレーションの後に送信が行われるようにするために使用される。随意的な静止フリップフロップｑ０は、既に実行された依存性のアトミックメモリオペレーションまたは複合メモリオペレーション（ストア、または、副次的効果のみのために実行される内側ループなど）によって設定される。送信は、ｑ０を設定する先の命令により開始される全てのアクティビティが完了するまで（すなわち、ｑ０が１であるまで）停滞する。
【００９７】
［００１２０］
前述したように、ロードが完了する前に依存性（アトミックまたは複合）メモリオペレーションが開始されないようにするために、最終的なゼロ幅ダミー結果レジスタｄ１を使用することができる。
【００９８】
［００１２１］
ストア命令（以下のｓｔｏｒｅ＿ｂｙｔｅ命令など）が、メモリ名ＭＥＭ、オペコード、アドレス、および、データを含むストアリクエストの送信へと変換される（対応する受信を伴わない）。ストア命令は、静止フリップフロップ、例えばｑ１を設定する。このストアに依存する任意のオペレーションは、静止フリップフロップｑ１が１になるのを待たなければならない。何もこのループ内でストアに依存しない場合には、ｑ１が必要とされない。送信のための随意的なダミー入力レジスタｄ０は、レジスタ結果を戻す先の依存性メモリロードオペレーションまたは先の依存性内側ループによって設定されてもよい。送信は、先のロード命令または内側ループ命令が完了するまで待つ。送信用の随意的な静止フリップフロップ入力ｑ０は、レジスタ結果を戻さない先のストアまたは先の内側ループによって設定される。この送信は、先のストア命令または戻さない内側ループ命令により開始される全てのアクティビティが完了するまで待つ。なお、送信においては、この送信が依存する先の命令の数に基づき、ゼロ又は１以上の入力ダミーレジスタおよび入力静止フリップフロップが存在してもよい。
【表７】
0005817032.tif 000008
【００９９】
［００１２２］
レジスタ結果を戻すカレントループの内側ループ（以下に示されるｆｏｒループなど）の起動は、ループタスクサブネットワークへのループパラメータの送信（ループのトップに存続してループの内側で使用されるレジスタ）へと変換され、その後に、ｋ個の単一サイクル遅延オペレーションが続き、その後に、逆方向タスクサブネットワークからの内側ループ結果の受信（何らかのループ出口に存続してループの内側で設定されるレジスタ）が続く。なお、内側ループは、条件付きで、異なる出口ポイントから抜け出ることができる。複数の出口ポイントを伴う内側ループの場合には、内側ループがどのように抜け出たのかを含有ループが見つけ出すことができるように、ループ出口条件レジスタの１つを除く全ての値も内側ループから受けられてチェックされなければならない。
【表８】
0005817032.tif 000009
【０１００】
［００１２３］
副次的効果（ストアまたは更新など）だけのために実行されるループは、レジスタを何ら戻さない。この場合、以下に示されるように、対応する受信を伴わない、静止フリップフロップを設定する送信オペレーションで十分である。
【表９】
0005817032.tif 000010
【０１０１】
［００１２４］
この場合も先と同様に、このループ内の他のオペレーションが内側ループに依存しなければ、静止フリップフロップが必要とされない。
【０１０２】
［００１２５］
任意の複合的な多重サイクルオペレーション（整数除算、浮動小数点）は、所定の種類のオペレーションのための専用のネットワークへのリクエストの送信へと変えられ、その後に、ｋ個の遅延オペレーションが続き、その後に、オペレーションの結果の受信が続く。除算などの純粋な算術オペレーションがメモリを何ら設定しない或いは使用しないため、ダミーレジスタまたは静止フリップフロップは必要とされない。これは、以下のｄｉｖｉｄｅ＿ｕｎｓｉｇｎｅｄ命令に関して示される。
【表１０】
0005817032.tif 000011
【０１０３】
［００１２６］
一対のメモリ命令（Ｉ１，Ｉ２）が与えられると、依存性解析アルゴリズムが質問に答えなければならない。ここで、Ｉ１，Ｉ２間のそれぞれは、このループ内に位置し或いはこのループの内側ループのうちのいずれかの内側でネストされ、また、Ｉ１，Ｉ２のうちの少なくとも一方がストアである。すなわち、このループの任意の起動の実行トレース内にはＩ１のインスタンスとＩ２のインスタンスとが存在し、それにより、Ｉ２の前記インスタンスは、Ｉ１の前記インスタンスと同じアドレスを参照するかという質問である。依存性解析アルゴリズムの答えがｍａｙｂｅ（アルゴリズムが答えを知らないことを意味する）またはｙｅｓであれば、このループ内で一対の命令（Ｉ１，Ｉ２）が依存していることが控えめに推測されるべきである。各ロード／ストアのアドレスのための最も簡単な形式の記号表現を形成し且つ記号減算および他の試験を使用して依存性をチェックする記号実行に基づき依存性解析技術を使用してこの答えを得るために、本発明者らは、カレントループインデックスｊを伴うＩ１とカレントループインデックスｊ'を伴うループＩ２との間で（Ｉ１，Ｉ２）に関する依存性チェックを以下の場合のみに制限しなければならない。
・ループボディ内で逆のポスト順序でＩ２がＩ１の後に続く、および、ｊ'＞＝ｊ、または、
・ループボディ内で逆のポスト順序でＩ２がＩ１に先行する、および、ｊ'＞ｊカレントループを取り囲むループのインデックスは、Ｉ１，Ｉ２の両方の記号アドレス表現のインデックスに維持されるが、カレントループの内側ループの任意のインデックスは、Ｉ１，Ｉ２の記号アドレス表現の異なる変数に置き換えられる。
【０１０４】
［００１２７］
先のコンパイラ依存性解析にしたがってこのループ内で（Ｉ１，Ｉ２）が依存しているように、このループまたはその内側ループ内の任意の場所で２つのメモリ命令Ｉ１，Ｉ２が与えられると、依存性が強要される態様は以下の通りである。
・Ｉ１がレジスタ結果を戻さない内側ループＡ内にあり、Ｉ２が内側ループＢ内にある場合、
〇Ｉ１を含む内側ループＡにおける送信オペレーションが静止レジスタｑ１をセットし、また、Ｉ２を含む内側ループＢにおける送信オペレーションがｑ１を使用する。Ｂは、第１のループＡの既に開始された実行の全てが完了するまで、すなわち、ｑ１が１になるまで発行されない。
・Ｉ１がレジスタ結果を戻さない内側ループＡ内にあり、Ｉ２がループの直ぐ内側のロードまたはストアである場合、
〇Ｉ１を含む内側ループＡにおける送信オペレーションが静止レジスタｑ１を設定し、また、ロードまたはストアオペレーションＩ２のための送信オペレーションがｑ１を使用する。したがって、Ｉ２は、第１のループＡが静止するまで発行されない。Ｉ２は、Ａの既に開始された実行が終わるのを待つ。
・Ｉ１がレジスタ結果を戻す内側ループＡ内にあり、Ｉ２が内側ループＢ内にある場合、
〇Ｉ１を含む内側ループＡのレジスタ結果における受信オペレーションがダミーレジスタｄ１を設定するとともに、内側ループＢにおける送信オペレーションがｄ１を使用し、それにより、適切な順序付けが確保される。なお、内側ループＡがレジスタを戻す際には、その内側ループ（Ｉ１を含む）内の全てのメモリオペレーションが既に完了していなければならない。
・Ｉ１がレジスタ結果を戻す内側ループＡ内にあり、Ｉ２がループの直ぐ内側のロードまたはストアである場合、
〇Ｉ１を含む内側ループのレジスタ結果における受信オペレーションがダミーレジスタｄ１を設定するとともに、Ｉ２における送信オペレーションがｄ１を使用し、それにより、適切な順序付けが確保される。なお、内側ループＡがレジスタを戻す際には、その内側ループ（Ｉ１を含む）内の全てのメモリオペレーションが既に完了していなければならない。
・Ｉ１がループの直ぐ内側のストアであり、Ｉ２が内側ループＢ内にある場合、
〇Ｉ１における送信オペレーションが静止フリップフロップｑ１を設定し、また、Ｉ２を含む内側ループＢにおける送信オペレーションは、ｑ１を使用して、Ｉ１の先のインスタンスの全てが静止するのを待つ。
・Ｉ１がループの直ぐ内側のストアであり、Ｉ２がループの直ぐ内側のロードまたはストアである場合、
〇Ｉ１における送信オペレーションが静止フリップフロップｑ１を設定し、また、Ｉ２における送信オペレーションは、ｑ１を使用して、ストアＩ１の先のインスタンスの全てが静止するのを待つ。
・Ｉ１がループの直ぐ内側のロードであり、Ｉ２が内側ループＢ内にある場合、
〇Ｉ１における受信オペレーションがダミーレジスタｄ１を設定し、また、Ｉ２を含む内側ループＢにおける送信オペレーションがｄ１を使用する。Ｂが開始するときには、Ｉ１は既に終わっている。
・Ｉ１がループの直ぐ内側のロードであり、Ｉ２がループの直ぐ内側のストアである場合、
〇Ｉ１における受信オペレーションがダミーレジスタｄ１を設定し、また、Ｉ２における送信オペレーションがｄ１を使用する。Ｉ２が開始するときには、Ｉ１は既に終わっている。
【０１０５】
［００１２８］
推移閉包により示される静止依存性は無視できる。例えば、（Ｉ１，Ｉ２）が静止依存性を有するとともに、（Ｉ２，Ｉ３）が静止依存性を有し、また、Ｉ２が実行される場合に且つその場合にのみＩ３が実行されるとともに、Ｉ１が実行される場合に且つその場合にのみＩ２が実行されれば、任意の静止依存性エッジ（Ｉ１，Ｉ３）を無視できる。これは、Ｉ３が実行されるときにはいつでも、Ｉ２が既に実行されてしまっており、したがって、Ｉ１も既に実行されてしまっているからである。この最適化は、不必要な静止依存性（より小さい論理入力を伴うＡＮＤゲートをもたらす。以下のｍａｉｎＬｏｏｐ例参照）を除去することによってハードウェアを減らすことができる。
【０１０６】
［００１２９］
なお、カレントループ内のメモリ命令の全ての依存性対を検査することにより、先の規則を使用して、１つのループのためのシーケンシャルコードにおけるアトミック命令および複合命令の結果オペランドおよびソースオペランドに対して静止フリップフロップおよびゼロ幅ダミーレジスタを加えることができ、それにより、スケジューリング／ソフトウェアパイプライニングアルゴリズムに備えることができる。
【０１０７】
［００１３０］
最後に、以下の変更は、ループにおけるシーケンシャルコードの初めと終わりとに対してなされる。
・親ループ／領域から次のループ起動リクエストを受けるために、コードがループの初めに加えられる。
・ループがレジスタ結果を戻す場合（ループで設定される非ゼロ幅レジスタがループ出口で存続する）、
〇ループのレジスタ結果をレスポンスメッセージで親ループへ送るために、コードがループの出口に加えられる。このメッセージは、それが送られる前に、カレントループ内の全ての内側ループおよびストアが静止するのを待つ。
・次のループ起動パラメータの受信をカレントループ起動における任意のアクティビティと重ね合わせることができない（さもなければ、外側ループが次の起動パラメータを送るのをカレントループが待つ場合に、また、外側ループがカレントループ起動の結果を受信するのを待つ場合に、デッドロックが生じる可能性がある）。この依存性は、ループ起動結果の最後の送信によって設定され且つループ起動パラメータの最初の受信によって使用されるダミーゼロ幅レジスタによって確保され得る。
【０１０８】
［００１３１］
これは、このときにスケジューリングに備えているシーケンシャルコードの構成のためのアルゴリズムを完了する。
【０１０９】
［００１３２］
複合命令／内側ループ間の依存性を更に明確にするために、１つのループの内側ループ間の依存性を強要するための静止検出回路および静止フリップフロップのオペレーションを実証する例を以下に示す。
【表１１】
0005817032.tif 000012
【表１２】
0005817032.tif 000013
・ここで、ｊ１ループの各インスタンスは、ｊ２ループの論理的に先の全てのインスタンスに依存する。これは、ｊ１ループがＸマトリクス内の任意の位置を読み取ることができるとともに、ｊ２の論理的に先の実行がＸマトリクスを書き込むからである。また、ｊ２ループの各インスタンスは、ｊ１ループの論理的に先の全てのインスタンスに依存する。これは、ｊ２ループがＸマトリクス内の新たな値を（場合により、ｊ１ループにより読み取られた同じ場所に）ストアする前にＸ内の古い値が最初にｊ１ループによって読み取られなければならないからである。ｉループの異なる繰り返しのｊ１ループは互いに依存しない。これは、それらのｊ１ループがＸマトリクスだけを読み取るからである。ｉループの異なる繰り返しのｊ２ループは互いに依存しない。これは、それらのｊ２ループがＸマトリクスの異なる部分を書き込むからである。したがって、ｊ１ループリクエストの送信は、ｊ２ループの静止フリップフロップｑ２でゲート制御され、ｊ２ループリクエストの送信は、ｊ１ループの静止フリップフロップｑ１でゲート制御される。ｉループには他のメモリ依存性が存在しない。
・ループｉの並列実行中に、ｊ２ループの先のインスタンスが開始されて未だ終了されない場合には、ｉループの現在の繰り返しがｊ１ループ（ｔｓｔ１（ｉ）は真である）を実行する。ｊ１ループ起動のためのリクエストの送信は、ｊ２ループの全ての先の起動が静止するまで待ち、それにより、ｊ２ループの全ての先の起動が新たな値をマトリクスＸに書き込んでしまうようにする。
・同様に、ｊ１ループの論理的に先のインスタンスが開始されたが未だ終了されていないときにｊ２ループが呼び出されている場合、ｊ２ループは、ｊ１ループの論理的に先の起動の全てが静止するまで待ち、それにより、これらのｊ１ループがＸマトリクス内の古い値を読み取ってしまうようにする。
・一連のｉループ繰り返しにおいて、ｊ１ループだけが呼び出される場合には、あたかもｊ１ループスレッドユニットアレイがパイプライン化された機能ユニットであったかのように、サイクルごとに最大１回だけ、ディープパイプライン化される態様で、ｊ１ループ起動を発行することができる。同様に、ｊ２ループだけが呼び出される一連のｉループ繰り返しにおいては、あたかもｊ２ループスレッドユニットアレイがパイプライン化された機能ユニットであったかのように、サイクルごとに最大１回だけ、ディープパイプライン化される態様で、ｊ２ループ起動を発行することができる。
【０１１０】
［００１３３］
ここで、本発明者らは、スケジューリング・ソフトウェアパイプライニングアルゴリズムについて説明する。任意の汎用ソフトウェアパイプライニングアルゴリズムを本文書と共に使用できる。この好ましい実施形態において、本発明者らは、主要なスケジューリング技術としてエンハンスドパイプラインスケジューリング（ＥＰＳ）技術［１０］を使用する。これは、ＥＰＳが、リソース制約され、１つのループ内で任意の条件付きブランチおよび条件付き出口を扱うとともに、全ての経路でオペレーションの推測的実行を実施し、したがって、ブランチ予測ミスへの回復力に富むからである。本発明者らは、ここで、段階的な例を用いてＥＰＳアルゴリズムの概要を与える。ＥＰＳの利点は、以下のように、条件付き実行を伴うツリーＶＬＩＷ命令から成るその結果をＶｅｒｉｌｏｇ有限状態機械へと容易に変換できるという点である。
・送受信が導入されて、静止依存性レジスタおよびダミー依存性レジスタが加えられた後、シーケンシャルループプログラムで完全ＥＰＳアルゴリズム（レジスタ割り当て、ピープホール圧縮を含む）を起動する、
・ＥＰＳによりもたらされる条件付き実行を伴う最終ツリーＶＬＩＷから始めて、それぞれのＶＬＩＷツリー命令ごとにＦＳＭ状態を形成する、
・以下の重要な変換アルゴリズムを使用して、ツリーＶＬＩＷ命令プログラムをＶｅｒｉｌｏｇモジュールへ変換する：
〇ツリーＶＬＩＷを介する各経路は、条件コードレジスタの互いに排他的な組み合わせを表す。例えば、
【表１３】
0005817032.tif 000014
〇ツリーＶＬＩＷの各リーフ（例では、Ｌ０のラベルが付される）は、（ｉ）条件レジスタの組み合わせ、（ｉｉ）これらの条件が当てはまるときに実行すべき一組のオペレーション、（ｉｉｉ）ジャンプすべき次のＶＬＩＷラベル、を表す。条件は互いに排他的である。これは、ラベルＬ０が付されたツリーＶＬＩＷの例に関する以下の表に示される。
【表１４】
0005817032.tif 000015
〇このツリーＶＬＩＷは、その後、その内部ｃａｓｅのそれぞれがツリーＶＬＩＷのリーフに対応するＶｅｒｉｌｏｇ  ｃａｓｅｚ命令文へと変換される。ツリーリーフに固有のブール組み合わせ条件が当てはまると（Ｔｒｕｅ）、オペレーションの対応する組が実行され、また、次の状態が、このリーフが分岐する先のＶＬＩＷラベルに対応するＦＳＭ状態に設定される。ツリーＶＬＩＷの各リーフのための条件が互いに排他的であるため、レジスタ転送レベルＶｅｒｉｌｏｇ仕様から合成されるべき更に最適化された状態機械をもたらすことができる合成注釈「ｆｕｌｌ  ｃａｓｅ  ｐａｒａｌｌｅｌ  ｃａｓｅ」（意味：ｃａｓｅの条件が互いに排他的であり、ｃａｓｅが全ての可能性を網羅する）を安全に加えることができる。以下のＶｅｒｉｌｏｇコードは、Ｌ０を含むツリーＶＬＩＷプログラムの変換を示す。
【表１５】
0005817032.tif 000016
条件付き実行［８］をサポートする汎用ツリーＶＬＩＷ機械は、１つのサイクルで各ＦＳＭ状態移行を実行する、任意のツリーＶＬＩＷプログラムを解釈できる有限状態機械インタープリタである。しかし、この文書の場合のようにツリーＶＬＩＷプログラムを直接にハードウェア有限状態機械へと変換することによって、本発明者らは解釈オーバーヘッドを避けることができ、それにより、潜在的に、汎用ツリーＶＬＩＷ機械と比べて、かなりの節電および性能利点がたらされる。
〇有限状態機械において送受信オペレーションがどのように実施されるのかを以下に示す。すなわち、所定の送信ＦＩＦＯインタフェースにおける出力信号ｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔがアサートされ（１に設定され）、また、送信が実行されるべき状態および条件にあるときにだけｏｕｔｐｕｔ＿ｐａｙｌｏａｄ出力バスが正しい値に設定される。送信が実行される状態および条件にあると直ぐに、有限状態機械は、ｏｕｔｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅ入力もアサートされるまで次の状態へ進まない。ｉｎｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅ出力は、このネットワークからの受信が実行されるべき状態および条件にあるときにだけアサートされる。有限状態機械は、ｉｎｐｕｔ＿ｒｅｑｕｅｓｔ入力もアサートされるまで次の状態へ進まず、このときに、データがネットワークから受信される。
【０１１１】
［００１３４］
以下の小さい例は、エンハンスドパイプラインスケジューリング論文［１０］のｐ．８６３、図６（ｃ）から引用される。この例をＶｅｒｉｌｏｇモジュールに変換する方法を示す。
【表１６】
0005817032.tif 000017
【０１１２】
［００１３５］
ＥＰＳにおいては、ループの電流制御フローグラフのエッジの組をカットするｆｅｎｃｅを常に使用することによって、スケジュールされるべきコードが非サイクルにされる。初期のｆｅｎｃｅはループボディの初めに配置される。ＥＰＳの各段階では、ｆｅｎｃｅによりカットされるエッジで空のツリーＶＬＩＷが形成され、また、空のＶＬＩＷから到達可能で且つｆｅｎｃｅと交差しない経路上の準備オペレーションが、空のＶＬＩＷへ移動される。グラフは、コード移動を行いつつ漸進的に変更される。例えば、レジスタが改名されてもよく、また、コード移動の経路を結合するエッジにオペレーションのコピーが形成されてもよい。それぞれの増分ステップは正しい変換である。すなわち、プログラムのセマンティクスは変更されない。ｆｅｎｃｅの空のＶＬＩＷの全てがオペレーションの１回サイクルの相当量および条件付きブランチで満たされると、ｆｅｎｃｅは、新たに形成されたＶＬＩＷの送出エッジへ移動され、ＥＰＳ段階が始まる。ＥＰＳ段階は、繰り返し１からの全てのオペレーションが何らかのＶＬＩＷにおいてスケジュールされるまで続く。入力コードにおけるループ出口および任意の条件付きブランチをＥＰＳによって取り扱うことができる。
【０１１３】
［００１３６］
送信／受信オペレーションを加えた後に得られるシーケンシャルコードが以下に与えられる。
【表１７】
0005817032.tif 000018
【０１１４】
［００１３７］
本発明者らは、以下において、このループのための段階的ＥＰＳスケジューリング［１０］について説明する。以下に示されるように、それぞれが１つのオペレーションを含むツリーＶＬＩＷとして書き換えられるこのコードの主要ループ部分に端を発して、ｆｅｎｃｅは、最初に、ループボディの初めに配置される。ＥＰＳ段階中に使用される条件付き実行を伴うツリーＶＬＩＷは逐次的セマンティクスを有する。すなわち、これらのツリーＶＬＩＷも通常のＲＩＳＣマイクロプロセッサによって正確に実行できる。しかしながら、ツリーＶＬＩＷ内にＥＰＳにより配置されるオペレーションの各グループを全て並列に実行できる。ＥＰＳ段階１、すなわち、ループ繰り返し１では、サイクル１がスケジュールされる。このサイクルでスケジュールされ得る唯一のオペレーションは、以下のように、ｆｅｎｃｅの直後に続くｒ０＝ｆ（ｒ０）である。
【表１８】
0005817032.tif 000019
【表１９】
0005817032.tif 000020
【０１１５】
［００１３８］
ＥＰＳの第２の段階において、ｆｅｎｃｅは、第１のｆｅｎｃｅのＶＬＩＷの送出エッジへと下げられ、また、繰り返し１のサイクル２が、ｆｅｎｃｅと交差することなく今時点で到達可能な繰り返し２のサイクル１（ｌｏｏｐのラベルが付されたＶＬＩＷ）と共にスケジュールされる。最初に、既にｆｅｎｃｅに隣接するｃｃ０＝ｒ０＜Ｃ条件計算がｆｅｎｃｅへと移される。（ｃｃ０）の場合には、繰り返し１のオペレーションをｆｅｎｃｅへと移すことができない。これは、このオペレーションの準備が未だできていないからである。しかし、ｒ０＝ｆ（ｒ０）計算を含む繰り返し２の既にスケジュールされたサイクル１をｆｅｎｃｅへと移すことができる。しかしながら、繰り返し１が抜け出る場合にはｒ０の古い値が依然として存続するため、ｒ０＝ｆ（ｒ０）をそのままｆｅｎｃｅへ移すことは誤りである。そのような移動は上書きｒ０であり、それにより、出口がｒ０の間違った値を見込むからである。新たなレジスタｒ１がｆ（ｒ０）の送り先レジスタとして使用されなければならない。これは、
ｒ０＝ｆ（ｒ０）；
を以下の等価なシーケンス
ｒ１＝ｆ（ｒ０）；
ｒ０＝ｒ１；
へと変えた後に、ｒ１＝ｆ（ｒ０）をｆｅｎｃｅＶＬＩＷへ移すことによって行われる。オペレーションがループエントリの結合ポイントを通り過ぎて移動されている際に、ループエントリエッジでオペレーションｒ１＝ｆ（ｒ０）のコピーが形成される。ここで、ｒ１＝ｆ（ｒ０）オペレーションは、繰り返し２が実行されるか否かが知られる前に繰り返し１内で実行される繰り返し２に属する推測的オペレーションである。すなわち、繰り返し１が抜け出る（推測が誤りである）場合には、この計算が無駄になる。なお、この増分変換の結果として、本発明者らは、ｒ０＝ｆ（ｒ０）の当初の位置に残されてしまった余分なオペレーションｒ０＝ｒ１をもたらした。しかし、この余分なコピーオペレーションは、それが決して並列度を抑制しないという意味において無害であり、トランスペアレントである。すなわち、ｒ０を使用してｒ０＝ｒ１の後に続くオペレーションは、常に、そのオペレーション内でｒ０の使用をｒ１の使用へ改名することにより、ｒ０＝ｒ１を通じて進むことができる。
【表２０】
0005817032.tif 000021
【表２１】
0005817032.tif 000022
【表２２】
0005817032.tif 000023
【表２３】
0005817032.tif 000024
【０１１６】
［００１３９］
ＥＰＳ段階３において、ｆｅｎｃｅは、最後のｆｅｎｃｅのＶＬＩＷの送出エッジへと再び下げられ、その後、繰り返し１のサイクル３、並びに、ｆｅｎｃｅと交差することなく現時点で到達可能な繰り返し２のサイクル２（ｌｏｏｐ＿のラベルが付されたＶＬＩＷ）および繰り返し３のサイクル１（Ｌ１のラベルが付されたＶＬＩＷ）からのオペレーションが一緒にスケジュールされる。ｃｃ０の場合には、繰り返し１のオペレーションの準備が最終的に整い、このオペレーションがｆｅｎｃｅへと移される。その後、繰り返し２からのｒ１＝ｒ０がｆｅｎｃｅへと移される。最後に、繰り返し３からのｃｃ０＝ｒ０＜Ｃおよびｒ１＝ｆ（ｒ０）がｆｅｎｃｅへと移される。定常状態ソフトウェアパイプライニングカーネルがツリーＶＬＩＷＬ２で形成された。これ以上スケジュールされないままの繰り返し１オペレーションがないため、ＥＰＳ段階が終了した。
【表２４】
0005817032.tif 000025
【表２５】
0005817032.tif 000026
【表２６】
0005817032.tif 000027
【表２７】
0005817032.tif 000028
【０１１７】
［００１４０］
その後、以下により、ＥＰＳの結果から、条件付き実行を伴う最後のツリーＶＬＩＷが得られる。
・シーケンシャルＶＬＩＷセマンティクスから、ＶＬＩＷにおける各オペレーションがＶＬＩＷ命令の初めに利用できるレジスタを使用する並列ＶＬＩＷセマンティクスへと変える。
〇例えば、同じＶＬＩＷにおけるｒ０＝ｒ１；ｒ１＝ｆ（ｒ０）がｒ０＝ｒ１；ｒ１＝ｆ（ｒ１）へと変えられ、また、ｒ１＝ｆ（ｒ０）；ｒ０＝ｒ１がｒ１＝ｆ（ｒ０）；ｒ０＝ｆ（ｒ０）へと変えられる。
・これ以上まとめることができなくなるまで、ＶＬＩＷ制御フローグラフにおいて隣接する独立のＶＬＩＷを繰り返し１つにまとめる。これはピープホール圧縮と呼ばれる。
・デッドコード除去とレジスタ割り当てとを行う。
ループ起動パラメータの受信および送信を含む最終結果が以下に示される。
【表２８】
0005817032.tif 000029
【０１１８】
［００１４１］
論文［１０］はＥＰＳの更なる詳細を含む。条件付き実行を伴う最後のツリーＶＬＩＷを使用して、本発明者らは、ここで、Ｖｅｒｉｌｏｇモジュールを発することができる。
【表２９】
0005817032.tif 000030
【表３０】
0005817032.tif 000031
【表３１】
0005817032.tif 000032
【表３２】
0005817032.tif 000033
【０１１９】
［００１４２］
任意の合成技術を使用して、ＥＰＳから得られるＶｅｒｉｌｏｇコードからハードウェアを形成できる。しかし、任意の特定の合成プラットフォームとは無関係に、シーケンシャルシングルスレッドコードからハードウェアを形成するための本発明者らの方法を明確に述べるために、本発明者らは、ここで、ＥＰＳから得られるＶｅｒｉｌｏｇコードのための好ましいハードウェア合成技術について説明する。
・Ｖｅｒｉｌｏｇプログラムにおける割り当ての右側のそれぞれの固有の表現（ｒ１  ｏｐ  ｒ２）ごとに（ｒ１およびｒ２はレジスタである）、１つの機能ユニット（入力がｒ１およびｒ２に直接に関連付けられた状態で機能ｏｐを果たす）のみが形成される。Ｖｅｒｉｌｏｇプログラムにおける右側の（ｒ１  ｏｐ  ｒ２）の複数の発生は、（ｒ１  ｏｐ  ｒ２）を行う唯一のハードウェア機能ユニットをもたらす。
・ワンホットエンコーディングを伴って状態が実施され、この場合、１つのフリップフロップが各状態に割り当てられる。状態移行信号、クロックイネーブル信号、および、マルチプレクサ選択信号がサイクルにおいて早期に利用できる見込みがあるように、サイクルの初めにブール条件レジスタを利用できる。
・各レジスタは、任意のレジスタファイル内にない１つ以上のフリップフロップから形成される。各レジスタのクロックイネーブル信号は、そのレジスタに対してＶｅｒｉｌｏｇコードにおける非ブロッキング割り当てが割り当てられる全ての（状態、条件）対の論理ＯＲである。複数の表現がレジスタｒ１に割り当てられるときには、レジスタの前に、それぞれの別個の表現ｅのためのその選択信号が（状態、条件）対の論理ＯＲである入力マルチプレクサが形成される。この場合、ｅがｒ１に割り当てられる。ｒ１のためのクロックイネーブル信号が誤りである（状態、条件）対は、これらのマルチプレクサ選択信号の論理最適化のために使用されるべき「ｄｏｎ'ｔ  ｃａｒｅ」条件となる。
・組み合わせ１ビット出力信号（送信ＦＩＦＯにおけるｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔまたは受信ＦＩＦＯにおけるｉｎｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅなど）は、前記出力信号が１である（状態、条件）対の論理ＯＲとして得られる。
・組み合わせｏｕｔｐｕｔ＿ｐａｙｌｏａｄバスは、それをＶｅｒｉｌｏｇプログラムにおける複数の想定し得る表現に設定できるときには、その入力が別個の表現であり且つ各表現ｅのためのその選択信号がその表現ｅを前記ｏｕｔｐｕｔ＿ｐａｙｌｏａｄバスに割り当てる（状態、条件）対の論理ＯＲから得られるマルチプレクサを使用して得られる。対応するｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔ信号が誤っている（状態、条件）対は、マルチプレクサ選択信号の論理最適化のために使用されるべき「ｄｏｎ'ｔ  ｃａｓｅ」条件となる。
最適化の節における最適化４は、前述した合成パラダイム内の周波数最適化技術について記載する。
【０１２０】
［００１４３］
生成されたハードウェアを改良するために、以下の改良を当初のエンハンスドパイプラインスケジューリングアルゴリズムに対して行うことができる。
・当初のＥＰＳは、同じツリーＶＬＩＷ内で依存性オペレーション（例えば、その後にａｎｄ  ｒ２＝ｒ１，Ｎが続くｘｏｒ  ｒ１＝ｒ０，ｒ３）を実行できない。改良として、１サイクル（１つのサイクルは、簡単なマルチプレクサおよび３２ビットａｄｄの待ち時間をほぼ保持できる）を超えない複数の依存性オペレーションを同じツリーＶＬＩＷ内に配置できる。この技術は、周知であり、例えば、組み合わせ法（ｃｏｍｂｉｎｉｎｇ）または連鎖法（ｃｈａｉｎｉｎｇ）と呼ばれてきた。
・当初のＥＰＳは最長マッチ（ｇｒｅｅｄｙ）である。すなわち、この当初のＥＰＳは、リソースを利用できる場合には可能な限り早くオペレーションをスケジュールする。レジスタのプレッシャーを減らし、低いサイクル／繰り返しを達成するとともに、有限のリソ−スによりスケジューリングを改善するために、モジュロスケジューリング［２７］における先のオペレーションに類似する方法で、特定のオペレーションのスケジューリングを最短マッチ（ｎｏｎ−ｇｒｅｅｄｙ）にすることができる。すなわち、そのようなオペレーションが所定のサイクルにおいていつでもスケジュールできる状態にある場合であっても、そのスケジューリングを後のサイクルまで延ばすことができる。
【０１２１】
［００１４４］
より複雑な例として、図２１〜図３２において、本発明者らは、ランダムアクセスプログラムの内側ループのＶｅｒｉｌｏｇモジュールへの変換を与える。
・図２１は、更新命令が送信へ変換された後におけるランダムアクセス内側ループのためのシーケンシャルな中間コードおよびＣコードを与える。ｊループのループ起動入力は、受信命令により、外側（ｉ）ループから受信される。ｆｅｎｃｅ（コードを一時的に非サイクルにする）は、ループボディのトップにあり、ＥＰＳアルゴリズムの開始に備える。
・図２２は、エンハンスドパイプラインスケジューリング（ＥＰＳ）段階１の後のランダムアクセス内側ループを示す。ｆｅｎｃｅはラベルＬ１を有する命令にある。
・図２３は、エンハンスドパイプラインスケジューリング（ＥＰＳ）段階２の後のランダムアクセス内側ループを示す。ｆｅｎｃｅはラベルＬ２を有する命令へと下げられた。
・図２４は、エンハンスドパイプラインスケジューリング（ＥＰＳ）段階３（最終段階）の後のランダムアクセス内側ループを示す。ラベルＬ２を有するツリーＶＬＩＷ命令が１繰り返し／サイクルの速度で実行する。
・図２５は、ランダムアクセス内側ループのための最終ツリーＶＬＩＷを示す。
・図２６は、ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール１／７部分（モジュールのＩ／Ｏピン）を示す。
・図２７は、ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール２／７部分（レジスタ宣言）を示す。
・図２８は、ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール３／７部分（その状態が条件付き実行を伴うツリーＶＬＩＷ命令である有限状態機械）を示す。
・図２９は、ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール４／７部分（継続有限状態機械）を示す。
・図３０は、ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール５／７部分（継続有限状態機械）を示す。
・図３１は、ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール６／７部分（有限状態機械、組み合わせＦＩＦＯハンドシェーキング出力）を示す。
・図３２は、ランダムアクセス内側ループのためのＶｅｒｉｌｏｇモジュール７／７部分（メモリネットワークおよび親ループネットワークのための静止検出回路）を示す。更新命令は、リクエストの数が肯定応答の数に等しいときに静止する。この内側ループモジュールは、ＦＳＭが開始（アイドル）状態のときに静止状態になり（ｉｎｐｕｔ＿ｑｕｉｅｓｃｅｄ＝１）、また、既に発行されたメモリへの全ての更新リクエストが完了されてしまっている。この時点で、ＦＳＭは、新たなループ起動リクエストを待ち始める。
【０１２２】
［００１４５］
依存性内側ループＡの論理的に先のインスタンスの静止を内側ループＢがどのように待つのかを詳しく示すために、本発明者らは、ここで、段落［００１３１］で与えられる外側ループ例ｍａｉｎＬｏｏｐのハードウェア実装も提供する。以下は、インデックスｉを有するこの外側ループのためのツリーＶＬＩＷ命令の組である。
【表３３】
0005817032.tif 000034
【表３４】
0005817032.tif 000035
【０１２３】
［００１４６］
ｍａｉｎＬｏｏｐのための以下のＶｅｒｉｌｏｇコードは、静止フリップフロップでの待ちがどのように実施されるのかを示す。例えば、ループｊ２が生み出される以下のＶｅｒｉｌｏｇコードにおける状態Ｓ＿Ｌ２を参照すると、ループｊ２を生み出すためのＬＯＯＰｊ２＿ｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔ信号は、先の依存性内側ループｊ１の静止フリップフロップｑ１に設定される。したがって、ＬＯＯＰｊ２＿ｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔ信号は、静止フリップフロップｑ１が１になるまでアサートされない。また、状態Ｓ＿Ｌ２では、状態移行条件が（ＬＯＯＰｊ２＿ｏｕｔｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅ  ＆＆  ｑ１）として定められる。したがって、Ｓ＿Ｌ２後の次の状態への移行は、静止フリップフロップｑ１が１になる前に生じない。ＦＳＭは状態Ｓ＿Ｌ２でフリーズし、一方、ｑ１は０のままである。静止フリップフロップのための他の待ち要件も同様に扱われる。共有メモリを使用するソフトウェアスレッド同期化技術と比べて、特殊化したハードウェア手法はかなり効率が良い。
【表３５】
0005817032.tif 000036
【表３６】
0005817032.tif 000037
【表３７】
0005817032.tif 000038
【表３８】
0005817032.tif 000039
【表３９】
0005817032.tif 000040
【表４０】
0005817032.tif 000041
【表４１】
0005817032.tif 000042
【表４２】
0005817032.tif 000043
【０１２４】
［００１４７］
静止フリップフロップは、本発明者らが認識すべき以下の問題を有する。すなわち、静止フリップフロップｑ１を設定する内側ループＡが開始されて、その後、内側ループＢがｑ１によって内側ループＡの静止時に待ち始めると、同じ静止レジスタｑ１を再び設定する内側ループＡの新たなインスタンスを開始することができない（Ｂがｑ１に関して依然として読み取っているおよび待っているため、ｗｒｉｔｅ−ａｆｔｅｒ−ｒｅａｄ依存性が存在する）。無論、Ａの新たなインスタンスに関して、本発明者らは、新たな独立した静止回路と異なる静止フリップフロップとを使用できる。すなわち、Ａの新たなインスタンスのためのリクエストメッセージは、Ａの古いインスタンスのためのリクエストメッセージとは異なるタグを有さなければならず、また、このタグは、Ａの新たなインスタンスおよび古いインスタンスから生じるアクティビティの静止を独立に決定できるように、Ａの新たなインスタンスおよび古いインスタンスの全てのサブタスクへ伝搬されなければならない。しかし、ベースラインスーパーコンピュータにおけるハードウェア簡略さを保つために、本発明者らは、単に、以下のように静止フリップフロップ内のｗｒｉｔｅ−ａｆｔｅｒ−ｒｅａｄ依存性を重んじる。すなわち、静止依存性（Ａ，Ｂ）は存在するが依存性（Ｂ，Ａ）が存在しないときにはいつでも、本発明者らは、依存性が対称的になるようにするために、依存性（Ｂ，Ａ）を加える。このようにすると、Ａの古いインスタンスでＢが待っているときにはいつでも、今度はＡの新たなインスタンスがＢを待たなければならない。したがって、Ａの新たなインスタンスは、現時点でＢにより読み取られている／待たれている静止フリップフロップを上書きできない。この問題も、静止検出の代わりに使用され得る更に一般的な同期化技術について記載する、最適化の節における最適化番号２によって解決される。
同じ状態／サイクルにおいて複数のネットワーク送受信を行う方法。
【０１２５】
［００１４８］
同じＦＳＭ状態および条件で２つの送信および／または受信オペレーションが行われているときには、
・正確に１つのデータ転送が各ＦＩＦＯで行われなければならず、および、
・次の状態への移行は、この状態および条件の中で定められる全てのＦＩＦＯ転送が行われるまで待たなければならない。
【０１２６】
［００１４９］
例えば、停滞状態の第１のサイクル中にメモリオペレーション１がｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔをアサートしてｏｕｔｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅを得る一方で、メモリオペレーション２がｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔをアサートするが幾つかのサイクルにわたり肯定応答を得ない（したがって、状態移行を防止する）場合には、第２のサイクルにおいて、同じデータの第２の転送がメモリオペレーション１の送信ＦＩＦＯで生じてはならない。したがって、１つの転送がうまく完了すると直ぐに、メモリオペレーション１の送信ＦＩＦＯで更なる送信が停止されなければならない。
【０１２７】
［００１５０］
この想定し得るエラーを防止するために、本発明者らは、
・それぞれの送信ｆｉｆｏインタフェースのためのｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄフリップフロップ、および、
・それぞれの受信ｆｉｆｏインタフェースのためのａｃｋｎｏｗｌｅｄｇｅ＿ｓａｔｉｓｆｉｅｄフリップフロップ
を使用する。
【０１２８】
［００１５１］
ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄフリップフロップが作動して以下のように使用される。
・ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄフリップフロップがシステムリセット時間にゼロに設定される。
・ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄフリップフロップがゼロであるとともに、このＦＩＦＯで転送が要求されてそれが正に起ころうとしている（ｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔおよびｏｕｔｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅはいずれも１である）が、何らかの他の停滞条件に起因して現在の状態が完了できない場合には、ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄフリップフロップが１に設定される。
・ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄフリップフロップが１であるとともに、その状態内の全ての停滞条件が解消され、それにより、次の状態への移行が可能である場合には、ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄフリップフロップが再びゼロに設定される。
・出ていくｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔが（！ｒｅｑｕｅｓｔ  ｓａｔｉｓｆｉｅｄ）に設定され、したがって、ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄフリップフロップがｏｎの状態で、このＦＩＦＯでの全ての通信が抑制される。
・２つの同時に起こる送信オペレーションの場合には、（ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄ１｜｜ｏｕｔｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅ１）＆＆（ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄ２｜｜ｏｕｔｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅ２）のときに次の状態への状態移行が起こる。３つ以上の同時に起こる送信も同様に扱われる。
【０１２９】
［００１５２］
受信ＦＩＦＯもａｃｋｎｏｗｌｅｄｇｅ＿ｓａｔｉｓｆｉｅｄフリップフロップによって同様に作動する。
【０１３０】
［００１５３］
ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄフリップフロップの目的は、１つの状態内で移行が生じる時点における更なるＦＩＦＯトランザクションを防止するとともに、サイクルの初めに非常に僅かな論理遅延をもってｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔ信号およびｉｎｐｕｔ＿ａｃｋｎｏｗｌｅｄｇｅ信号を送信する（ｏｕｔｐｕｔ＿ｒｅｑｕｅｓｔは、ｒｅｑｕｅｓｔ＿ｓａｔｉｓｆｉｅｄフリップフロップの逆バージョンに接続されて、ワンホット状態フリップフロップおよびその状態内のツリー経路条件によってＡＮＤされる）ことである。
【０１３１】
［００１５４］
受信オペレーション中に、データを受け入れているレジスタｒ１の古い値が、同時送信オペレーションを行う送信ＦＩＦＯのソースでもあり、また、送信ＦＩＦＯが停滞されるが受信ＦＩＦＯが停滞されない場合、送信ＦＩＦＯは、（レジスタｒ１にわたって依存性を妨害する）ｒ１の古い値の代わりにｒ１の新しい値を不正確に送信する場合がある。これを解決するために、コンパイラは、同じ状態および条件内で、送信ＦＩＦＯのソースおよび受信ＦＩＦＯの送り先と同じレジスタを使用することを回避しなければならない。これが可能でない場合には、受信ＦＩＦＯが正にデータをｒ１へ転送しようとしているが、停滞されるｒ１の古い値の同時送信が存在するときにはいつでも、入力データが異なるレジスタｒ１'へ受信されなければならず、また、その後、全ての停滞条件が除去されて次の状態への移行がなされるときに、ｒ１'がｒ１へコピーされなければならない。
【０１３２】
［００１５５］
バラバラの順序でレスポンスを受ける方法。
複数のポートと複数のインターリーブバンクとを伴うメモリネットワークでは、ロードリクエスト０およびロードリクエスト１がその順序で同じポートから送信されてもよいが、ロードリクエスト０がキャッシュミスを引き起こすバンク０へ行ってもよく、また、ロードリクエスト１がキャッシュヒットを引き起こす異なるバンク、例えばバンク３へ行ってもよい。したがって、リクエスト１へのレスポンスは、リクエスト０へのレスポンス前に戻ってもよい。
【０１３３】
［００１５６］
バラバラの順序のレスポンスが可能であるときにいずれのリクエストが応答されているのかを特定できるべく、図１３に記載されるように、リクエストの更なる最下位フィールドとしてタグが加えられる。
【０１３４】
［００１５７］
所定のマスターポートの各タグ番号ｉ＝０，...，ｎ−１ごとに、以下のレジスタが形成される。ここで、ｎは、未解決リクエストの最大数である。
・タグｉ  ｂｕｓｙ  ｆｌｉｐ−ｆｌｏｐ（１ビット）。これは、このタグ番号ｉを伴うリクエストが送信されたがレスポンスが依然として戻らなかった場合に且つその場合に限り１である。
・タグｉ  ｄａｔａ  ｒｅｇｉｓｔｅｒ（マスターポートの受信ＦＩＦＯのペイロード幅に等しいＮビット）。
【０１３５】
［００１５８］
タグの数は、リソース制約に晒されるプリミティブオペレーションのパイプライン深さ（または、内側ループのループ複製カウント）にほぼ等しくなければならない。タグはラウンドロビン順序で使用される。使用すべき次のタグ番号のためのタグｂｕｓｙ  ｆｌｉｐ−ｆｌｏｐが１の状態では、リクエストの送信が停滞される（このタグを使用する最後のリクエストのためのレスポンスが未だ戻らなかったことを意味する）。タグｂｕｓｙ  ｆｌｉｐ−ｆｌｏｐが最終的に０であり、送信リクエストがネットワークによって受け入れられると、送信オペレーションは、次のタグ番号を戻すことによって最終的に成功し、その間に、この送信ＦＩＦＯのためのタグカウンタが、タグの総数を法（ｍｏｄｕｌｏ）としてインクリメントされる。送信および受信がパイプライン化される場合であっても、送信に対応する受信オペレーションは、正しいレスポンスが受けられるようにするために、送信のために使用された同じタグを使用する。
【０１３６】
［００１５９］
タグｘを伴うリクエストに対するレスポンスが目下のマスターポートの受信ＦＩＦＯに到達したときには、そのレスポンスがタグｘデータレジスタへ直ちに受けられるとともに、タグｘビジーフリップフロップが再び０に設定される。
【０１３７】
［００１６０］
このとき、タグｘのための受信オペレーションは、スレッドユニット内の全くローカルなオペレーションになる。受信オペレーション
ｒｅｃｅｉｖｅ  ｒ１＝ＮＷ，ｘ，...
は、タグ番号ｘビジーフリップフロップがゼロであるまで停滞し、その後、送り先レジスタｒ１へのタグｘデータレジスタの内容を受ける。
【０１３８】
［００１６１］
これは、リクエストへのレスポンスがバラバラの順序で戻る場合であっても、そのレスポンスが対応するタグデータレジスタに保存されることを保証する。状態機械が最終的にそのレスポンスを処理するようになる場合及び時に、それをそのタグデータレジスタで利用できる。
【０１３９】
［００１６２］
スレッドユニットは、推測的に副次的効果（ロード、除算などのマルチサイクルオペレーション、或いは更には、内側ループなど）を伴うことなく、すなわち、当初のシーケンシャルプログラム内でリクエストをガードする条件が計算されるのを待つことなく、オペレーションのためのリクエストを送信してもよい。推測的実行は、しばしば、性能を向上させる。推測的実行をサポートするために、メモリシステムは、存在しない或いはさもなければアクセスできないアドレスからロードリクエストを受けるようになっていなければならない。これは、とられていない経路上での推測的なロードが、無効値を含むアドレスとして任意の値にアクセスしようと試みることができるからである。推測的に送られるリクエストが実際のとられた経路上にない場合、対応するレスポンスは、もしあれば、依然としてスレッドユニットにより常に受けられるが、使用されないままでもよい。周波数を維持するために、推測的オペレーションのためのリクエストがスレッドユニットのマスターポートによって送信されると、そのリクエストは、たとえ推測がその後に間違っていると分かる場合であっても、このスレッドユニットによりキャンセルされない。とられていない経路上にある推測的に発行された内側ループネストは、長い時間を要する場合があり、または、終了しない場合さえある。これは、ループ出口条件が不要データに依存する場合があるからである（例えば、その「ループカウント」がＣ＋＋コードにおけるタグ付けされた共用体（ｔａｇｅｄ  ｕｎｉｏｎ）によりもたらされる内側ループが推測的に発行される場合には、その共用体のタグをチェックする前に、「ループカウントフィールド」が実際に何を含んでいるのかは分からない）。したがって、推測的に発行された内側ループネストは、推測が正しいかどうかにかかわらずコンパイラが妥当な時間に終了するであろうと分かり得る内側ループネストに限られるべきである。しかしながら、最適化の節の中の最適化番号８は、この制限を緩和する。
【０１４０】
［００１６３］
タグｘを伴う推測的ロードオペレーションへのレスポンスは、タグｘデータレジスタ内へ常に受け入れられる。しかしながら、とられた経路上にロードがなかったため、レスポンスは使用されないままであってもよい。この場合、同じタグｘデータレジスタは、タグｘが再使用される次の機会に上書きされる。
【０１４１】
［００１６４］
周波数最適化として、受信ＦＩＦＯへ入ってくるレスポンスおよびそのタグは、入ってくるデータのタグをチェックすることなくステージングバッファへ受け入れられ得るとともに、次のサイクルで元の対応するタグデータレジスタへ書き込まれ得る。このポートでの受信オペレーション中にタグデータレジスタが読み取られると、データは、それが依然としてステージングバッファにあってタグデータレジスタに未だストアされない場合には、ステージングバッファからバイパスされる。
【０１４２】
［００１６５］
レスポンスのバラバラの順序の受信は、最小待ち時間に関して１つの余分なサイクルがかかる。
【０１４３】
［００１６６］
この手法は待ち時間許容範囲問題を解決せず、パイプライン化されたレスポンスは、それらが有限状態機械によって送信された順序で依然として処理される。実際に、レスポンスは、時として、依存性に起因して順番に処理されなければならず、例えば、階層的ソフトウェアパイプライニングを用いるパイプライン態様で呼び出される１つのループの内側ループで生じる例外が当初の連続する順序でチェックされなければならない。しかし、レスポンスは任意の順序で到達でき、また、この節に記載されるタグのおかげで、回路が依然として正確に機能する。待ち時間許容範囲問題に対する改善は、この文書における後の最適化番号９で論じられる。
【０１４４】
［００１６７］
アウトオブオーダレスポンスユニットの設計：タグの数（未解決リクエストの最大数）が大きい場合には、フリップフロップおよびレジスタをもはや使用することができない。同様に、入力メッセージが可変長を有するときには、タグデータレジスタがもはや適さない。この場合、１つの考えは、先に与えられたアルゴリズムを真似るマルチポートＳＲＡＭから形成されるサーキュラバッファを使用することである。
【０１４５】
［００１６８］
大型構造の分割。
今や、本発明者らは、ループ／プログラム領域のハードウェアスレッドユニットへの変換を網羅するとともに、トップレベル設計の構成についても説明してきたため、本発明者らは、チップ上に適合しない大型構造を分割する課題に戻ることができる。
【０１４６】
［００１６９］
複数のチップにわたる構造の分割。
階層的ソフトウェアパイプライニングの結果として、内側ループのアレイが、各内側ループが内側ループのそれ自体のアレイを含む場合、各内側ループがそれ自体の内側ループのアレイを含む場合などにおいて、十分な並列度を伴うアプリケーションのために単一チップの面積を急速に満たすことは明らかである。このため、特定用途向けスーパーコンピュータは、複数の通信チップを使用して実施されなければならない。しかしながら、検査および製造のコストを下げるため、チップおよびボード／ラックモジュールは、好ましくは、標準的な均一フォーマットに従うべきであり、チップ間通信機構は、汎用的なスケーラブルネットワーク（この実施形態では、高速シリアル通信ケーブルが実装された不完全ハイパーキューブ）を使用すべきであり、また、チップを横断するメッセージは、好ましくは、カスタムフォーマットではなく標準フォーマットに従うべきである。
【０１４７】
［００１７０］
最初に、トップレベル構造に関する節で説明されたように全てのコンポーネントおよびネットワークが単一のチップ上に適合することを想定するフラット構造が形成される。なお、コンポーネントは、ネットワークのみを介して他のコンポーネントと通信できる。この特性は、分割を容易にするために必要不可欠である。
【０１４８】
［００１７１］
フラット構造におけるメモリ階層「ブラックボックス」スーパーコンポーネントも、該スーパーコンポーネントを分割前にその内部のコンポーネントおよびネットワークへとエクスプロードすることによって、チップにわたって分割できることに留意されたい。
【０１４９】
［００１７２］
ここで、本発明者らは、このフラット構造をハイパーグラフ［３０］と見なす。この場合、ハイパーバーテックスがコンポーネントであり、ハイパーエッジがネットワークである。すなわち、ネットワークは、ハイパーエッジと見なされると、このネットワークが接続するコンポーネント（ハイパーバーテックス）の組である。ソフトウェアプロファイラまたはハードウェアプロファイラから得られるネットワーク通信ボリューム（通信ボリュームは、全てが基本的なプロファイラ−フィードバック統計から利用できる、所定のメモリに関して実行されたロード／ストアの数またはタスクネットワークにわたって通信される全内側ループレジスタパラメータおよび結果の数に比例する）などの発見的ハイパーエッジ重みを使用して、フラット構造ハイパーグラフのコンポーネントは、カットセットエッジ（カットサイズ）の重みを最小限に抑えようと試みつつ且つ各コンポーネント内のそれぞれの種類のリソースのほぼ等しい分配（例えば、４５％−５５％〜５５％−４５％の範囲）を達成しようと試みつつ、複数のチップへと分割される。結果として、各コンポーネントからその分割番号（チップ番号）へマッピングが形成される。
【０１５０】
［００１７３］
カットサイズを最小限に抑えつつ１つのハイパーグラフから２つのほぼ等しいサイズのハイパーグラフを形成するハイパーグラフ二分割アルゴリズム（例えば［３０］）を利用できれば、それを使用して、全てのリソース制約が満たされるまで、１つの構造を必要な数のチップへと再帰的に分割できる。疑似Ｃ＋＋コードにおける再帰的ハイパーグラフ二分割アルゴリズムを以下に示す。
【表４３】
0005817032.tif 000044
【０１５１】
［００１７４］
分割間通信はかなりのエネルギーコストを有する。なお、各再帰的二分割ステップで分割間通信ボリュームを最小にすることにより、先の分割アルゴリズムは、高い通信ボリュームを有するネットワークを分割しないことを好むことによって、特定用途向けスーパーコンピュータの総エネルギー消費量も減らす。
【０１５２】
［００１７５］
最後に、それぞれのネットワークごとに、全てのエンドポイントコンポーネントが同じチップ上にないように、チップＩ／Ｏコントローラにも接続される部分ネットワーク（バタフライサブネットワークまたはタスクサブネットワークからも形成される）が各チップ上に形成される。簡単のため、メッセージは、あたかも構造がフラットであったかのように（送り先ポート＝フラットネットワーク出力ポート番号）コンポーネントにより送られる。部分ネットワークは、当初のフラット構造ネットワークの送り先（マスターまたはスレーブ）ポートを、当該チップ上のローカル部分ネットワークの送り先ポートへと、メッセージがローカル部分ネットワークに入る前に変換するために、カスタムルーティングルックアップテーブルＲＯＭを使用する。余分のローカル出力ポートフィールドがローカルルーティングのためにメッセージの最初のワード（ワードサイズは必要に応じて拡張される）に付加され、その後、ローカルルーティングは、通常の不完全バタフライネットワークオペレーションにより、メッセージを正しいローカル出力ポートへと案内する。
【０１５３】
［００１７６］
各チップ上のＩ／Ｏコントローラコンポーネントの目的は、内部ネットワークメッセージを、メッセージソースコンポーネントを含むチップから、メッセージ送り先コンポーネントを含むチップへと経路付けることである。コンポーネントは、通常、高度にカスタマイズされた特定用途向けネットワークにわたって通信する。カスタマイズされたネットワークＹに付随する全てのコンポーネントを単一のチップ上に配置できない場合、Ｉ／Ｏコントローラは、第１のチップＡ上のコンポーネントがネットワークＹを介してメッセージを第２のチップＢ上のコンポーネントへ送ることができるようにし、それにより、実際には、複数のチップにわたってカスタム特定用途向けネットワークＹが延ばされる。
・第１のチップＡ上のＩ／Ｏコントローラは、ソースコンポーネントからローカル部分Ｙネットワークを介してメッセージを受け入れて、そのメッセージを標準的なフォーマット（送り先チップを示すヘッダワードと、Ｙのためのグローバルネットワークｉｄと、このメッセージがリクエストであるか或いはレスポンスであるかどうかを示すビットとを伴う６４ビットワードを有する可変長メッセージ、および、メッセージの長さ）へ変換するとともに、それを（場合により不完全な）ハイパーキューブネットワークへ向けてチップ外に送る。フォーマット変化は、一般に、ペイロードサイズ変化（幅広−幅狭変換または幅狭−幅広変換）を必要とする。タスクネットワークリクエストは、同じタスクネットワークに付随するコンポーネントを含む次の更に高い番号が付されたチップへ送られる。そのような更に高い番号が付されたチップが存在しないと、リクエストは、このタスクネットワークに付随するコンポーネントを有する最も低い番号が付されたチップへ送られる。チップは、内部でグレイコードナンバリングを使用し、そのため、次の更に高い番号が付されたチップへのメッセージの送信は、ハイパーキューブ上で隣接間通信になる。通常の（非タスク）リクエストは、最長マッチな（ｇｒｅｅｄｙ）決定論的不完全ハイパーキューブルーティングにより、送り先コンポーネントを含む正しいチップへ送られる。
・幾つかのチップのＩ／Ｏコントローラは、途中で、最長マッチな決定論的不完全ハイパーキューブルーティングアルゴリズムを使用して、メッセージが送り先チップＢに到達するまで、不完全ハイパーキューブネットワークにおける正しい次のチップへとメッセージを経路付ける。
・チップＢ上のＩ／Ｏコントローラは、メッセージを受け入れて、ヘッダワードを削除するとともに、メッセージペイロードサイズ変化（ナロー−ワイド変換またはワイド−ナロー変換）によってそのメッセージを元のＹネットワークの当初のカスタマイズされたフォーマットへと変換する。その後、メッセージは、ローカル部分ＹネットワークによってチップＢ上の送り先コンポーネントへ配信される。
【０１５４】
［００１７７］
図３３、図３４、および、図３５は、各分割に関してＩ／Ｏコントローラを含む図１９のランダムアクセスのためのフラット構造によりもたらされる分割を示す。プレゼンテーションを向上させるため、本発明者らは、各分割においてメモリ階層コンポーネントが再び部分スーパーコンポーネントとしてひとまとめにされたと想定することによって、これらの図をメモリ階層の内部実装細部から独立させた。
【０１５５】
［００１７８］
チップ統合によるＮＲＥコストの低減。
ＡＳＩＣの性能利点および電力低減利点の利益を享受するために、ＦＰＧＡを使用することにより特定用途向けスーパーコンピュータを試作できるが、理想的な解決策は、全ての最適化が行われた後に最終的なアクセラレータを形成する際にＦＰＧＡの代わりにＡＳＩＣを使用することである。しかしながら、それぞれの分割ごとに異なるＡＳＩＣを解放することは、おそらく、開発費（マスク費用など）を複数回招く。最終的な分割アルゴリズムは、ほぼ等しい数の所定タイプのコンポーネントを各チップへ分配しようとする。その後、コンパイラは、各ラック上の各ラックモジュール上の各チップに正しい分割を実現させるためにシステム初期化時間に書き込まれる、構造に加えられたコンフィギュレーションレジスタおよびＳＲＡＭの初期値に応じて分割（パーティション）のうちのいずれか１つとしての機能を果たし得る統合チップを形成するために、チップ統合を分割に対して適用できる。コンフィギュレーションＳＲＡＭの初期化は、別個の小型の埋め込み式マイクロプロセッサとシステム内の全てのチップのコンフィギュレーションＩ／Ｏピンに接続される別個のシリアルバスとを用いて行うことができる。コンフィギュレーションＳＲＡＭ／レジスタの初期値に基づき、統合チップは、１つの構造の幾つかの分割（パーティション）のうちの１つとしての機能を果たすことができる。統合チップ内のコンポーネントには、依然として、カスタム論理がＡＳＩＣ構造内に実装され、また、統合チップは、コンフィギュレーションＳＲＡＭにアクセスするための余分な遅延とチップ統合に起因する拡張ネットワークの余分な待ち時間とを受け入れるために再コンパイルされ、したがって、ＡＳＩＣの性能利点は、おそらく、統合チップ内で無傷のままである。
【０１５６】
［００１７９］
スーパーコンピュータのＦＰＧＡプロトタイプとの関連でそのような統合チップを形成すると、全体のＦＰＧＡ合成を減らすことにも役立ち得るとともに、アプリケーション起動時の実装時間およびＦＰＧＡプログラミング時間を減らすことにも役立ち得る。しかしながら、統合ＦＰＧＡチップは、任意の個々の分割よりも多くのリソースを必要とする。
【０１５７】
［００１８０］
チップ統合を説明するために、本発明者らは、当初のフラット構造のコンポーネントをグローバルコンポーネントと名付ける。本発明者らは、当初のフラット構造のネットワークのマスター（スレーブ）ポート番号をグローバルマスター（スレーブ）ポート番号と名付ける。なお、チップ統合後、全てのメッセージは、依然として、フラット構造のグローバルマスターポート番号およびグローバルスレーブポート番号と共に送られる（構造が決して分割されなかったと見せかける）。変換テーブル（統合チップのコンフィギュレーションＳＲＡＭの一部である）は、グローバルマスター（スレーブ）ポート番号を統合チップ上のローカルマスター（スレーブ）ポート番号へと変換して、統合チップの異なるインスタンスで正しいチップ間およびチップ内のルーティングを扱う。以下は、統合チップに特定の分割を実現させるために必要とされる主要なコンフィギュレーションＳＲＡＭ／レジスタである。
【０１５８】
［００１８１］
それぞれの分割ごとに：
・分割内の少なくとも１つのグローバルコンポーネントに接続されるそれぞれの分割されたネットワークごとに、
・グローバルスレーブポート番号−ローカルスレーブポート番号マップ。グローバルスレーブポート番号におけるこのマップの値は、
・所望のグローバルスレーブポート番号がこの分割内にない場合には、Ｉ／Ｏコントローラのローカルスレーブポート番号、および、
・そうでない場合には、このグローバルスレーブポート番号がこの分割内に対してマッピングされたローカルスレーブポート番号。
・グローバルマスターポート番号−ローカルマスターポート番号マップ。グローバルマスターポート番号におけるこのマップの値は、
・所望のグローバルマスターポート番号がこの分割内にない場合には、Ｉ／Ｏコントローラのローカルマスターポート番号、および、
・そうでない場合には、このグローバルマスターポート番号がこの分割内に対してマッピングされたローカルマスターポート番号。
これらのマップは、分割されて統合された構造の異形態の正しいグローバルコンポーネントの正しいポートへとメッセージが経路付けられるようにする。
【０１５９】
［００１８２］
分割にかかわらず：
・それぞれの分割されたネットワークごとに
・そのグローバルスレーブポート番号を含む分割を示すグローバルスレーブポート番号−分割番号マップ。
・そのグローバルマスターポート番号を含む分割を示すグローバルマスターポート番号−分割番号マップ。
これらのテーブルは統合チップＩ／Ｏコントローラによって必要とされ、したがって、該コントローラは、リクエストメッセージまたはレスポンスメッセージを送るための送り先チップを特定することができる。これらのテーブルは、全ての分割に関して同じであり、したがって、統合チップのＲＯＭ内に配置され得る。ｂｌｏｃｋ  ｏｒ  ｃｙｃｌｉｃ分配［３２］などの簡単な通常の分配が分割アルゴリズムによって使用される場合には、ＲＯＭさえも必要とされない。すなわち、この場合には、グローバルポート番号を表すビットストリングのサブストリングから送り先分割番号を得ることができる。
【０１６０】
［００１８３］
それぞれの分割ごとに：
・分割内の少なくとも１つのコンポーネントに接続されるそれぞれの分割されたタスクネットワークごとに、
・このタスクネットワークに接続されるスレッドユニットが存在する次の更に高い分割番号を示す次の分割レジスタ。残りの分割内にこれ以上スレッドユニットが存在しない場合には、次の分割レジスタは、タスクネットワークに接続されるスレッドユニットが存在する最小分割番号を含む。
なお、タスクパラメータメッセージは、それが自由なスレッドユニットを見つけるまで、タスクネットワークに接続される全てのスレッドユニットを通じて移動し、自由なスレッドユニットがどこにも存在しない場合には初めに戻す。分割ｉｄはグレイコーディングを内部で使用し（例えば、２進数分割ｉｄ番号００，０１，１０，１１はグレイコードでは００，０１，１１，１０になる）、そのため、この転送手法は、しばしば、ハイパーキューブにおいて隣接間ルーティングをもたらす。
【０１６１】
［００１８４］
それぞれの分割ごとに：
・この分割において何らかのグローバルコンポーネントがマッピングされるローカルコンポーネントのサブセットをその１ビットが表すローカルコンポーネントプレゼンスマスク。ローカルコンポーネントに関してプレゼンスマスクビットがゼロであると、このローカルコンポーネントに対してグローバルコンポーネントがマッピングされず、その後、この分割では何もされない。漏れ電流を減らすためにこのコンポーネントの電源を切ることができる。
【０１６２】
［００１８５］
図３６は、ランダムアクセスから形成される分割に適用されるチップ統合の結果を示す。所定のタイプのローカルコンポーネントにはシーケンスｉｄＡ，Ｂ，Ｃ，...が与えられ、一方、同じタイプのグローバルフラット構造コンポーネントにはシーケンスｉｄ０，１，２，...が与えられた。図３７および図３８は、各分割を実現するために必要とされるコンフィギュレーションＳＲＡＭの異なる内容を示す。
【０１６３】
［００１８６］
例えば一組の同一のグローバルコンポーネントがコンポーネントタイプを形成するとする。例は、多数回複製される特定の内側ループのためのスレッドユニット、または、多数回複製されるＬ２キャッシュである。
【０１６４】
［００１８７］
統合チップは、以下のようにフラット構造およびその分割から構成される。
・それぞれのコンポーネントタイプｔごとに：
〇任意の分割において生じた所定タイプの最大数のインスタンスを統合チップに形成する。
〇それぞれの分割ごとに、グローバルコンポーネントおよびローカルコンポーネントの次第に増大する番号順で分割内のタイプｔの各グローバルコンポーネントを共通のチップの同じタイプのローカルコンポーネントに対して最長マッチで割り当てるグローバル−ローカルコンポーネントマップを形成する。このマップは、所定の分割においてタイプｔのグローバルコンポーネントのローカルバージョンと呼ばれる。
・なお、タイプｔのローカルコンポーネントは、分割のグローバルコンポーネントがそれにマッピングされない場合には、所定の分割において使用されないままであってもよい。
・統合チップネットワークを形成する。
〇任意の分割において生じたそれぞれのグローバルネットワークごとに、同じネットワークのインスタンスを形成する。
〇Ｉ／Ｏコントローラのインスタンスを形成する。
〇任意の分割で生じた最大数の外部（シリアル）チップ間通信デバイスを形成する。これらの全てのシリアル通信デバイスを１：１ネットワークによりＩ／Ｏコントローラに接続する。
〇それぞれのネットワークｎごとに：
・Ｉ／Ｏコントローラが任意の分割におけるマスターポートによりネットワークｎに接続される場合にも、Ｉ／Ｏコントローラをマスターポートにより統合チップにおけるネットワークｎに対して接続する。
・Ｉ／Ｏコントローラが任意の分割におけるスレーブポートによりネットワークｎに接続される場合にも、Ｉ／Ｏコントローラをスレーブポートにより統合チップにおけるネットワークｎに対して接続する。
したがって、Ｉ／Ｏコントローラには、それがマスター（スレーブ）ポートにより接続されるそれぞれのネットワークごとにローカルマスター（スレーブ）ポート番号０が割り当てられる。
〇統合チップ上のそれぞれのローカルコンポーネントｘごとに：
・ｘが接続されるそれぞれの（分割された或いは分割されない）ネットワークｎごとに、
・ネットワークｎに接続されるコンポーネントｘのそれぞれの内部マスターポートｍごとに、
〇この内部ポートｍを統合チップにおけるローカルネットワークｎの次のローカルマスターポートｍ'に接続する。
・ネットワークｎに接続されるコンポーネントｘのそれぞれの内部スレーブポートｍごとに、
〇この内部スレーブポートｍを統合チップにおけるローカルネットワークｎの次のローカルスレーブポートｍ'に接続する。
これは、統合チップ上におけるローカルコンポーネント、ローカルネットワーク、および、Ｉ／Ｏコントローラの形成および配線を完了させる。それぞれの分割ごとにコンフィギュレーションＳＲＡＭおよびレジスタを形成して統合チップの構造を完成させる。
【０１６５】
［００１８８］
統合チップ上の有限リソースを管理する方法：統合チップは、それぞれのコンポーネントタイプの少なくとも１つのインスタンスを含まなければならない。したがって、それぞれのコンポーネントタイプの含んでいるインスタンスが統合チップ上のリソースを既に超える場合には、コンポーネントタイプの数を増大させる積極的な最適化（カスタマイズされたキャシュを特殊化によって形成するなど）が最も重大なコンポーネントに限定されなければならない。
【０１６６】
［００１８９］
統合チップが標的技術に適合する機会を向上させるため、分割アルゴリズムは、クロス分割通信の容量も最小限に抑えつつ、複数の分割間にわたって等しく、全てのコンポーネントタイプを分割することに高い優先順位を与えなければならない。統合チップは、好ましくは、始めるのに大きな面積を有するべきである。
【０１６７】
［００１９０］
分割後、統合チップは、各分割が単独で適合する場合であっても、標的技術に適合しなくてもよい。例えば、一方の分割が１つのＸコンポーネントと１００個のＹコンポーネントとを含むとともに、他方の分割が１００個のＸコンポーネントと１つのＹコンポーネントとを含み、それにより、統合チップが１００個のＸコンポーネントと１００個のＹコンポーネントとを有し、許容領域を超えるときには、以下のアルゴリズムを適用して、更なる分割により、統合チップ上の大面積に寄与するコンポーネントの有害なグループを破壊することができる。
【表４４】
0005817032.tif 000045
【図１】
0005817032.tif 000046
【図２】
0005817032.tif 000047
【図３】
0005817032.tif 000048
【図４】
0005817032.tif 000049
【図５】
0005817032.tif 000050
【図６】
0005817032.tif 000051
【図７】
0005817032.tif 000052
【図８】
0005817032.tif 000053
【図９】
0005817032.tif 000054
【図１０】
0005817032.tif 000055
【図１１】
0005817032.tif 000056
【図１２】
0005817032.tif 000057
【図１３】
0005817032.tif 000058
【図１４】
0005817032.tif 000059
【図１５】
0005817032.tif 000060
【図１６】
0005817032.tif 000061
【図１７】
0005817032.tif 000062
【図１８】
0005817032.tif 000063
【図１９】
0005817032.tif 000064
【図２０】
0005817032.tif 000065
【図２１】
0005817032.tif 000066
【図２２】
0005817032.tif 000067
【図２３】
0005817032.tif 000068
【図２４】
0005817032.tif 000069
【図２５】
0005817032.tif 000070
【図２６】
0005817032.tif 000071
【図２７】
0005817032.tif 000072
【図２８】
0005817032.tif 000073
【図２９】
0005817032.tif 000074
【図３０】
0005817032.tif 000075
【図３１】
0005817032.tif 000076
【図３２】
0005817032.tif 000077
【図３３】
0005817032.tif 000078
【図３４】
0005817032.tif 000079
【図３５】
0005817032.tif 000080
【図３６】
0005817032.tif 000081
【図３７】
0005817032.tif 000082
【図３８】
0005817032.tif 000083
【図３９】
0005817032.tif 000084
【図４０】
0005817032.tif 000085
【図４１】
0005817032.tif 000086
【図４２】
0005817032.tif 000087
【図４３】
0005817032.tif 000088
【図４４】
0005817032.tif 000089
【図４５】
0005817032.tif 000090
【図４６】
0005817032.tif 000091
【図４７】
0005817032.tif 000092
【図４８】
0005817032.tif 000093
【図４９】
0005817032.tif 000094
【図５０】
0005817032.tif 000095
【図５１】
0005817032.tif 000096
【図５２】
0005817032.tif 000097
【図５３】
0005817032.tif 000098
【図５４】
0005817032.tif 000099
【図５５】
0005817032.tif 000100
【図５６】
0005817032.tif 000101
【図５７】
0005817032.tif 000102
【図５８】
0005817032.tif 000103
【図５９】
0005817032.tif 000104
【図６０】
0005817032.tif 000105
【図６１】
0005817032.tif 000106
【図６２】
0005817032.tif 000107
【図６３】
0005817032.tif 000108
【図６４】
0005817032.tif 000109
【図６５】
0005817032.tif 000110
【図６６】
0005817032.tif 000111
【図６７】
0005817032.tif 000112
【図６８】
0005817032.tif 000113
【図６９】
0005817032.tif 000114
【図７０】
0005817032.tif 000115
【図７１】
0005817032.tif 000116