A heuristic clustering approach to use case-aware application-specific network-on-chip synthesis

Network-on-chip (NoC) is a promising paradigm for efficient communication between the processing elements inside multi-core system-on-chip (SoC) and general purpose chip-multi-processor. Choosing appropriate topology for NoCs with predefined application characteristics plays a pivotal role in improving power and area metrics. Until now, different irregular topologies with varying objective optimization parameters have been offered. In this paper, a novel heuristic topology synthesis method for creating application-specific NoCs consisting of some use cases which are described the applications characteristics has been proposed. This approach is composed of application clustering for assigning cores to specific routers, topology construction for finding a routing path for all flows, and also link insertion for producing final topology by interconnecting the routers. To confirm the proposed method, results of an industrial smartphone SoC and some generic benchmarks have been used as case studies. Experimental results demonstrate the benefits of the proposed method compared to state-of-the-art approaches.     

片上网络拓扑结构

介绍了片上网络（NoC）拓扑结构的相关研究进展。对NoC拓扑结构进行了分类，详细分析了各种网络拓扑的相关特性。从拓扑结构的角度出发，介绍了几种典型的NoC实例，归纳了相关的设计方法。最后，探讨了NoC拓扑结构的发展方向。     

应用分段遗传算法的视频纹理合成算法

通过对视频纹理定义的分析,将视频纹理合成转化为一个优化组合问题。提出一种应用分段遗传算法的视频纹理合成算法,采用分段遗传算法,对有限长度的源视频进行加工,得到可无限播放的连续视频序列。算法采用更适当的相似性尺度和测量准则,省去了大量复杂的对源视频的预处理,分段的搜索策略只需要用很少的遗传代数即可快速合成出质量很高的视频纹理。与现有的视频纹理合成方法比较,该算法具有较小的计算复杂度,在合成的速度和质量上都有所提高。另外,实验结果给出了种群大小以及最大遗传代数对合成质量和速度的影响。     

Distributed topology discovery in self-assembled nano network-on-chip

In this paper, we present DiSR, a distributed approach to topology discovery and defect mapping in a self-assembled nano network-on-chip. The main aim is to achieve the already-proven properties of segment-based deadlock freedom requiring neither a topology graph as input, nor a centralized algorithm to configure network paths. After introducing the conceptual elements and the execution model of DiSR, we show how the open-source Nanoxim platform has been used to evaluate the proposed approach in the process of discovering irregular network topology while establishing network segments. Comparison against a tree-based approach shows how DiSR still preserves some important properties (coverage, defect tolerance, scalability) while avoiding resource hungry solutions such as virtual channels and hardware redundancy. Finally, we propose a gate-level hardware implementation of the required control logic and storage for DiSR, demonstrating a relatively acceptable impact ranging from 10 to about 20% of the budget of transistors available for each node.     

Power- and performance-efficient cluster-based network-on-chip with reconfigurable topology

Topology is widely known as the most important characteristic of networks-on-chip (NoC), since it highly affects overall network performance, cost, and power consumption. In this paper, we propose a reconfigurable architecture and design flow for NoCs on which a customized topology for any target application can be implemented. In this structure, the nodes are grouped into some clusters interconnected by a reconfigurable communication infrastructure. The nodes inside a cluster are connected by a mesh to benefit from the interesting characteristics of the mesh topology, i.e. regular structure and efficient handling of local traffic. A reconfigurable inter-cluster topology then eliminates the major shortcoming of the mesh by providing short paths between remotely located nodes. We then present a design flow that maps the frequently communicating tasks of a given application onto the same cluster and exploits the reconfigurable infrastructure to set up appropriate inter-cluster connections. The experimental results show that by efficiently handling local and long-distance traffic flows, this structure is scalable, and power- and performance-efficient.     

基于改进遗传算法的3DNoC低功耗映射研究

二维片上网络（Two-Dimensional Network-on-Chip,2D NoC）在面积、功耗、布局布线、封装密度等方面都已达到了瓶颈。与2D NoC相比,三维片上网络（Three-dimensional Network-on-Chip,3D NoC）有着诸多优势,因此3D NoC逐渐成为一个重要的研究方向。随着3D NoC集成度的提高,低功耗映射逐渐成为研究热点。将贪心算法的思想与遗传算法相结合提出一种改进的遗传算法,用以解决3D NoC低功耗映射问题,相对于传统遗传算法,改进遗传算法具有更优的搜索能力。仿真结果表明,采用改进后的遗传算法解决3D NoC映射问题可以降低功耗,从总体趋势来看随着处理单元数量的增加功耗降低幅度逐渐增大,在120个处理单元情况下总功耗可降低14%。     

Structural topology optimization using a genetic algorithm with a morphological geometric representation scheme

This paper describes a versatile methodology for solving topology design optimization problems using a genetic algorithm (GA). The key to its effectiveness is a geometric representation scheme that works by specifying a skeleton which defines the underlying topology/connectivity of a structural continuum together with segments of material surrounding the skeleton. The required design variables are encoded in a chromosome which is in the form of a directed graph that embodies this underlying topology so that appropriate crossover and mutation operators can be devised to recombine and help preserve any desirable geometry characteristics of the design through succeeding generations in the evolutionary process. The overall methodology is first tested by solving ‘target matching’ problems—simulated topology optimization problems in each of which a ‘target’ geometry is first created and predefined as the optimum solution, and the objective of the optimization problem is to evolve design solutions to converge towards this target shape. The methodology is then applied to design two path-generating compliant mechanisms—large-displacement flexural structures that undergo some desired displacement paths at some point when given a straight line input displacement at some other point—by an actual process of topology/shape optimization.     

三维片上网络正四面体裂变拓扑结构研究

旨在研究新型三维片上网络正四面体裂变拓扑结构,给出了该拓扑结构的生成过程;对该拓扑结构进行了编码设计和路由设计。通过对gpNoCsim片上网络仿真器进行三维扩展,对正四面体裂变拓扑结构进行性能仿真实验。仿真结果表明,在均匀负载模式下,正四面体裂变拓扑结构的平均延时和平均跳数均低于Mesh结构,当注入率为0.02时,平均延时比Mesh结构低16.8%、平均跳数比Mesh结构少5.5%;在局部负载模式下,当注入率大于0.008时,正四面体裂变拓扑结构的平均延时和平均跳数与Mesh结构相比,均有明显改善;当注入率为0.014时,平均延时比 Mesh结构降低18.7%、平均跳数比 Mesh结构减少9.6%。说明正四面体裂变拓扑结构可用于三维片上网络拓扑结构设计。     

Optimum topology and shape design of prestressed concrete bridge girders using a genetic algorithm

The purpose of this study is to optimize the topology and shape of prestressed concrete bridge girders. An optimum design approach that uses a genetic algorithm (GA) for this purpose is presented. The cost of girders is the optimum design criterion. The design variables are the cross-sectional dimensions of the prefabricated prestressed beams, the cross-sectional area of the prestressing steel and the number of beams in the bridge cross-section. Stress, displacement and geometrical constraints are considered in the optimum design. AASHTO Standard Specifications for Highway Bridges are taken into account when calculating the loads and designing the prestressed beams. A computer program is coded in Visual Basic for this optimization. Many design examples from various applications have been optimized using this program. Several of these examples are presented to demonstrate the efficiency of the algorithm coded in the study.     

A genetic algorithm for combined topology and shape optimisations

A method to find optimal topology and shape of structures is presented. With the first the optimal distribution of an assigned mass is found using an approach based on homogenisation theory, that seeks in which elements of a meshed domain it is present mass; with the second the discontinuous boundaries are smoothed. The problem of the optimal topology search has an ON/OFF nature and has suggested the employment of genetic algorithms. Thus in this paper a genetic algorithm has been developed, which uses as design variables, in the topology optimisation, the relative densities (with respect to effective material density) 0 or 1 of each element of the structure and, in the shape one, the coordinates of the keypoints of changeable boundaries constituted by curves. In both the steps the aim is that to find the variable sets producing the maximum stiffness of the structure, respecting an upper limit on the employed mass. The structural evaluations are carried out with a FEM commercial code, linked to the algorithm. Some applications have been performed and results compared with solutions reported in literature.     

Optimization of microwave devices combining topology gradient and genetic algorithm

Topology optimization can be seen as optimizing a distribution of small topological elements within a domain with respect to given specifications. A numerical topology gradient (TG) algorithm is applied in the context of electromagnetism for optimizing microwave devices, computing the sensitivity on adding or removing small metallic elements. This method leads to an optimum topology with very little initial information in acceptable time consumption. The method is applied to the design of a microstrip component in which the topology gradient is directly used as a direction of descent. However, in some ill‐behavior problems, topology gradient is not sufficient to converge to the global optimum. In the latter case, the basic TG is coupled with a genetic algorithm (GA) to make a more suitable algorithm for solving local optima problems. © 2008 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2008.     

Improved genetic algorithm with two-level approximation for truss topology optimization

Truss topology optimization using Genetic Algorithms (GAs) usually requires large computational cost, especially for large-scale problems. To decrease the structural analyses, a GA with a Two-level Approximation (GATA) was proposed in a previous work, and showed good computational efficiency with less structural analyses. However, this optimization method easily converges to sub-optimum points, resulting in a poor ability to search for a global optimum. Therefore, to address this problem, we propose an Improved GA with a Two-level Approximation (IGATA) which includes several modifications to the approximation function and simple GA developed previously. A Branched Multi-point Approximation (BMA) function, which is efficient and without singularity, is introduced to construct a first-level approximation problem. A modified Lemonge penalty function is adopted for the fitness calculation, while an Elite Selection Strategy (ESS) is proposed to improve the quality of the initial points. The results of numerical examples confirm the lower computational cost of the algorithm incorporating these modifications. Numerous numerical experiments show good reliability of the IGATA given appropriate values for the considered parameters.     

Structural topology optimization using ant colony optimization algorithm

The ant colony optimization (ACO) algorithm, a relatively recent bio-inspired approach to solve combinatorial optimization problems mimicking the behavior of real ant colonies, is applied to problems of continuum structural topology design. An overview of the ACO algorithm is first described. A discretized topology design representation and the method for mapping ant's trail into this representation are then detailed. Subsequently, a modified ACO algorithm with elitist ants, niche strategy and memory of multiple colonies is illustrated. Several well-studied examples from structural topology optimization problems of minimum weight and minimum compliance are used to demonstrate its efficiency and versatility. The results indicate the effectiveness of the proposed algorithm and its ability to find families of multi-modal optimal design.     

A two phase approach based on skeleton convergence and geometric variables for topology optimization using genetic algorithm

This paper introduces a set of skeleton operators for characterizing topologies evolving in a bit-array represented structural topology optimization problem. It is shown that the design generally converges to a stable skeleton fairly early in the optimization process. It is observed that further optimization is more about finding optimal gross shape for the various branches of the converged skeleton and the bit-array representation is not appropriate. A two-phase approach to topology optimization is proposed in which the first phase, where bit-array is used to represent the topology, ends with the detection of stabilization of skeleton, and the second phase proceeds further with the geometry based representation that directly addresses gross variation in shape of the branches of the converged skeleton. Genetic Algorithm has been used for optimization in both the phases. The efficiency and effectiveness of the use of skeleton operators and geometric variables for identification of convergence in the first phase and optimization in the second phase respectively is demonstrated.     

Variable chromosome length genetic algorithm for progressive refinement in topology optimization

This article introduces variable chromosome lengths (VCL) in the context of a genetic algorithm (GA). This concept is applied to structural topology optimization but is also suitable to a broader class of design problems. In traditional genetic algorithms, the chromosome length is determined a priori when the phenotype is encoded into the corresponding genotype. Subsequently, the chromosome length does not change. This approach does not effectively solve problems with large numbers of design variables in complex design spaces such as those encountered in structural topology optimization. We propose an alternative approach based on a progressive refinement strategy, where a GA starts with a short chromosome and first finds an optimum solution in the simple design space. The optimum solutions are then transferred to the following stages with longer chromosomes, while maintaining diversity in the population. Progressively refined solutions are obtained in subsequent stages. A strain energy filter is used in order to filter out inefficiently used design cells such as protrusions or isolated islands. The variable chromosome length genetic algorithm (VCL-GA) is applied to two structural topology optimization problems: a short cantilever and a bridge problem. The performance of the method is compared to a brute-force approach GA, which operates ab initio at the highest level of resolution.     

基于遗传算法的鲁棒数字水印技术

提出了一种增强水印鲁棒性的算法,该算法采用多目标优化的遗传算法定义一种新的适应度函数,结合Watson视觉感知模型,调节水印在DCT变换域嵌入的强度.根据遗传算法得到的不同结果,不同强度的水印信息被嵌入到各个DCT块的视觉感知门限(JND)最大的几个中低频系数中.实验结果表明,在满足水印不可见性的同时,算法在噪声、滤波、旋转,压缩等图像处理条件下具有很好的鲁棒性.     

基于Prim初始种群选取优化遗传算法的三维片上网络低功耗映射

针对将计算任务合理地映射到三维片上网络（NoC）的问题,提出了一种基于遗传算法（GA）的改进算法。GA具有快速随机的搜索能力,Prim算法可在加权连通图内得到最小生成树,改进算法结合了两种算法的优势,将计算任务合理地分配到各个网络节点,对于优化三维片上网络功耗和散热等问题具有很高的效率。通过仿真实验,对所提出的基于Prim算法的改进GA与基本GA的3D NoC映射算法进行了对比,仿真结果显示,基于Prim算法的改进GA平均功耗更低,从总体趋势来看,处理单元数量的增加与功耗降低幅度成正相关,在101个处理单元情况下,平均功耗比基本GA降低32%。     

A shortly connected mesh topology for high performance and energy efficient network-on-chip architectures

Network-on-chip-based communication schemes represent a promising solution to the increasing complexity of system-on-chip problems. In this paper, we propose a new mesh-like topology called the shortly connected mesh technology (ScMesh), which is based on the traditional mesh topology, to exploit the graph symmetry properties of interconnection networks. This proposed topology not only enhances network performance by reducing the network diameter, but also provides a lower area/energy solution for interconnection network scenarios. This study analyzes and compares the performance of ScMesh to some newly improved topologies, including the WK-recursive, extended-butterfly fat tree, and diametrical mesh topologies. The experiment results indicate that ScMesh outperforms the other topologies, with throughput increases of 47.71, 33.45, and 18.64 % as well as latency decreases of 45.71, 35.84, and 14.58 % compared to the extended-butterfly fat tree, WK-recursive and diametrical mesh topologies, respectively. In addition, ScMesh achieves 41.22, 32.23, and 15.01 % lower energy consumption and 38.96, 27.43, and 18.21 % lower area overhead than the extended-butterfly fat tree, WK-recursive, and diametrical mesh topologies, respectively.     

改进遗传算法的并行任务调度

并行任务调度是一个NP完全问题,它关注资源的分配和并行任务调度,要求具有高性能的调度算法,且能求解出高质量的解。提出了一种基于改进遗传算法的并行任务调度算法,在算法初始化种群产生时引入任务向量矩阵来表示任务、资源以及调度的关系,并采用启发式方法得到初始化种群,提高种群质量;采用规则约束的交叉和变异操作,提高个体的质量;提出了加速进化策略,有效地避免了早熟。仿真实验结果表明,该改进算法能更有效地求解并行任务调度问题。