`
`
`
`US010003553B2
`
`
`
`
`
`
`
`
`
`
`(12) United States Patent
`
`
`
`
`
`US 10,003,553 B2
`(10) Patent No.:
`
`
`
`
`
`
`
`
`Konda
`*Jun. 19, 2018
`(45) Date of Patent:
`
`
`
`Notice:
`
`
`
`
`
`
`5,451,936 A
`5,541,914 A *
`
`
`
`
`5,654,695 A *
`
`
`
`
`6,018,523 A
`
`
`
`6,091,723 A *
`
`
`
`6,185,220 Bl
`
`
`
`
`
`
`
`
`
`
`
`9/1995 Yang et al.
`
`
`
`
`
`7/1996 Krishnamoorthy ... HO4L 49/254
`370/427
`
`
`8/1997 Olnowich ......... GO6I' 13/4022
`
`
`
`
`
`340/2.23
`
`1/2000 Even
`
`
`
`7/2000 Even woe HO4L 49/1507
`
`
`
`
`
`340/2.21
`
`2/2001 Muthukrishnan etal.
`
`
`
`
`
`(Continued)
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`Ronald I. Greenberg, “The Fat-Pyramid and Universal Parallel
`
`
`
`
`
`
`
`Computation Independent of wire delay’ [EEE Trans. Computers,
`
`
`
`
`
`43(12): 1358-1364, Dec. 1994
`
`
`(Continued)
`
`
`
`Primary Examiner — Rasheed Gidado
`
`
`
`
`
`
`
`
`
`
`
`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 ofthis
`
`
`
`
`
`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 Al
`Sep. 8, 2016
`Int. Cl.
`
`HOAL 12/933
`
`
`HOAL 29106
`
`US. Cl.
`
`
`CPC ....
`
`
`
`(54)
`
`
`(71)
`
`(72)
`
`(73)
`
`
`(*)
`
`
`(21)
`
`(22)
`
`(65)
`
`
`(31)
`
`
`(52)
`
`
`(58)
`
`
`(56)
`
`
`ABSTRACT
`(57)
`
`
`
`
`
`
`
`Significantly optimized multi-stage networks, uscful in wide
`
`
`
`
`
`
`
`
`target applications, with VLSI layouts using only horizontal
`
`
`(2013.01)
`
`
`
`
`
`
`
`
`
`
`
`aod vertical links to route large scale sub-integrated circuit
`(2006.01)
`
`
`
`
`
`
`
`
`
`
`blocks having inlet and outlet links, and laid out
`in an
`
`
`
`
`
`
`
`integrated circuit device in a two-dimensional grid arrange-
`
`
`
`
`
`HO4L 49/1515 (2013.01); HO4L 29/06081
`
`
`
`
`
`
`
`
`ment of blocks are presented. The optimized multi-stage
`
`
`
`
`
`
`(2013.01); HO4L 49/109 (2013.01); HO4L
`
`
`
`
`
`
`
`
`
`networks in each block employ several rings of stages of
`
`
`
`65/4076 (2013.01)
`
`
`
`
`
`
`
`
`Field of Classification Search
`switches with inlet and outlet links of sub-integrated circuit
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`blocks connecting to rings fromeitherleft-hand side only, or
`CPC oe HO4L 49/1515; HO4L 65/4076; HO4L
`29/0608 1
`
`
`
`
`
`
`
`
`
`
`
`
`
`from right-hand side only, or from both left-hand side and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`right-hand side; and employ shuffle exchange links where
`See application file for complete search history.
`
`
`
`
`
`
`
`
`
`
`outlet links of cross links from switches in a stage of a ring
`References Cited
`
`
`
`
`
`
`
`
`
`
`
`in one sub-integrated circuit block are connected to either
`
`
`
`
`
`
`
`
`
`inlet links of switches in the another stage of a ring in the
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`
`
`
`same or another sub-integrated circuit block.
`10/1992 Batcher
`5,153,843 A
`
`
`
`
`
`
`9/1994 Cloonan
`
`
`5,345,444 A *9/1994Cloonanonc... HO4L 12/5601
`
`
`
`
`
`
`
`
`
`370/381
`
`
`
`
`
`
`
`20 Claims, 19 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` Dy :al
`
`
`GheeDati
` PET a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 BL*
`1/2002 Lee wie HOAL 49/101
`
`
`
`
`
`
`
`
`
`370/387
`
`
`
`
`
`
`
`
`
`
`
`6,469,540 B2* 10/2002 Nakaya............ HO3K 19/17728
`326/38
`
`
`
`
`
`
`
`
`6,940,308 B2
`9/2005 Wong
`7,440,449 B2* 10/2008 Carson oo... GO6T 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
`
`
`
`
`
`
`
`2003/0117946 Al*
`6/2003 Fontana................ HO4L 12/437
`
`
`
`
`
`
`
`
`
`370/216
`
`
`2011/0037498 A1*
`2/2011 Konda ........... GO6F 17/5077
`
`
`
`
`
`
`
`
`326/41
`
`2012/0269190 A1* 10/2012 Konda .........0. GO6F 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 Letters—PPL , vol. 7, No. 3, pp.
`279-284, 1997.
`
`
`
`
`
`
`
`
`
`
`
`
`Hoda El-Sayed and AbdouYoussef; “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/SIGDAIntl Sympon 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-
`taphy, 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,” [EEE 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 universal 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
`
`
`
`
`
`
`Ubigq. 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.
`
`
`
`
`
`
`
`André 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 El 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.Pandeet al. “Evaluation of MP-SoC Interconnect Architectures: a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case Study”, Proceedings of 4th WSOC, Banff, 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 Tield-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 Gamalet. 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 TEEF/ACM Intl. 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-
`
`
`
`
`
`
`
`
`Programmable Gate Arrays, Feb. 1999, pp. 125-134.
`
`
`
`
`
`
`
`
`André 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 ACMISIGDAInt’l. Symposium on Field Programmable
`
`
`
`
`
`
`
`
`Gate Arrays, pp. 155-164, Monterey, CA, Feb. 2000.
`
`
`
`
`
`
`
`
`S. Sivaswamyet. 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.'l. 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 of 19
`
`
`
`
`US 10,003,553 B2
`
`
`W000
`
`
`
`
`
`(Zew2' WI
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`120
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ring1,Stage“m”
`
`=oD&&
`
`@—@&a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`“n-1”
`100 T
`
`Ring2,Stage
`
`
` Ring1,Stage1
`Ring2,Stage1
`
`Ring1,Stage0
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`{e' Lod >,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` Coed 9A W2in “L
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Computational
`Block
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bol2,2)
`
`
`
`
`
`
`FIG.1A
`
`
`
`Page 3 of 47
`
`Page 3 of 47
`
`

`

`U.S. Patent
`
`
`
`
`
`
`Jun. 19, 2018
`
`
`
`Sheet 2 of 19
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(euz‘zo Wh
`(g-uzziod
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Cuzarea (gauz‘zde/
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 4 of 47
`
`Page 4 of 47
`
`
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 3 of 19
`
`
`
`
`US 10,003,553 B2
`
`
`
`FIG.2A 2"
`
`
`
`20
`
`
`
`Ri(k,2m+1)
`
`7
`
`
`
`
`
`
`
`
`Fo(k.2m+1)
`D
`
`
`
`
`
`
`
`
`
`
`
`
`Fo(k,2m+2)
`
`Ri(k,2m+2)
`
`4
`
`
`Ui(k,2m+1) Bo(k.2m+1)
`
`
`
`FIG.2B
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`200B
`
`
`
`
`Fotk,2m+1}
`
`-
`
`Fo(k,2m+2)
`
`
`
`
`Ui(kK,2m+1)
`
`
`Ui(k,2m+2)
`
`
`
`
`
`Fo(k,2m+2)
`
`
`
`
`
`
`
`
`Muiomee) Bo(k2m#2)
`
`
`
`
`
`
`
`FIG. 2D
`
`200D
`
`
`
`
`Fi(k.2m+1)
`|
`
`
`Fi(k.2m+2)
`
`
`Fo(k,2m+1)
`ee
`
`
`
`
`
`
`
`
`
`200¢
`
`
`
`
`
`
`
`
`
`FIG. 2C
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 5 of 47
`
`Page 5 of 47
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 4 of 19
`
`
`US 10,003,553 B2
`
`
`
`
`
`FIG. 2E
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bo(k.2m+2)
`
`
`
`
`
`
`
`
`
`
`
`Ri(k,2m+1)
`
`
`Ri(k,2m+2)
`
`
`Bo(k,2m+1)
`»)
`
`
`
`Page 6 of 47
`
`Page 6 of 47
`
`

`

`U.S. Patent
`
`
`
`Jun. 19, 2018
`
`
`
`
`Sheet 5 of 19
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`a
`FIG. 3A
`
`Ring “x”, Stage “p+1"
`
`
`
`Ring “’, Stage “p”
`
`
`Ri(x,2p+1)
`
`
`
`
`
`f—
`Ris2p+8)
`Fovx2pe)
`
`oo
`
`
`Fatx2p+3)
`
`
`
`
` Ri(x,2pt4)
`
`
`
`
`
`RiG.2p+2)
`
`-
`
`
`
`
`
`
`
`Oo Bo(x,2p+2)j Vix.2pr4)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a)
`tetBS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fo(x,2p+4)
`>
`
`
`:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`>¢&
`
`a3
`&
`
`
`aa
`)
`
`
`
`Foty,20+4)
`
`
`
`
`
`
`
`
`Fo(y,29+1) \
`
`
`
`
`
`etl
`
`3o(y,2q+3)
`~
`
`
`
`
`
`y
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Hop(t,1)>
`
`Hop(2,1)>
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ring “y”, Stage “a”
`
`Rily,2q+1}
`
`
`) e
`
`Ri(y,29+2)
`
`2
`
`
`
`
`
`Page 7 of 47
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 7 of 47
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 6 of 19
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`FIG. 3B
`
`
`-
`
`
`
`
`
`Folx,2p+1)
`J
`
`
`
`Rix.2p+3)
`
`;
`
`/
`
`Fatxap+s)
`
`-
`
`Fo(x,2p-2)
`
`
`RiQx,2p+4)
`
`?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Foly.2q+3)
`
`
`Foly,2q+4)
`
`
`Jily,2g+3)
`
`
`;
`Jity,24+4)
`
`
`Ring “y”, Stage “q+1"
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Uoly.24r4
`
`oy 20%
`é
`
`
`
`
`
`iN)
`
`+=
`
`}Rily,20-+3)
`Rity,2q+4)y
`
`
`
`
`
`
`
`
`
`
`
`Hop(1.1y~~
`
`Hop(2,1y
`
`
`~s Hop(1.2)
`
`--f Hope,2)
`
`
`Boty,2q+3)
`
`
`
`+a
`
`a2Sm
`
`
`y
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Foly.2q-1)
`
`
`
`
`
`
`
`Page 8 of 47
`
`Page 8 of 47
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 7 of 19
`
`
`
`
`US 10,003,553 B2
`
`
`FIG. 4
`
`
`
`
`
`Ring “x”, Stage “p”
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bo(x,2p+3)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bo(x,2p+2)
`
`_Hop(1,2)
`
`
`
`_Hop(2,2)
`
`
`
`
`Ring “y”, Stage Kg”
`
`
`
`Ring “y”, Stage “g+1"
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fo(y,2q+3)
`
`>
`
`Fo(y.29q+4)
`
`
`Uify,2q+3)
`
`
`Uity,2q+4)
`
`-
`
`=~=ya
`
`N2S
`
`ay
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Boty,2q+2)
`
`
`Page 9 of 47
`
`Page 9 of 47
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 8 of 19
`
`
`US 10,003,553 B2
`
`
`
`
`FIG. 5
`
`
`
`
`Ring ‘x’, Stage “p”
`
`
`
`Ring “x”, Stage “p+1"
`
`
`-
`
`
`
`
`
`
`
`
`
`Fo(x,2p+3)
`)
`
`
`
`
`Fo(%,2p+1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Hop(1,1)
`
`Hop(2,1)7
`
`
`
`~ Hop(1.2)
`
`Hop(2.2)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Foty,2q+3)
`
`
`
`
`o
`
`
`
`
`
`so)Ca,
`locy,ic
`Uoty,C Uily,2q+3)
`
`nealaer ro>oreUily.2a+4)
`
`
`TR]
`
`
`
`
`
`
`
`
`
`
`
`Boty,2q+2)
`
`
`Page 10 of 47
`
`Page 10 of 47
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 9 of 19
`
`
`US 10,003,553 B2
`
`
`
`
`FIG.6
`
`_—
`
`
`
`
`
`
`
`
`
`
`
`
`Ring “x”, Stage “p”
`
`
`
`
`
`
`
`
`
`
`
`
`
`ee2p+1)
`|
`
`
`
`Uo(x,2p+1C .+SIa
`
` "
`
`
`
`
`
`|
`
`
`
`
`Uoty,i
`Uoyy,.i
`
`C2q+1)
`C2q+3)
`
`
`
`(p+b7'_
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`_Hop(1,2)
`
`Hop(2,2)
`
`
`
`
`
`
`
`
`Ring “y’, Stage “q+1"
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Foly.2q+3)
`
`
`
`Foty.2q+4)
`
`
`
`
`
`
`
`
`Uily,29+3)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Uiy.2q+4)
`
`Boly,2q+2)
`
`
`Page 11 of 47
`
`Page 11 of 47
`
`

`

`
`
`
`
`
`
`OTe 84 5 6
`
`
`
`
`
`
`
`
`
`
`
`“sonenmg>$Y
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`Sheet 10 of 19
`
`
`
`
`US 10,003,553 B2
`
`
`FIG.7
`
`
`_
`
`L1 V1 U1 H1 K1L2
`
`L1 V3 U3 L2 H3 K3 V5
`
`Page 12 of 47
`
`Page 12 of 47
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`Sheet 11 of 19
`
`
`
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`8°Old
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 13 of 47
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`wold
`
`
`
`Page 13 of 47
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`Sheet 12 of 19
`
`
`
`
`US 10,003,553 B2
`
`FIG. 9A
`
`
`
`90
`
`
`
`Fick,2m+1)
`
`)
`
`YFi(k,2m+1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fo(k,.2m#1)
`
`5
`—
`
`Fik,2m+1}
`
`-
`
`Fi(k,2m+1)
`
`,
`a
`
`i
`
`Fi(k,2m+2)
`a
`
`
`
`
`
`Fuk22}
`
`is
`
`Fo(k,2m+2
`
`
`ol m+2)
`_
`Uitk,2m+1
`
`,
`, Bo(k,2m+1)
`2
`.2m+:
`
`
`
`
`
`
`Botan
`\
`
`
`
`
`
`
`
`
`900C
`
`
`
`rotk2me1)
`
`.
`<
`
`
`
`Fo(k,2m+2
`
`0
`)
`<
`Ui(k2m
`
`)
`at
`
`
`
`
`
`
`
`
`
`
`
`
`
`Botc2meg)
`>
`
`
`
`
`
`
`
`
`
`
`
`
`YUi(k.2m+1)
`
`Bo(k,2m+2)
`
`
`2
`
`—
`Ui(k,2m+2)
`
`
`
`
`
`
`
`
`
`UYitk,2m+1)
`
`-
`Uitk,2m+2)
`
`
`
`
`
`Fockames) MRAmel)
`Fueme)
`
`
`
`YFi(k,2m+1)
`YFi(k.2m+1).,
`
`
`
`
`
`
`
`Fik.2m+2) Fo(k.2m+2)—Fi(k.2m+2) Fok2m#2)
`
`—
`oe
`co
`<
`Ui(k,2m+1
`Ui
`2met
`
`
`camel)
`\ i(k2mrt)
`_
`
`
`Fo(k.2m+1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`YUitk.2m+1)
`
`
`—s
`Vi(k,2m+2)
`
`
`
`Bo(k,2m+2)
`%
`¢
`
`
`
`
`
`
`
`
`UYitk.2m+1)
`
`=
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bo(k,2m+1)
`
`s
`
`
`
`
`Uitk,2m+2)
`
`
`
`Bo(k.2m+1) _
`
`
`Bo(k,2m+2}__
`
`a
`
`Page 14 of 47
`
`Page 14 of 47
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 13 of 19
`
`
`
`
`
`US 10,003,553 B2
`
`FIG. 10A FIG. 10B=:1099B1000A
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fo(k,.2m+1)
`
`
`Fo(k,2m+2)
`
`*
`
`
`
`Rik,2m+1)
`
`
`
`
`RYi(k,2m+1)
`
`;
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fo(k,2m+1)
`
`
`
`
`
`
`
`
`FIG. 10C=10900c FIG. 10D 1000p
`
`
`
`
`
`
`
`‘
`
`Ri(k.2m+1)
`
`
`
`
`
`
`
`
`
`
`
`o(k,2m+
`Fotk2met)
`
`2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ri(k,.2m+2};
`
`Bo(k,2m+2)
`Bo(k,2m+2)
`
`
`Ri(k,2m+1}
`/
`Fo(k,2m+1)
`i
`\
`
`_
`RYi(k,2m+1)
`
`
`Fotk.2m2)
`ro
`—_
`
`Vick.2metflk2m*2)
`Bo(k,2m+1
`=
`
`YUick.2m+1)
`(
`2
`
`Ui(k.2m+2)
`
`Botk.2m+2)
`5
`‘)
`C
`
`Ri{k.2m+2)
`
`
`Bo(k,2m+1)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`c-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 10E=1090E FIG. 10F 1000F
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Rik2m+1)_
`
`;
`c
`YRi(k.2m+1),
`
`
`Ri(k.2m+2)=
`-
`
`Bo(k.2m+1)}
`
`
`
`
`
`Page 15 of 47
`
`Page 15 of 47
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 14 of 19
`
`
`
`
`US 10,003,553 B2
`
`
`FYi(k,2m+2)
`
`rx
`Ri(k,2m+1)
`
`
`Ri(k,2m+2)7
`
`
`a
`
`Bo(k,2m+1)
`
`
`
`Bo(k,2m+2)
`
`
`
`FIG. 11A
`
`
`ea
`
`Fo(k,2m+1)
`
`
`
`
`
`Ui(k.2m+1)
`“
`
`Ui(k.2m+2)
`i
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 11B
`
`
`
`Ri(k,2m+1)
`
`co
`
`Ri(k.2m+2)
`
`_
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Bo(k,2m+1)
`
`
`
`
`
`
`
`FIG. 11C
`
`FYi(k,2m+2)
`
`oo
`Ri(k,2m+1)
`
`
`
`i
`Ri(k,2m+2)
`
`Bo(k,2m+1).,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 16 of 47
`
`
`
`a
`
`
`
`
`Fo(k.2m+1)
`
`)
`
`
`
`
`
`
`
`
`
`
`
`BYo(k,2m+2)~
`BYo(k,2m+t2)s,
`
`Page 16 of 47
`
`€
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Sheet 15 of 19
`
`
`
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ub+d,aBeyg“x,Bury
`
`
`
`(erdZ>)ly
`
`
`
`(reneeSuter
`
`
`
`
`
`
`
`
`
`{e+bz'A)o4aa.(e+be'Ajy
`clOL
`
`ub+b,368)5“A,Bury;3my
`re:z+xe4
`
`fe+dz'xian¢—(L4+dz"%o4
`
`
`
`
`
`‘«d,aBeyg“x,Bury
`
`Page 17 of 47
`
`(zonjs.AL'2)d0H
`
`
`
`{z'yydonHLYOH6saz59)n
`
`
`
`
`
`
`
`
`
`iL+bz'A)In,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`b,a6eis“A,Bur
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(+0750
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`g
`
`
`
`(L+bz‘A)og
`
`
`
`Page 17 of 47
`
`

`

`U.S. Patent
`
`
`
`
`
`
`Jun. 19, 2018
`
`
`
`Sheet 16 of 19
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ubtb,obeys‘A,Bury
`
`
`
`(e+dz%Ora
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`othel‘D1d
`
`
`
`
`
`
`
`A,2681$Xx,Bury
`
`Page 18 of 47
`
`(adeo4Sedzoog
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`~.LVZ}d0H
`
`
`
`
`
`
`
`L..('bidoy(2+de410
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`“CL+b2'Hld
`
`
`
`
`
`(LabZOIA
`
`
`
`(2282's
`
`
`
`
`
`
`
`
`
`wb,aBeys‘A,Bury
`
`Page 18 of 47
`
`
`
`
`
`
`

`

`
`U.S. Patent
`
`
`
`Jun. 19, 2018
`
`
`
`
`
`Sheet 17 of 19
`
`
`
`
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`
`
`
`
`
`
`cevog'Ao
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ub+b,a6eg“A,Bury
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`.2g+4)
`Bey.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5
`
`
`
`
`
`(ered, _(sdewg
`
`
`
`
`
`
`
`Usdein(waz'ea
`
`
`
`
`
`
`
`
`
`.,abeys‘x,Bury
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(exdz™)I4
`
`
`
`
`
`
`
`
`
`f+bz'Hogpes
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ghz’
`
`
`
`(erbzIN
`
`aePLD
`
`
`
`Page 19 of 47
`
`Page 19 of 47
`
`
`

`

`
`U.S. Patent
`
`
`
`
`Jun. 19, 2018
`
`
`
`Sheet 18 of 19
`
`
`
`
`
`
`
`
`US 10,003,553 B2
`
`
`
`‘e-dzX)o4
`
`
`
`{(p+dZ”OA4
`
`>
`
`
`
`den
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ub+d,oBe}g“x,Bury
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ub+b,abeys‘4,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(erbzA)o54,
`
`
`
`
`
`
`
`om
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`O0S1 e.
`
`(esdz'xia(Lede)
`
`(poder(2+dzrd
`o>a
`
`fed(+dz*)oa
`_)Cee
`
`(esde>urs(Ladzxou
`
`
`
`
`
`
`
`~_AdcH
`
`
`
`
`
`_A'2)d0H
`
`
`
`(dzAg
`
`
`
`
`
`
`
`
`
`