`
`
`
`US010003553B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(12) United States Patent
`US 10,003,553 B2
`(10) Patent No.:
`
`
`
`
`
`
`
`Konda
`
`(45) Date of Patent:
`*Jun. 19, 2018
`
`
`
`
`(54)
`
`
`(71)
`
`(72)
`
`(73)
`
`
`(*)
`
`
`(21)
`
`(22)
`(65)
`
`
`
`(51)
`
`
`(52)
`
`(58)
`
`
`(56)
`
`
`Notice:
`
`
`
`
`OPTIMIZATION OF MULTI-STAGE
`
`
`
`HIERARCHICAL NETWORKS FOR
`
`
`PRACTICAL ROUTING APPLICATIONS
`
`
`
`
`
`
`
`
`Applicant: Venkat Konda, San Jose, CA (US)
`
`
`
`
`
`Inventor: Venkat Konda, San Jose, CA (US)
`
`
`
`
`
`
`Assignee: Konda Technologies Inc., San Jose,
`
`CA (US)
`
`
`
`
`
`
`Subject to any disclaimer, the term of this
`
`
`
`
`
`patent is extended or adjusted under 35
`
`
`
`U.S.C. 154(b) by 107 days.
`
`
`
`
`
`This patent is subject to a terminal dis-
`claimer.
`
`
`
`
`Appl. No.: 15/140,470
`
`
`
`Filed:
`Apr. 28, 2016
`Prior Publication Data
`
`
`
`
`
`
`
`
`US 2016/0261525 A1
`Sep. 8, 2016
`Int. Cl.
`
`H04L 12/933
`
`
`H04L 29/06
`
`US. Cl.
`
`
`CPC
`
`
`
`
`(2013.01)
`
`
`(2006.01)
`
`
`
`
`
`H04L 49/1515 (2013.01); H04L 29/0608]
`
`
`
`
`
`
`(2013.01); H04L 49/109 (2013.01); H04L
`65/4076 (2013.01)
`
`
`
`Field of Classification Search
`
`
`
`
`CPC ............. H04L 49/1515; H04L 65/4076; H04L
`
`
`
`
`
`
`29/06081
`
`
`
`
`
`
`
`
`
`See application file for complete search history.
`References Cited
`
`
`U. S. PATENT DOCUMENTS
`
`
`
`10/1992 Batcher
`5,153,843 A
`
`
`
`
`
`
`............. H04L 12/5601
`9/1994 Cloonan
`5,345,444 A *
`
`
`
`
`
`
`
`370/381
`
`
`
`
`
`
`
`5,451,936 A
`
`
`
`
`5,541,914 A *
`
`
`
`
`5,654,695 A *
`
`
`
`
`6,018,523 A
`
`
`
`6,091,723 A *
`
`
`
`6,185,220 B1
`
`
`
`
`
`
`
`9/1995 Yang et a1.
`
`
`
`
`H04L 49/254
`7/1996 Krishnamoorthy
`
`
`
`
`
`370/427
`
`
`8/1997 Olnowich ........... G06F 13/4022
`
`
`
`
`
`340/223
`
`1/2000 Even
`
`
`
`7/2000 Even ................... H04L 49/1507
`
`
`
`
`
`340/221
`
`2/2001 Muthukrishnan et a1.
`
`
`
`(Continued)
`
`
`OTHER PUBLICATIONS
`
`
`Ronald I. Greenberg. “The Fat-Pyramid and Universal Parallel
`
`
`
`
`
`
`
`
`Computation Independent of wire delay” IEEE Trans. Computers,
`
`
`
`
`
`
`
`43(12):1358-1364, Dec. 1994
`
`
`
`
`
`(Continued)
`
`
`
`
`
`Primary Examiner 7 Rasheed Gidado
`
`
`
`
`
`
`
`
`
`ABSTRACT
`
`
`
`(57)
`
`
`
`
`
`
`
`Significantly optimizcd multi-stagc networks, useful in wide
`
`
`
`
`
`
`
`
`target applications, with VLSI layouts using only horizontal
`
`
`
`
`
`
`
`
`
`and vertical links to route large scale sub-integrated circuit
`
`
`
`
`
`
`
`
`
`
`blocks having inlet and outlet links, and laid out
`in an
`
`
`
`
`
`
`
`integrated circuit device in a two-dimensional grid arrange-
`
`
`
`
`
`
`
`
`ment of blocks are presented. The optimized multi—stage
`
`
`
`
`
`
`
`
`
`networks in each block employ several rings of stages of
`
`
`
`
`
`
`
`
`switches with inlet and outlet links of sub-integrated circuit
`
`
`
`
`
`
`
`
`
`blocks connecting to rings from either left-hand side only, or
`
`
`
`
`
`
`
`
`
`
`
`from right-hand side only, or from both left-hand side and
`
`
`
`
`
`
`
`
`
`right-hand side; and employ shuffle exchange links where
`
`
`
`
`
`
`
`
`
`
`outlet links of cross links from switches in a stage of a ring
`
`
`
`
`
`
`
`
`
`in one sub-integrated circuit block are connected to either
`
`
`
`
`
`
`
`
`
`inlet links of switches in the another stage of a ring in the
`same or another sub-integrated circuit block.
`
`
`
`
`
`
`
`
`
`
`
`20 Claims, 19 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 1 of 47
`
`FLEX LOGIX EXHIBIT 1006
`
`Page 1 of 47
`
`FLEX LOGIX EXHIBIT 1006
`
`
`
`
`
`
`US 10,003,553 B2
`Page 2
`
`
`
`(56)
`
`
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`
`
`6,335,930 B1 *
`1/2002 Lee ....................... H04L 49/101
`
`
`
`
`
`
`
`
`
`370/387
`
`
`6,469,540 B2 * 10/2002 Nakaya ............ H03K 19/17728
`
`
`
`
`
`
`
`
`
`326/38
`
`6,940,308 B2
`9/2005 Wong
`
`
`
`
`
`
`
`7,440,449 B2 * 10/2008 Carson ...................... G06T 7/20
`
`
`
`
`
`
`
`
`257/499
`
`
`8,170,040 B2
`5/2012 Konda
`
`
`
`
`
`
`
`8,269,523 B2
`9/2012 Konda
`
`
`
`
`
`
`
`8,270,400 B2
`9/2012 Konda
`
`
`
`
`
`
`
`8,363,649 B2
`1/2013 Konda
`
`
`
`
`
`
`
`8,898,611 B2
`11/2014 Konda
`
`
`
`
`
`
`
`9,374,322 B2
`6/2016 Konda
`
`
`
`
`
`
`
`9,529,958 B2
`12/2016 Konda
`
`
`
`
`
`
`
`H04L12/437
`2003/0117946 A1*
`6/2003 Fontana
`
`
`
`
`
`
`
`
`
`370/216
`
`
`2011/0037498 A1*
`2/2011 Konda ................ G06F 17/5077
`
`
`
`
`
`
`
`
`326/41
`
`2012/0269190 A1* 10/2012 Konda ................ G06F 17/5054
`
`
`
`
`
`
`
`
`370/388
`
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`Hypertree: A Multiprocessor Interconnection Topology , by James
`
`
`
`
`R. Goodman and Carlo H Sequin, Computer Science Technical
`
`
`
`
`
`
`
`Report #427, Dept , of EECS, University of California.
`
`
`
`
`
`
`
`Data Movement Techniques for the pyramid computer, Russ Miller
`
`
`
`
`
`
`
`
`and Quentin F. Stout, SIAM Journal on Computing. vol. 16. No. 1,
`
`
`
`
`
`
`
`
`pp. 38-60, Feb. 1987.
`
`
`
`
`C. Clos, "A Study of Non-Blocking Switching Networks," Bell
`
`
`
`
`
`
`
`
`System Technical Journal, 32:406-424, 1953
`
`
`
`
`
`
`
`A. DeHon, “Balancing Interconnect and Computation in a
`
`
`
`
`
`
`
`
`
`Reconfigurable Computing Array,” ACM Int. Symp. on FPGA, pp.
`
`
`
`
`
`
`69-78, Feb. 1999.
`
`
`
`Chihming Chang, Rami Melhem, “Arbitrary Size Benes Networks”,
`
`
`
`
`
`
`
`
`Journal: Parallel Processing LettersiPPL , vol. 7, No. 3, pp.
`
`
`
`
`
`
`
`
`279-284, 1997.
`
`
`
`Hoda El-Sayed and Abdou Youssef; “The r-truncated Benes Net-
`
`
`
`
`
`
`
`
`
`works and their Randomized Routing Algorithms”1997 Intl Conf on
`
`
`
`
`
`
`
`
`
`Parallel and Dist Sys, Seoul, Korea, Dec. 1997.
`
`
`
`
`
`
`
`
`Guy Lemieux and David Lewis, “Using Sparse Crossbars within
`
`
`
`
`
`
`
`
`
`LUT Clusters”, Procds of the ACM/SIGDA Intl Symp on Field Prog
`
`
`
`
`
`
`
`
`
`
`Gate Arrays 2001, Feb. 11-13, 2001, Monterey, CA.
`
`
`
`
`
`
`
`P. Manuel, W. K. Qureshi, A. William, A. Muthumalai, “VLSI
`
`
`
`
`
`
`
`
`layout of Benes networks,”, J. of Discrete Math. Sci. & Cryptog-
`
`
`
`
`
`
`
`raphy, vol. 10, No. 4, pp. 461-472. 2007.
`
`
`
`
`
`
`
`
`Quinn, Michael J, “Parallel Computing Theory and Practice”, 2nd.
`
`
`
`
`
`
`
`
`ed., 1994, McGraw Hill Series in computer Science, Networks, and
`
`
`
`
`
`
`
`
`
`parallel computing, ISBN 0-07-051294-9.
`
`
`
`
`A. DeHon, “Unifying Mesh- and Tree-Based Programmable Inter-
`
`
`
`
`
`
`
`
`
`connect,” IEEE Trans. on Very Large Scale Int. Systems, vol. 12,
`
`
`
`
`
`
`
`
`
`
`
`No. 10, pp. 1051-1065, Oct. 2004.
`
`
`
`
`
`
`
`Guy Lemieux and David Lewis. Analtyical framework for switch
`
`
`
`
`
`
`
`
`
`block design. In Int‘/. Conference on Field Programmable Logic
`
`
`
`
`
`
`
`and Applications, pp. 122-131, Sep. 2002.
`
`
`
`
`
`
`
`
`Chen, G; Lau, FCM, “A tight layout of the cube-connected cycles”,
`
`
`
`
`
`
`
`
`The 4th International Conference on High Perf. Computing,
`
`
`
`
`
`
`
`
`Bangalore, India, Dec. 18-21, 1997, p. 422-427.
`
`
`
`
`
`
`
`Michael Shyu, Yu-Dong Chang, Guang-Ming Wu, and Yao-Wen
`
`
`
`
`
`
`
`
`
`
`Chang, Generic 1miversal switch blocks. IEEE Transactions on
`
`
`
`
`
`
`
`
`Computers,49(4):348-359. Apr. 2000.
`
`
`
`
`
`Y. Yamada, et. al. . “Folded Fat H-Tree: an interconnection topology
`
`
`
`
`
`
`
`
`for Dynamically Reconfigurable Processor Array”, Embed and
`
`
`
`
`
`
`
`Ubiq. Cmpting, Intl Conf. EUC 2004.
`
`
`
`
`
`
`A. DeHon. Balancing Interconnect
`and Computation in a
`
`
`
`
`
`
`
`
`Reconfigurable Computing Array (or, why you don’t really want
`
`
`
`
`
`
`
`
`100% LUT utili). In Proc. of intl. symp. on FPGAs, Feb. 1999.
`
`
`
`
`
`
`
`
`Andre DeHon. Compact, Multilayer Layout for Butterfly Fat-Tree.
`
`
`
`
`
`
`
`In Twelfth Annual ACM Symposium on Parallel Algs and Archi-
`
`
`
`
`
`
`
`
`
`
`tectures (SPAA 2000), pp. 206-215, Jul. 9-12, 2000.
`
`
`
`
`
`
`
`
`V. P Roychdowdhury et. al., “Segmented Channel Routing,” IEEE
`
`
`
`
`
`
`Trans on Computer-Aided Design of Integrated Circuits and Sys-
`
`
`
`
`
`
`
`
`tems, vol. 12, No. 1, pp. 79-95, Jan. 1993.
`
`
`
`
`
`Ivo Dobbelaere, Mark Horowitz, and Abbas E1 Gamal. Regenera-
`
`
`
`
`
`
`
`
`tive feedback repeaters for programmable interconnections. IEEE
`
`
`
`
`
`
`
`Journal of Solid-State Circuits, 30(11), 1995.
`
`
`
`
`
`
`F. Petrini et. al., k-ary n-trees: High performance networks for
`
`
`
`
`
`
`
`
`
`massively parallel architectures,
`in: Proceedings of the 11th Intl
`
`
`
`
`
`
`
`
`
`Parallel Proc. Symp. . IPPS’97, pp. 87-93.
`
`
`
`
`
`
`P.Pande et al. “Evaluation of MP—SoC Interconnect Architectures: a
`
`
`
`
`
`
`
`Case Study”, Proceedings of 4th IWSOC, Bantf, Alberta, Canada,
`
`
`
`
`
`
`
`
`Jul. 19-21, 2004.
`
`
`
`Yeh, C.-H., Varvarigos, E.A., Parhami, B.: Multilayer VLSI layout
`
`
`
`
`
`
`for interconnection networks.
`In: Proc.
`Intl. Conf. on Parallel
`
`
`
`
`
`
`
`
`
`Processing, 2000‘
`
`
`M. Lin. A. El Gamal, “A Low-Power Field-Programmable Gate
`
`
`
`
`
`
`
`
`
`Array Routing Fabric,” IEEE Transactions on Very Large Scale
`
`
`
`
`
`
`
`
`Integration, vol. 17, No, 10, pp. 1481-1494, Oct. 2009.
`
`
`
`
`
`
`
`
`Avior, A et. al., A Tight Layout of the Butterfly Network. Proc. 8-th
`
`
`
`
`
`
`
`Annual ACM Symp. on Parallel Alg. and Arch. (SPAA ’96), ACM
`
`
`
`
`
`
`
`
`
`
`Press Ed., 1996, pp. 170-175.
`
`
`
`
`
`
`A. El Gamal et. al., “An Architecture for Electrically Configurable
`
`
`
`
`
`
`
`Gate Arrays,” IEEE Jrnl of Solid-State Circuits, vol. 24, No. 2, pp.
`
`
`
`
`
`
`
`
`394—398, Apr. 1989.
`
`
`
`
`Vaughn Betz et. al., Directional bias and non-uniformity in FPGA
`
`
`
`
`
`
`
`
`global routing architectures In IEEE/ACM Intlt Conference on
`
`
`
`
`
`
`
`
`Computer-Aided Design, pp. 652-659, san jose, 96.
`
`
`
`
`
`
`
`
`W. Tsu et. al., “HSRA: High-Speed, Hierarchical Synchronous
`
`
`
`
`
`
`
`
`
`Reconfigurable Array,” in Procds. of the Intl. Symp. on Field-
`
`
`
`
`
`
`
`
`
`
`Progrannnable Gate Arrays, Feb. 1999, pp. 125-134.
`
`
`
`
`
`
`
`
`Andre DeHon. Rent’s Rule Based Switching Requirements.
`In
`
`
`
`
`
`
`
`
`System-Level Interconnect Prediction (SLIP 2001), pp. 197-204,
`
`
`
`
`
`
`
`
`
`Mar. 31-Apr. 1, 2001.
`
`
`
`
`Guy Lemieux et.al., Generating highlyroutablesparse crossbars for
`
`
`
`
`
`
`PLDs. In ACMISIGDA Int’l. Symposium on Field Programmable
`
`
`
`
`
`
`
`Gate Arrays, pp. 155-164, Monterey, CA, Feb. 2000.
`
`
`
`
`
`
`
`
`S. Sivaswamy et. al., “HARP: hard-wired routing pattern FPGAs”,
`
`
`
`
`
`
`
`
`FPGA’05, Monterey, California, USA, Feb. 20-22, 2005.
`
`
`
`
`
`
`Yeh, C.-H., E.A. Varvarigos, and B. Parhami, “Efficient VLSI
`
`
`
`
`
`
`
`layouts of hypercubic networks,” Proc. Symp. Frontiers of Mas-
`
`
`
`
`
`
`
`
`sively Parallel Computation, Feb. 1999.
`
`
`
`
`
`Bhatt. S. N. and Leighton, F. '1'. 1984. A framework for solving VLSI
`
`
`
`
`
`
`
`
`graph layout problems. J. Comput. Syst, Sci. 28, 300-343.
`
`
`
`
`
`
`
`
`
`
`
`* cited by examiner
`
`Page 2 of 47
`
`Page 2 of 47
`
`
`
`
`U.S. Patent
`
`
`
`
`Jun. 19,2018
`
`
`
`
`
`Sheet 1 0f 19
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ring1,Stage"m“
`
`‘ECDCDa:u
`a)
`F"m
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ring2,Stage‘n-1"
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`100 ‘T
`.ED:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG.1A
`
`Page 3 of 47
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` Ring1,Stage1 Ring2,Stage1
`
`
` Ring1:Stage0
`Ring2,Stage0
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Computational
`Block
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5012.2)
`
`
`
`
`Page 3 of 47
`
`
`
`U.S. Patent
`
`
`
`
`
`
`Jun.19,2018
`
`
`
`Sheet2 0f19
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 4 of 47
`
`Page 4 of 47
`
`
`
`
`U.S. Patent
`
`
`
`
`Jun. 19,2018
`
`
`
`
`
`Sheet 3 0f 19
`
`
`
`
`US 10,003,553 B2
`
`FIG. 2A
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`20
`
`2A
`
`
`
`Fo(l\<,2m+1)
`
`:
`
`Ri(k,2m+1)
`
`2,)
`<
`
`
`Fo(_k,2m+2)
`/ \
`
`Ri(|§,\2m+2)
`
`\-)
`<\\
`
`
`Ui(k,>2m+1) B0(k,2m+1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ui(k,§m+2) Bo(k.2mf2)
`
`
`
`
`
`
`
`
`FIG. 2B
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`20 B
`
`
`
`
`Fo(k,2m+1)
`9‘
`
`
`F0(k,2m+2)
`
`/ j
`
`
`
`
`Ui(l§,2m+‘l)
`
`Ui(_|:<,2m+2)
`
`
`
`
`
`Bi(K,2m+1)
`
`
`
`20 C
`
`Fo\(k,2m+1)
`
`//‘
`
`Fq(k,2m+2)
`
`/»
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`20 D
`
`
`
`
`Fo(}<,2m+1)
`
`
`Fo{k,2m+2)
`
`
`
`
`
`
`Fi(k,2m_+\j)
`
`
`Fi(k.2mf?)
`
`Page 5 of 47
`
`Page 5 of 47
`
`
`
`
`U.S. Patent
`
`
`
`
`Jun. 19,2018
`
`
`
`
`
`Sheet 4 0f 19
`
`US 10,003,553 B2
`
`
`
`
`
`FIG. 2E
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`>
`
`
`
`Ri(k,2m+1)
`
`
`Ri(k,2m+2)
`
`
`Bo(k,2m+1)
`
`T>
`
`B0(k,2m+2)
`
`
`Page 6 of 47
`
`Page 6 of 47
`
`
`
`U.S. Patent
`
`
`
`
`
`
`Jun. 19, 2018
`
`
`
`Sheet 5 0f 19
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`Rl(:<.2p+1)
`
`/‘
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bo(x,2p+3)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Hup(1,1)fl\
`
`Hop(2,1)/A‘
`
`
`
`
`
` Ring My") Stage “q"
`
`
`
`
`
`FD(y,2q+1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ring “X”, Stage up”
`
`
`
`
` Ring “x”, Stage “p+1 "
`
`
`
`Fo(x,2p+1)
`
`
`
`
`
`
`
`RKX’ZPW MHI
`I‘dHI FMXYZW}
`
`
`
`
`
`.I Mll Uiogzpfi»
`7
`l
`E
`W)"a".
`
`
`Bu(x,2p+2)1
`
`
`
`
`
`
`
`F9(x,2p+4)
`
`
`\\
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 7 of 47
`
`Page 7 of 47
`
`
`
`
`U.S. Patent
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 6 0f 19
`
`
`
`
`
`FIG. 3B
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
` Ring “)6, Stage “p”
`Ring “x', Stage “p+1”
`
`
`
`
`RI(_X,2p+’|)
`
`
`
`F0(x,2p+3)
` F0(x,2p+1)
`R'(X=2p+3)_
`,/
`
`
`
`
`
`
`m)
`
`
`
`T
`-
`.2 +4
` Ri(X29%)Z
`
`
`
`
`
`
`Fo(x.2p-2)
`00“ p,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`F9(x,2p+4)
`
`
`Ui(_)(‘2p+3)
`
`
`
`
`
`
`
`
`
`
`
`
`Um: 2p+4)
`A
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`)
`
`
`
`Ring “”,y Stage “q+1"
`Ring “y", Stage “q"
`
`
`
`
`
`
`Ri(_y,2q+1)
`»\fii(y,2c+3)
`
`
`
`
`
`
`W
`Bo(y,2q+4)\/E
`l
`.
`JI<_v.2q+3)
`
`Bo(y,2q+3)
`l E L4
`
`
`,2“Na+3
`
`
`
`F(iHb‘
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fo(y.2q+3)
`
`
`
`
`
`
`)
`
`
`
`(_—.
`
`
`
`
`
`\ yopmz)
` Hop(1,1)/\"
`
`
`, 39mm
`Hop(2.1}/“-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 8 of 47
`
`Page 8 of 47
`
`
`
`U.S. Patent
`
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 7 0f 19
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`FIG. 4
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bo(x,2p+3)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bo(x,2p+2)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fo(y,2q+3)
`
`
`
`
`
`
`
`
`
`
`Afl'+5
`N.
`3o
`'33
`
`
`
`
`
`
`
`
`
`
`
`Fo(y,2q+4)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 9 of 47
`
`Page 9 of 47
`
`
`
`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 8 0f 19
`
`US 10,003,553 B2
`
`
`
`
`
`FIG. 5
`
`
`
`
`
`Ring x Stage p
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bo(x,2p+1)
`
`U0(x,Zp+ )
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`“X2p+2)W
`
`
` (wBo(x,2p+2)
`
`
`
`
`
`
`
`MEI llllfflrigll
`00'20%
`Uo(yan:
`
`
`pawl
`
`E300,2q+4)E— g E+33
`
`
`
`
`Hop(1,1)’"\
`
`Hop(2,1)’fl‘
`
`
`\ fi0p(1,2)
`
`Hop(2,2)
`
`
`Ring ‘",y Stage “q"
`
`
`
`Ringy" Stageq+"1
`
`
`
`
`
`
`
`
`
`
`
`
`Bow2q+1)U
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`500!2W3)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`F0(y.2q+3)
`
`
`Fo(y,2q+4)
`
`
`Ui(y,2q+3)
`)
`
`
`
`
`
`
`
`
`
`Page 10 of 47
`
`Page 10 of 47
`
`
`
`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 9 0f 19
`
`US 10,003,553 B2
`
`
`
`
`
`FIG. 6
`
`
`
`
`
`
`
`
`Ring “)("a Stage 0in
`
`
`U§o(x,2p+1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EO(X,2p+2)
`
`
`
`
`
`
`
`
`
`Ring “y", Stage “(1+1 ..
`
`
`
`
`MHII F0(y,2q+4)
`U00,20]“)
`|Ui(Y.201+3)
`U0((Y2q+3%
`
`)BDQ,2q+3)
`Bo(y2q+1)
`
`
`Piiflégfllll Hip.“
`
`
`
`
`LE“)?09
`
`
`
`Ring “y", Stage 1qu
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`B°(y,2q+2)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`F00(v.2q+3)
`
`
`
`
`
`
`
`
`Page 11 of 47
`
`Page 11 of 47
`
`
`
`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`Sheet 10 0f 19
`
`
`
`
`US 10,003,553 B2
`
`
`FIG. 7
`
`
`‘9”
`
`
`
`L1 V1 U1 H1 K1 L2
`
`$MW¥
`
`
`
`
`
`
`
`
`
`NZMMM
`
`
`
`
`
`
`
`
`L1 V3 U3 L2 H3 K3 V5
`
`Stages in 1st Ring
`
`
`
`
`
`
`
`
`
`Stages in 2'"d Ring
`
`
`
`
`
`
`
`Page 12 of 47
`
`Page 12 of 47
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`
`
`Jun.19,2018
`
`
`
`
`
`Sheetll 0f19
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`w.Umm
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`xuo_m_
`
`
`
`Page 13 of 47
`
`Page 13 of 47
`
`
`
`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`Sheet 12 0f 19
`
`
`
`
`US 10,003,553 B2
`
`FIG. 9A
`
`
`
`90
`
`
`
`Fi(k,2in+1)
`
`‘)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fo(k,2m+1)
`
`\
`
`
`
`
`Fi(k,2m+1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ui(k,2m+1)
`
`
`B0(k,2m+_1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`YFi(lg,2m+1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`YURk,2m+1)
`
`Bo(k,2m+2_)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bo(k,2m§-1)
`
`y
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ui(k,2m+2)
`
`
`
`
`Wklzmfi) mum”?
`,,
`(
`,1
`_
`
`YFKKz'I‘f")
`
`
`F|(k.2mf3)
`
`
`
`
`FQSk.2m+2)
`Ui(k,2m+1)
`‘1
`
`,1
`
`
`
`YU‘i(k,2m+1) Bo(k,2m+2)
`
`
`>
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fi(k.2m+1) A]
`,
`YFi(k.2m+1),
`
`
`Fi(k,2m+2) N
`
`
`Bo(k.2m+1)
`
`
`Bo(k,2m+2)\
`
`
`Page 14 of 47
`
`Page 14 of 47
`
`
`
`U.S. Patent
`
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 13 0f 19
`
`
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ri(k.2m+1)
`
`Q
`
`FIG. 10A
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 10C
`
`
`
`
`
`
`
`
`
`100 A
`
`
`
`
`F0(k,2m+1)
`
`I»
`Fo(k,2m+2)
`
`J
`
`
`
`Ri(k,2m+1)
`
`7)
`
`
`
`RYi(k,2nT+1)
`
`_
`
`
`
`
`
`
`
`
`100 C
`
`
`
`Fo\(k,2m+1)
`
`
`
`
`FIG. 103
`
`
`
`
`
`100 B
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 10D 100 D
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`RI(k,2m+2)—,
`
`‘1 ,>
`Bc(k,2m+2)
`
`RYi(k,2m+1)
`
`J
`Fq(k,2m+2)
`
`r‘nu
`*
`
`Uj(k.2m+1)Rl(k‘2m+2)
`Bo k,2m+1
`‘9
`
`Yyi(k.2m+1)
`(
`Z
`
`Ui(k,2m+2)
`
`Bo(k 2m+g),
`>
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`100 E
`
`
`
`
`Ri(k-2mi1‘)
`Fp(k,2m+1)
`#)
`
`
`FIG, 10F
`
`
`
`
`
`10
`
`F
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ri(k.2m+?__)
`
`r”
`
`Bo(k,2m+1)
`;
`
`
`Bo(k,2m+2)_
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fogk 2m+2)
`, J
`
`
`
`{Ji(k,2m+1)
`
`
`“j
`Yg(k.2m+1)
`
`Ui(k.2m+2)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 10E
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ri(k.2m+1)\
`
`)
`V
`YRi(k.2m+1)\
`
`/
`Ri(k,2m+2)*
`
`
`
`
`B°(k’2m+1)j
`
`
`
`Page 15 of 47
`
`Page 15 of 47
`
`
`
`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 14 0f 19
`
`
`
`
`US 10,003,553 B2
`
`
`
`FIG. 11A
`
`110 A
`
`
`
`FYi(k,2)m+2)
`
`p-
`Ri(k,2m+1)
`
`
`Ri(k,2m+2f7
`
`
`Bo(k,2mf1)>
`
`
`
`
`Bo(k,2m+g)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 11B
`
`
`
`
`Ri(k,2m+‘l)\\ '
`,
`\J
`
`
`
`
`F9(k,2m+1)w
`
`
`
`19”
`
`
`
`
`
`
`Ri(k.2m+2)
`
`1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`)
`F0(k,2m+2)
`
`Uj(k,2m+‘|)
`
`4‘
`
`L_J_j(k,2m+2)
`
`
`
`
`
`
`
`
`
`
`BYo(k,2m+2)\\ BYi(k,2m+2)
`BYO(k, 2m+2) \7
`
`Bo(k,2m+1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 11C
`
`
`
`
`
`FYi(k,2m+2')r
`
`(”
`Ri(k‘ 2m\+‘| )
`
`
`(’5 \,
`Ri(k,2ln+2)
`
`Bo(k,2m+1),,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 16 of 47
`
`Page 16 of 47
`
`
`
`
`U.S. Patent
`
`
`
`Jun.19,2018
`
`
`
`
`
`Sheet15 0f19
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`:3:£35.5.Ex,,51
`
`
`
`51m§m
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` 53.3:imam
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`:9Sim,x,Em
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`9man3.m5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`K‘
`
`
`ATENJCI
`
`
`
`
`
`sawer
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`N—.0?—
`
`Page 17 of 47
`
`Page 17 of 47
`
`
`
`U.S. Patent
`
`
`
`
`
`
`Jun.19,2018
`
`
`
`Sheet16 0f19
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`:5,22$.:>9E
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`83‘2.0E
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`3..mama3.8E
`
`
`
`
`
`
`
`dawém
`
`
`
`
`
`Samar;
`
`
`
`Rams:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`:awxxu;
`
`
`
`
`
`
`
`aawéom
`
`cawéfimcaNéi
`
`
`
`
`
`
`
`:9.0mg”.:X:GEM
`
`Page 18 of 47
`
`Page 18 of 47
`
`
`
`
`
`U.S. Patent
`
`
`
`
`
`Jun.19,2018
`
`
`
`
`
`Sheet17 0f19
`
`
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`Sagan
`
`
`
`
`
`/
`
`
`$+nmé3
`
`_ v
`
`
`
`“$358
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`,_in.mama3.Ex
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`in:mmfiw...x‘GEN.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`8343.0E
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 19 of 47
`
`Page 19 of 47
`
`
`
`
`U.S. Patent
`
`
`
`Jun.19,2018
`
`
`
`
`
`Sheet18 0f19
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`$3893
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`L+F335m»
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`7/(\
`
`
`
`
`
`€3.me
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`__$9,emsw.1,9Ea:mmsm:x._Em
`
`
`
`
`
`
`
`fiawxxvomcamdo”.
`
`
`
`
`
`
`
`
`
`
`
`
`
`a,
`
`,7;
`
`
`
`
`
`
`
`@3393
`
`>/\c.Sun:
`
`
`
`,(\¢.NEUI
`
`
`
`”NEW/£5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`@uum,xv_>u_,
`_:ENKE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a\
`
`
`
`ANRNéfiSm
`
`
`
`
`
`
`
`
`
`
`
`
`
`WENQE
`
`4L
`
`$355
`
`