ABSTRACT
CONTENTS 4.1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 70 4.2 Collective communications : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 71
4.2.1 A model of communication : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 72 4.2.2 Classification of collective communications : : : : : : : : : : : : : : : : : : : : : : : : 74 4.2.3 The lower bounds on time complexity : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 75
4.3 State-of-the-art : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 77 4.4 Evolutionary design of collective communications : : : : : : : : : : : : : : : : : : : : : : : : : 78
4.4.1 Input data structure and preprocessing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 80 4.4.2 Scatter encoding : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 80 4.4.3 Broadcast encoding : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 81 4.4.4 Fitness function definition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 83 4.4.5 Acceleration and restoration heuristics : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 84 4.4.6 The mutation operator : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 84
4.5 Optimization tools and parameters adjustments : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 85 4.5.1 Experimental comparison of optimization quality : : : : : : : : : : : : : : : : : : : 86 4.5.2 Experimental comparison of optimization speed : : : : : : : : : : : : : : : : : : : : 86 4.5.3 Experimental comparison of optimization scalability : : : : : : : : : : : : : : : 87 4.5.4 Tools assessment : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 89
4.6 Experimental results of the quest for high-quality schedules : : : : : : : : : : : : : : : : 89 4.6.1 Experimental results on common topologies : : : : : : : : : : : : : : : : : : : : : : : : 89 4.6.2 Experimental results on novel and fat nodes topologies : : : : : : : : : : : : : 91 4.6.3 Experimental results on fault-tolerant topologies and many-to-many patterns : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 94
4.7 Conclusions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 98 4.7.1 Contributions of the proposed technique : : : : : : : : : : : : : : : : : : : : : : : : : : : : 101 4.7.2 Future work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102
Acknowledgment : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 103
This chapter describes the technique of the evolutionary design aimed at scheduling of collective communications on autonomic networks-on-chip (ANoC). In order to avoid contention for links and associated delays, collective communications proceed in synchronized steps. A minimum number of steps is sought for the given network
topology and given sets of sender and receiver nodes. The proposed technique is not only able to re-invent optimum schedules for known symmetric topologies like hypercubes but also can find schedules even for any asymmetric, irregular, multistage and fat topologies in case of general many-to-many collective communications. In most cases, the number of steps reaches the theoretical lower bound for the given communication pattern; if it does not, non-minimum routing can provide further improvement. Optimal schedules may serve for writing high-performance communication routines for application-specific networks on chip or for the development of communication libraries in the case of general-purpose interconnection networks.
