Source: http://patents.com/us-10063496.html
Timestamp: 2019-04-21 18:43:51+00:00

Document:
4933933 June 1990 Daily et al.
5105424 April 1992 Flaig et al.
5163016 November 1992 Har'El et al.
5355455 October 1994 Hilgendorf et al.
5432785 July 1995 Ahmed et al.
5563003 October 1996 Suzuki et al.
5583990 December 1996 Birrittella et al.
5588152 December 1996 Dapp et al.
5859981 January 1999 Levin et al.
5991308 November 1999 Fuhrmann et al.
6003029 December 1999 Agrawal et al.
6029220 February 2000 Iwamura et al.
6058385 May 2000 Koza et al.
6101181 August 2000 Passint et al.
6108739 August 2000 James et al.
6249902 June 2001 Igusa et al.
6314487 November 2001 Hahn et al.
6674720 January 2004 Passint et al.
6711717 March 2004 Nystrom et al.
6925627 August 2005 Longway et al.
6967926 November 2005 Williams, Jr. et al.
6983461 January 2006 Hutchison et al.
7065730 June 2006 Alpert et al.
7143221 November 2006 Bruce et al.
7318214 January 2008 Prasad et al.
7509619 March 2009 Miller et al.
7693064 April 2010 Thubert et al.
7701252 April 2010 Chow et al.
7724735 May 2010 Locatelli et al.
7725859 May 2010 Lenahan et al.
7808968 October 2010 Kalmanek, Jr. et al.
7957381 June 2011 Clermidy et al.
7973804 July 2011 Mejdrich et al.
8018249 September 2011 Koch et al.
8020163 September 2011 Nollet et al.
8020168 September 2011 Hoover et al.
8050256 November 2011 Bao et al.
8099757 January 2012 Riedl et al.
8261025 September 2012 Mejdrich et al.
8281297 October 2012 Dasu et al.
8312402 November 2012 Okhmatovski et al.
8407425 March 2013 Gueron et al.
8412795 April 2013 Mangano et al.
8438578 May 2013 Hoover et al.
8448102 May 2013 Komachuk et al.
8490110 July 2013 Hoover et al.
8492886 July 2013 Or-Bach et al.
8541819 September 2013 Or-Bach et al.
8543964 September 2013 Ge et al.
8601423 December 2013 Philip et al.
8619622 December 2013 Harrand et al.
8635577 January 2014 Kazda et al.
8661455 February 2014 Mejdrich et al.
8667439 March 2014 Kumar et al.
8705368 April 2014 Abts et al.
8711867 April 2014 Guo et al.
8717875 May 2014 Bejerano et al.
8726295 May 2014 Hoover et al.
8793644 July 2014 Michel et al.
8798038 August 2014 Jayasimha et al.
8819611 August 2014 Philip et al.
2002/0071392 June 2002 Grover et al.
2002/0073380 June 2002 Cooke et al.
2002/0083159 June 2002 Ward et al.
2002/0095430 July 2002 Egilsson et al.
2003/0088602 May 2003 Dutta et al.
2003/0145314 July 2003 Nguyen et al.
2004/0049565 March 2004 Keller et al.
2004/0103218 May 2004 Blumrich et al.
2004/0216072 October 2004 Alpert et al.
2005/0147081 July 2005 Acharya et al.
2005/0203988 September 2005 Nollet et al.
2006/0031615 February 2006 Bruce et al.
2006/0075169 April 2006 Harris et al.
2006/0206297 September 2006 Ishiyama et al.
2006/0209846 September 2006 Clermidy et al.
2006/0268909 November 2006 Langevin et al.
2007/0038987 February 2007 Ohara et al.
2007/0088537 April 2007 Lertora et al.
2007/0118320 May 2007 Luo et al.
2007/0147379 June 2007 Lee et al.
2007/0162903 July 2007 Babb, II et al.
2007/0244676 October 2007 Shang et al.
2007/0256044 November 2007 Coryer et al.
2007/0267680 November 2007 Uchino et al.
2007/0274331 November 2007 Locatelli et al.
2008/0072182 March 2008 He et al.
2008/0126569 May 2008 Rhim et al.
2008/0184259 July 2008 Lesartre et al.
2008/0211538 September 2008 Lajolo et al.
2008/0232387 September 2008 Rijpkema et al.
2009/0037888 February 2009 Tatsuoka et al.
2009/0070726 March 2009 Mehrotra et al.
2009/0122703 May 2009 Gangwal et al.
2009/0172304 July 2009 Gueron et al.
2009/0187716 July 2009 Comparan et al.
2009/0210184 August 2009 Medardoni et al.
2009/0231348 September 2009 Mejdrich et al.
2009/0268677 October 2009 Chou et al.
2009/0285222 November 2009 Hoover et al.
2009/0300292 December 2009 Fang et al.
2009/0307714 December 2009 Hoover et al.
2009/0313592 December 2009 Murali et al.
2010/0158005 June 2010 Mukhopadhyay et al.
2010/0211718 August 2010 Gratz et al.
2010/0223505 September 2010 Andreev et al.
2011/0022754 January 2011 Cidon et al.
2011/0035523 February 2011 Feero et al.
2011/0060831 March 2011 Ishii et al.
2011/0072407 March 2011 Keinert et al.
2011/0085550 April 2011 Lecler et al.
2011/0103799 May 2011 Shacham et al.
2011/0154282 June 2011 Chang et al.
2011/0191774 August 2011 Hsu et al.
2011/0235531 September 2011 Vangal et al.
2011/0302345 December 2011 Boucard et al.
2011/0307734 December 2011 Boesen et al.
2012/0023473 January 2012 Brown et al.
2012/0026917 February 2012 Guo et al.
2012/0079147 March 2012 Ishii et al.
2012/0110106 May 2012 De Lescure et al.
2012/0110541 May 2012 Ge et al.
2012/0155250 June 2012 Carney et al.
2012/0173846 July 2012 Wang et al.
2012/0209944 August 2012 Mejdrich et al.
2013/0028090 January 2013 Yamaguchi et al.
2013/0103369 April 2013 Huynh et al.
2013/0103912 April 2013 Jones et al.
2013/0117543 May 2013 Venkataramanan et al.
2013/0159944 June 2013 Uno et al.
2013/0163615 June 2013 Mangano et al.
2013/0174113 July 2013 Lecler et al.
2013/0179613 July 2013 Boucard et al.
2013/0179902 July 2013 Hoover et al.
2013/0191572 July 2013 Nooney et al.
2013/0219148 August 2013 Chen et al.
2013/0250792 September 2013 Yoshida et al.
2013/0254488 September 2013 Kaxiras et al.
2013/0263068 October 2013 Cho et al.
2013/0268990 October 2013 Urzi et al.
2013/0326458 December 2013 Kazda et al.
2014/0068132 March 2014 Philip et al.
2014/0068134 March 2014 Philip et al.
2014/0092740 April 2014 Wang et al.
2014/0098683 April 2014 Kumar et al.
2014/0112149 April 2014 Urzi et al.
2014/0115218 April 2014 Philip et al.
2014/0115298 April 2014 Philip et al.
2014/0211622 July 2014 Kumar et al.
2014/0254388 September 2014 Kumar et al.
2015/0043575 February 2015 Kumar et al.
2015/0109024 April 2015 Abdelfattah et al.
2015/0159330 June 2015 Weisman et al.
2017/0061053 March 2017 Kumar et al.
2017/0063625 March 2017 Philip et al.
Ababei, C., et al., Achieving Network on Chip Fault Tolerance by Adaptive Remapping, Parallel & Distributed Processing, 2009, IEEE International Symposium, 4 pgs. cited by applicant .
Abts, D., et al., Age-Based Packet Arbitration in Large-Radix k-ary n-cubes, Supercomputing 2007 (SC07), Nov. 10-16, 2007, 11 pgs. cited by applicant .
Beretta, I, et al., A Mapping Flow for Dynamically Reconfigurable Multi-Core System-on-Chip Design, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Aug. 2011, 30(8), pp. 1211-1224. cited by applicant .
Das, R., et al., Aergia: Exploiting Packet Latency Slack in On-Chip Networks, 37th International Symposium on Computer Architecture (ISCA '10), Jun. 19-23, 2010, 11 pgs. cited by applicant .
Ebrahimi, E., et al., Fairness via Source Throttling: A Configurable and High-Performance Fairness Substrate for Multi-Core Memory Systems, ASPLOS '10, Mar. 13-17, 2010, 12 pgs. cited by applicant .
Gindin, R., et al., NoC-Based FPGA: Architecture and Routing, Proceedings of the First International Symposium on Networks-on-Chip (NOCS'07), May 2007, pp. 253-262. cited by applicant .
Grot, B., Preemptive Virtual Clock: A Flexible, Efficient, and Cost-Effective QOS Scheme for Networks-on-Chip, Micro '09, Dec. 12-16, 2009, 12 pgs. cited by applicant .
Grot, B., Kilo-NOG: A Heterogeneous Network-on-Chip Architecture for Scalability and Service Guarantees, ISCA 11, Jun. 4-8, 2011, 12 pgs. cited by applicant .
Grot, B., Topology-Aware Quality-of-Service Support in Highly Integrated Chip Multiprocessors, 6th Annual Workshop on the Interaction between Operating Systems and Computer Architecture, Jun. 2006, 11 pgs. cited by applicant .
Hestness, J., et al., Netrace: Dependency-Tracking for Efficient Network-on-Chip Experimentation, The University of Texas at Austin, Dept. of Computer Science, May 2011, 20 pgs. cited by applicant .
Jiang, N., et al., Performance Implications of Age-Based Allocations in On-Chip Networks, CVA MEMO 129, May 24, 2011, 21 pgs. cited by applicant .
Lee, J. W., et al., Globally-Synchronized Frames for Guaranteed Quality-of-Service in On-Chip Networks, 35th IEEE/ACM International Symposium on Computer Architecture (ISCA), Jun. 2008, 12 pgs. cited by applicant .
Lee, M. M., et al. Approximating Age-Based Arbitration in On-Chip Networks, PACT '10, Sep. 11-15, 2010, 2 pgs. cited by applicant .
Li, B. et al., CoQoS: Coordinating QoS-Aware Shared Resources in NoC-based SoCs, J. Parallel Distrib. Comput., 71 (5), May 2011, 14 pgs. cited by applicant .
Lin, S., et al., Scalable Connection-Based Flow Control Scheme for Application-Specific Network-on-Chip, The Journal of China Universities of Posts and Telecommunications, Dec. 2011, 18(6), pp. 98-105. cited by applicant .
Bolotin, Evgency, et al., "QNoC: QoS Architecture and Design Process for Network on Chip" 2004, 24 pages, Journal of Systems Architecture 50 (2004) 105-128 Elsevier. cited by applicant .
Holsmark, Shashi Kumar Rickard, et al., "HiRA: A Methodology for Deadlock Free Routing in Hierarchical Networks on Chip", 10 pages, (978-1-4244-4143-3/09 2009 IEEE). cited by applicant .
Munirul, H.M., et al., Evaluation of Multiple-Valued Packet Multiplexing Scheme for Network-on-Chip Architecture, Proceedings of the 36th International Symposium on Multiple-Valued Logic (ISMVL '06), 2006, 6 pgs. cited by applicant .
Rajesh BV, Shivaputra, "NOC: Design and Implementation of Hardware Network Interface With Improved Communication Reliability", 7 pages, International Journal of VLSI and Embedded Systems, IJIVES (vol. 04, Article 06116; Jun. 2013). cited by applicant .
Yang, J., et al., Homogeneous NoC-based FPGA: The Foundation for Virtual FPGA, 10th IEEE International Conference on Computer and Information Technology (CIT 2010), Jun. 2010, pp. 62-67. cited by applicant .
Zaman, Aanam, "Formal Verification of Circuit-Switched Network on Chip (NoC) Architectures using SPIN", Oosman Hasan, IEEE .COPYRGT. 2014, 8 pages. cited by applicant .
Benini, Luca, et al., "Networks on Chips: A New SoC Paradigm", IEEE Computers, Soc Designs, pp. 70-78, Copyright 2002 IEEE. 0018-9162/02. cited by applicant .
Sethuraman, Ranga Vemuri Balasubramanian, "optiMap: A Tool for Automated Generation of NoC Architecture Using Multi-Port Routers for FPGAs", IEEE, pp. 1-6, 2006. cited by applicant .
International Search Report and Written Opinion for PCT/US2014/060745, dated Jan. 21, 2015, 10 pgs. cited by applicant .
International Search Report and Written Opinion for PCT/US2014/060879, dated Jan. 21, 2015, 10 pgs. cited by applicant .
International Search Report and Written Opinion for PCT/US2014/060892, dated Jan. 27, 2015, 10 pgs. cited by applicant .
International Search Report and Written Opinion for PCT/US2014/060886, dated Jan. 26, 2015, 10 pgs. cited by applicant .
International Search Report and Written Opinion for PCT/US2013/064140, dated Jan. 22, 2014, 9 pgs. cited by applicant .
International Search Report and Written Opinion for PCT/US2014/012003, dated Mar. 26, 2014, 9 pgs. cited by applicant .
International Search Report and Written Opinion for PCT/US2014/012012, dated May 14, 2014, 9 pgs. cited by applicant .
International Search Report and Written Opinion for PCT/US2014/023625, dated Jul. 10, 2014, 9 pgs. cited by applicant .
International Preliminary Report on Patentability for International Application No. PCT/US2013/064140, dated Apr. 23, 2015, 6 pages. cited by applicant .
Office Action for Korean Patent Application No. 10-2016-7019093 dated Sep. 8, 2016, 3 pages plus 1 page English translation KIPO, Korea. cited by applicant .
Notice of Allowance for for Korean Patent Application No. 10-2016-7019093 dated Dec. 5, 2016, 5 pages. KIPO, Korea. cited by applicant .
International Search Report and Written Opinion for PCT/US2014/037902, dated Sep. 30, 2014, 14 pgs. cited by applicant .
Office Action for Japanese Patent Application No. 2015-535898 dated Oct. 25, 2016, 2 pages English, 2 pages untranslated copy. Japan Patent Office. cited by applicant .
Notice of Grant for Japanese Patent Application No. 2015-535898 dated Jan. 17, 2017, 3 pages, untranslated. Japan Patent Office. cited by applicant .
International Search Report and Written Opinion for PCT/US2014/048190, dated Nov. 28, 2014, 11 pgs. cited by applicant .
Office Action for Japanese Patent Application No. 2016-516030 dated Aug. 30, 2016, 2 pages, Japan Patent Office. cited by applicant .
Decision to Grant for Japanese Patent Application No. 2016-516030 dated Nov. 22, 2016, 3 pages, untranslated, Japan Patent Office. cited by applicant.
1. A method for generating a Network on Chip (NoC), comprising: executing a first process directed to derivation of arrival and departure characteristics of at least one buffer associated with the NoC; executing a second process directed to derivation of at least one buffer depth of the at least one buffer based on the arrival and the departure characteristics and further based on one or more characteristics of the NoC; and generating the NoC based on the at least one buffer depth; wherein the first process is machine learning based process configured to determine arrival rate of packets and drain rate of packets based on an arbitration process of the NoC.
3. The method according to claim 1 further comprising: executing a third process directed to optimize the at least one buffer depth to generate at least one second buffer depth through a first simulation of the NoC in isolation with the at least one buffer associated with the NoC; and executing a fourth process to optimize the at least one second buffer depth to generate at least one third buffer depth through a second simulation of the NoC and at least one system element associated with the NoC; wherein the generating the NoC based on the at least one buffer depth is based on the at least one third buffer depth.
6. The method according to claim 3, wherein the fourth process is configured to: create a probability distribution of the at least one buffer depth for the at least one buffer based on the at least one second buffer depth; conduct one or more second simulations based on a sampling of the probability distribution of the at least one buffer depth; rank the one or more second simulations based on a cost function; and obtain the at least one third buffer depth for at least one buffer from the one or more second simulations ranked upon occurrence of a probability distribution convergence.
8. A system for generation of a Network on Chip (NoC), comprising: a memory coupled to the processor, wherein the memory stores one or more computer programs executable by the processor; wherein the computer programs are executable to: execute a first process wherein the first process derives arrival and departure characteristics of at least one buffer associated with the NoC; execute a second process wherein the second process derives at least one buffer depth of the at least one buffer based on the arrival and the departure characteristics and further based on one or more characteristics of the NoC; generate the NoC based on the at least one buffer depth; wherein the first process is machine learning based process configured to determine arrival rate of packets and drain rate of packets based on an arbitration process of the NoC.
10. The system according to claim 8, wherein the computer programs are further executable to: execute a third process wherein the third process optimizes the at least one buffer depth to generate at least one second buffer depth through a first simulation of the NoC in isolation with the at least one buffer associated with the NoC; and execute a fourth process wherein the fourth process optimizes the at least one second buffer depth to generate at least one third buffer depth through a second simulation of the NoC and at least one system element associated with the NoC; wherein the NoC generated based on the at least one buffer depth is based on the at least one third buffer depth.
13. The system according to claim 10, wherein the fourth process is configured to: create a probability distribution of the at least one buffer depth for the at least one buffer based on the at least one second buffer depth; conduct one or more second simulations based on a sampling of the probability distribution of the at least one buffer depth; rank the one or more second simulations based on a cost function; and obtain the at least one third buffer depth for at least one buffer from the one or more second simulations ranked upon occurrence of a probability distribution convergence.
15. A non-transitory computer readable storage medium storing instructions for executing a process, the instructions comprising: executing a first process directed to derivation of arrival and departure characteristics of at least one buffer associated with the NoC; executing a second process directed to derivation of at least one buffer depth of the at least one buffer based on the arrival and the departure characteristics and further based on one or more characteristics of the NoC; and generating the NoC based on the at least one buffer depth, wherein the first process is a machine learning based process configured to determine arrival rate of packets and drain rate of packets based on an arbitration process of the NoC.
17. The non-transitory computer readable storage medium according to claim 15, the instructions further comprising: executing a third process directed to optimize the at least one buffer depth to generate at least one second buffer depth through a first simulation of the NoC in isolation with the at least one buffer associated with the NoC; and executing a fourth process to optimize the at least one second buffer depth to generate at least one third buffer depth through a second simulation of the NoC and at least one system element associated with the NoC; wherein the generating the NoC based on the at least one buffer depth is based on the at least one third buffer depth.
20. The non-transitory computer readable storage medium according to claim 17, wherein the fourth process is configured to: create a probability distribution of the at least one buffer depth for the at least one buffer based on the at least one second buffer depth; conduct one or more second simulations based on a sampling of the probability distribution of the at least one buffer depth; rank the one or more second simulations based on a cost function; and obtain the at least one third buffer depth for at least one buffer from the one or more second simulations ranked upon occurrence of a probability distribution convergence.
Messages are injected by the source and are routed from the source node to the destination over multiple intermediate nodes and physical links. The destination node then ejects the message and provides the message to the destination. For the remainder of this disclosure, the terms `components`, `blocks`, `hosts` or `cores` will be used interchangeably to refer to the various system components which are interconnected using a NoC. Terms `routers` and `nodes` will also be used interchangeably. Without loss of generalization, the system with multiple interconnected components will itself be referred to as a `multi-core system`.
There are several topologies in which the routers can connect to one another to create the system network. Bi-directional rings (as shown in FIG. 1A, 2-D (two dimensional) mesh (as shown in FIG. 1B), and 2-D Taurus (as shown in FIG. 1C) are examples of topologies in the related art. Mesh and Taurus can also be extended to 2.5-D (two and half dimensional) or 3-D (three dimensional) organizations. FIG. 1D shows a 3D mesh NoC, where there are three layers of 3.times.3 2D mesh NoC shown over each other. The NoC routers have up to two additional ports, one connecting to a router in the higher layer, and another connecting to a router in the lower layer. Router 111 in the middle layer of the example has its ports used, one connecting to the router 112 at the top layer and another connecting to the router 110 at the bottom layer. Routers 110 and 112 are at the bottom and top mesh layers respectively and therefore have only the upper facing port 113 and the lower facing port 114 respectively connected.
FIG. 2A pictorially illustrates an example of XY routing in a two dimensional mesh. More specifically, FIG. 2A illustrates XY routing from node `34` to node `00`. In the example of FIG. 2A, each component is connected to only one port of one router. A packet is first routed over the X-axis until the packet reaches node `04` where the X-coordinate of the node is the same as the X-coordinate of the destination node. The packet is next routed over the Y-axis until the packet reaches the destination node.
The term "wormhole" plays on the way messages are transmitted over the channels: the output port at the next router can be so short that received data can be translated in the head flit before the full message arrives. This allows the router to quickly set up the route upon arrival of the head flit and then opt out from the rest of the conversation. Since a message is transmitted flit by flit, the message may occupy several flit buffers along its path at different routers, creating a worm-like image.
To address the above bandwidth concern, multiple parallel physical NoCs may be used. Each NoC may be called a layer, thus creating a multi-layer NoC architecture. Hosts inject a message on a NoC layer; the message is then routed to the destination on the NoC layer, where it is delivered from the NoC layer to the host. Thus, each layer operates more or less independently from each other, and interactions between layers may only occur during the injection and ejection times. FIG. 3A illustrates a two layer NoC. Here the two NoC layers are shown adjacent to each other on the left and right, with the hosts connected to the NoC replicated in both left and right diagrams. A host is connected to two routers in this example--a router in the first layer shown as R1, and a router is the second layer shown as R2. In this example, the multi-layer NoC is different from the 3D NoC, i.e. multiple layers are on a single silicon die and are used to meet the high bandwidth demands of the communication between hosts on the same silicon die. Messages do not go from one layer to another. For purposes of clarity, the present disclosure will utilize such a horizontal left and right illustration for multi-layer NoC to differentiate from the 3D NoCs, which are illustrated by drawing the NoCs vertically over each other.
The following detailed description provides further details of the figures and example implementations of the present disclosure. Reference numerals and descriptions of redundant elements between figures are omitted for clarity. Terms used throughout the description are provided as examples and are not intended to be limiting. For example, the use of the term "automatic" may involve fully automatic or semi-automatic implementations involving user or administrator control over certain aspects of the implementation, depending on the desired implementation of one of ordinary skill in the art practicing implementations of the present disclosure. Example implementations may also be conducted singularly, or in combination with any other example implementation of the present disclosure, according to the desired implementations.
In the present disclosure the term "buffer depth" and "buffer size" or "buffer depths" and "buffer sizes" are interchangeably used. It may be noted by the person skilled in the art that the terms have similar logical meaning as the storage space provided by a buffer and the terms used throughout the description are provided as examples and are not intended to be limiting.
In another aspect, systems of the present disclosure can also optimally size the buffers before initiating the arbitration process. For instance, in case the input channel works at 100 MHz and output channel works at 400 MHz (i.e. can transfer 4 flits per cycle), and in case the maximum packet size is expected to be 20 flits long, buffer size can be configured by the system, for example, to accommodate/store 16 flits such that by the time the 16 flits are transmitted from the output channel (in 4 cycles), the remaining 4 flits can be buffered in the buffer (at one flit per cycle). In an aspect, in case the speed of a first channel is x, and speed of a second channel is y, where x is less than y, buffer requirement can be defined by ((y-x)*(maximum packet size))/y. Depending on the desired implementation, for a single flit packet, there may be no need of a store-and-forward channel, and the cut-through channel can thereby be maintained. In such an implementation, the traffic flow includes multi-flit packets to configure a channel as a store-and-forward channel. Such arrival and the departure characteristics according to the systems and/or methods according to the present disclosure can be utilized to derive the buffer depth of the buffer for the generation of the NoC.
FIG. 10 illustrates an exemplary flow diagram for optimizing buffer size 1002 in accordance with an example implementation. In the method 1000, design space of function "F" vs. Cost with varying values of buffer depths is explored so as to achieve high performance values for one or more buffers.
FIG. 11 illustrates an example plot obtained for brute force method for optimizing buffer size in accordance with an example implementation. As shown in FIG. 11, parameter "f" represents performance parameter function such as but not limited to latency function, bandwidth function, tradeoff function between bandwidth and cost, etc. decided by the user based on performance requirement from the NoC. The parameter "c" represents the cost of switching element (based on number of buffers).

References: Application No. 10
 Application No. 10
 Application No. 2015
 Application No. 2015
 Application No. 2016
 Application No. 2016