logo

Journals Books
Advanced Search
Sign in Register

中文

SCIENCE CHINA Information Sciences
Download PDF
SCIENCE CHINA Information Sciences, Volume 61 , Issue 6 : 060415(2018) https://doi.org/10.1007/s11432-017-9351-4

An intelligent partitioning approach of the system-on-chip for flexible and stretchable systems

Changqing XU *, Yi LIU , Yintang YANG
More info
  • ReceivedOct 27, 2017
  • AcceptedJan 11, 2018
  • PublishedApr 19, 2018
Previous Table of Contents Next
Share
Rating

Abstract


Acknowledgment

This work was supported by National Basic Research Program of China (Grant No. 2015CB351906), National Natural Science Foundation of China (Grant No. 61172030), and Programme of Introducing Talents of Discipline to Universities (111 Project) (Grant No. B12026).


References

[1] Wong W S, Salleo A. Flexible Electronics: Materials and Applications. Berlin: Springer, 2009. Google Scholar

[2] Sekitani T, Zschieschang U, Klauk H. Flexible organic transistors and circuits with extreme bending stability. Nat Mater, 2010, 9: 1015-1022 CrossRef PubMed ADS Google Scholar

[3] Gupta U, Ogras U Y. Extending networks from chips to flexible and stretchable electronics. In: Proceedings of the 10th IEEE/ACM International Symposium on Networks-on-Chip (NOCS), Nara, 2016. 1--6. Google Scholar

[4] Council N R. Flexible Electronics for Security, Manufacturing, and Growth in the United States: Summary of a Symposium. Washington: The National Academies Press, 2013. Google Scholar

[5] Kim D H, Ahn J H, Choi W M. Stretchable and foldable silicon integrated circuits. Science, 2008, 320: 507-511 CrossRef PubMed ADS Google Scholar

[6] Kim D H, Song J, Choi W M. From the cover: materials and noncoplanar mesh designs for integrated circuits with linear elastic responses to extreme mechanical deformations. Proc Natl Acad Sci USA, 2008, 105: 18675-18680 CrossRef PubMed ADS Google Scholar

[7] Yoon J, Baca A J, Park S I. Ultrathin silicon solar microcells for semitransparent, mechanically flexible and microconcentrator module designs. Nat Mater, 2008, 7: 907-915 CrossRef PubMed ADS Google Scholar

[8] Kim D H, Kim Y S, Wu J. Flexible electronics: ultrathin silicon circuits with strain-isolation layers and mesh layouts for high-performance electronics on fabric, vinyl, leather, and paper. Adv Mater, 2009, 21: 3703-3707 CrossRef Google Scholar

[9] Fusella E, Cilardo A. PhoNoCMap: an application mapping tool for photonic networks-on-chip. In: Proceedings of 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, 2016. 289--292. Google Scholar

[10] Chen W, Deng C C, Liu L B. An efficient application mapping approach for the co-optimization of reliability, energy, and performance in reconfigurable NoC architectures. IEEE Trans Comput-Aided Des Integr Circ Syst, 2015, 34: 1264-1277 CrossRef Google Scholar

[11] Li J S, Pan Y. A fast and energy efficient branch and bound algorithm for NoC task mapping. In: Proceedings of the 33rd IEEE International Conference on Computer Design (ICCD), New York, 2015. 9--16. Google Scholar

[12] Bo H, Song C, Wei Z, et al. Application-specific network-on-chip synthesis with topology-aware floorplanning. In: Proceedings of the 25th Symposium on Integrated Circuits and Systems Design (SBCCI), Brasilia, 2012. 1--6. Google Scholar

[13] Ye T T, Benini L, Micheli G D. Analysis of power consumption on switch fabrics in network routers. In: Proceedings of 2002 Design Automation Conference, New Orleans, 2002. 524--529. Google Scholar

[14] Elmiligi H, Morgan A A, El-Kharashi M W, et al. A delay-aware topology-based design for networks-on-chip applications. In: Proceedings of the 4th International Design and Test Workshop (IDT), Riyadh, 2009. 1--5. Google Scholar

[15] Sivanandam S N, Deepa S N. Introduction to Genetic Algorithms. Berlin: Springer, 2008. Google Scholar

[16] Chatha K S, Srinivasan K. Layout aware design of mesh based NoC architectures. In: Proceedings of the 4th International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS' 06), Seoul, 2006. 136--141. Google Scholar

[17] Seiculescu C, Murali S, Benini L. SunFloor 3D: a tool for networks on chip topology synthesis for 3-D systems on chips. IEEE Trans Comput-Aided Des Integr Circ Syst, 2010, 29: 1987-2000 CrossRef Google Scholar

[18] Yu B, Dong S Q, Chen S, et al. Floorplanning and topology generation for application-specific network-on-chip. In: Proceedings of the 15th Asia and South Pacific Design Automation Conference (ASP-DAC), Taipei, 2010. 535--540. Google Scholar

[19] Dick R P, Rhodes D L, Wolf W. TGFF: task graphs for free. In: Proceedings of Hardware/Software Codesign, Seattle, 1998. 97--101. Google Scholar

[20] Shuang Y, Fen G, Gui F, et al. A two-phase floorplanning approach for application-specific network-on-chip. In: Proceedings of the 10th International Conference on ASIC, Shenzhen, 2013. 1--4. Google Scholar

[21] Zhong L L, Sheng J Y, Jing M E, et al. An optimized mapping algorithm based on simulated annealing for regular NoC architecture. In: Proceedings of the 9th IEEE International Conference on ASIC, Xiamen, 2011. 389--392. Google Scholar

[22] Li Z X, Liu Y, Cheng M S. Solving NoC mapping problem with improved particle swarm algorithm. In: Proceedings of the 6th International Conference on Advanced Computational Intelligence (ICACI), Hangzhou, 2013. 12--16. Google Scholar

[23] Palaniveloo V A, Ambrose J A, Sowmya A. Improving GA-based NoC mapping algorithms using a formal model. In: Proceedings of 2014 IEEE Computer Society Annual Symposium on VLSI, Tampa, 2014. 344--349. Google Scholar

  • Click to view Download high-quality image

    Figure 1

    Illustration of flexible and stretchable systems with integrated sensing, computing and communication capabilities.

  • Click to view Download high-quality image

    Figure 2

    (Color online) Examples of bendable or stretchable systems. (a) Forces are applied in the $y$ direction only;protect łinebreak (b) forces are applied in the $y$ and $z$ directions only.

  • Click to view Download high-quality image

    Figure 3

    Illustration of flexible and stretchable systems based on network-on-chip.

  • Click to view Download high-quality image

    Figure 4

    (Color online) Examples of bendable or stretchable systems. (a) Forces are applied in the $y$ direction only;protectłinebreak (b) forces are applied in the $y$ and $z$ direction only.

  • Click to view Download high-quality image

    Figure 5

    Overview of the proposed partitioning approach of the SoC.

  • Click to view Download high-quality image

    Figure 6

    (Color online) Examples of (a) functional module characteristic graph, (b) cluster communication graph, and (c) architecture characterization graph.

  •   

    Algorithm 1 Function module clustering

    Require:The application characteristics graph (FMCG) of the given SoC $G({\rm~FM},~A)$, the number of clusters $N_{\rm~cluster}$, and the area of the functional module $S({\rm~fm}_i)$;

    Output:A cluster communication graph (CCG) $G(C,F)$.

    Calculate the average area of clusters $S_{\rm~avg}$ based on $N_{\rm~cluste}$;

    Based on the communication volume, sort the functional modules in descending order;

    Set the first functional module in the sort as cluster head;

    for $i=1$; $i<N_{\rm~cluster}$; $i++$

    while $(S(c_{i})~<~S_{\rm~avg})$ do

    if $(\exists$ adjacent functional module $~\notin~$ $c_{i})$ then

    Put an adjacent functional module in $c_i$;

    else

    Select another functional module from $c_i$ as the new cluster head;

    end if

    end while

    Select a new cluster head from the rest of the functional modules;

    end for

    Calculate the communication volume between clusters $F$;

    Obtain the CCG $G(C,F)$.

  • Table 1   Genetic operators in the operator pool
    SelectionCrossoverMutation
    S1: Truncation selection C1: Discrete recombination M1: Random mutation
    S2: Tournament selection C2: Single point recombination M2: Swap mutation
    S3: Roulette wheel selection C3: Multi-point recombination M3: Discrete breeder mutation
  • Table 2   Effectiveness of the proposed functional module clustering algorithm
    Benchmark$V$$E$No. of clustersNo clusters [3][20]Proposed
    VA CV Area VA CV Area $t$ (s) VA CV Area $t$ (s)
    SoC25 25 35 8 7.05 822 225 5.91 535 138 0.05 2.94 309 130 0.01
    SoC2626 62 6 55.09 5480 624 55.47 2160 437 0.10 7.47 2320 396 0.04
    SoC38 38 47 12 10.14 11892 608 18.70 4101 342 0.12 9.13 5053 336 0.04
    SoC50 50 147 9 4.39 37457 425 6.44 27209 387 0.18 0.86 23099 360 0.07
    SoC80 80 292 9 20.78 78992 1280 12.54 59325 1161 1.20 7.43 51332 1071 0.40
  •   

    Algorithm 2 Cluster mapping

    Require:Cluster communication graph CCG, architecture characterization graph ARCG and routing algorithm;

    Output:Position of mapped clusters.

    Initialize the parent population;

    Calculate the fitness of the parent population;

    while (not termination condition) do

    Select operators from the operator pool by roulette wheel selection;

    Obtain the offspring population from the selected genetic operators;

    Calculate the fitness of the offspring population;

    Update the weights of operators based on the “reward” mechanism;

    Compare the parent and offspring populations based on fitness;

    Generate a new parent population;

    end while

    Obtain the best individual as the mapping result.

  • Table 3   Average runtime of the mapping algorithms
    Benchmark No. of clustersSA[21] PSA[22] GA[23] GMO
    C_SoC258 11.26 14.06 6.19 1.13
    C_SoC266 0.070.05 0.04 0.04
    C_SoC3812 67.81 84.66 108.12 27.38
    C_SoC509 17.70 24.05 24.04 8.98
    C_SoC809 23.18 33.35 23.45 8.93
  • Table 4   Improvements in communication energy and delay achieved by the mapping algorithms
    BenchmarkSA[21]PSA[22]GA[23]GMO
    $E$ (%) $D$ (%) $E$ (%) $D$ (%) $E$ (%) $D$ (%) $E$ (%) $D$ (%)
    C_SoC25 56.63 41.08 56.63 41.08 56.63 41.08 56.63 41.08
    C_SoC26 24.28 36.62 24.28 36.62 24.28 36.62 24.28 36.62
    C_SoC38 35.85 48.76 35.65 49.78 35.28 49.91 36.45 50.30
    C_SoC50 12.91 16.35 13.34 16.60 12.78 15.60 13.91 18.35
    C_SoC80 10.10 14.57 10.34 14.06 9.21 14.43 10.64 15.06