Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions

The simplicity of regular mesh topology Network on Chip (NoC) architecture leads to reductions in design time and manufacturing cost. A weakness of the regular shaped architecture is its inability to efficiently support cores of different sizes. A proposed way in literature to deal with this is to utilize the region concept, which helps to accommodate cores larger than the tile size in mesh topology NoC architectures. Region concept offers many new opportunities for NoC design, as well as provides new design issues and challenges. One of the most important among these is the design of an efficient deadlock free routing algorithm. Available adaptive routing algorithms developed for regular mesh topology cannot ensure freedom from deadlocks. In this paper, we list and discuss many new design issues which need to be handled for designing NoC systems incorporating cores larger than the tile size. We also present and compare two deadlock free routing algorithms for mesh topology NoC with regions. The idea of the first algorithm is borrowed from the area of fault tolerant networks, where a network topology is rendered irregular due to faults in routers or links, and is adapted for the new context. We compare this with an algorithm designed using a methodology for design of application specific routing algorithms for communication networks. The application specific routing algorithm tries to maximize adaptivity by using static and dynamic communication requirements of the application. Our study shows that the application specific routing algorithm not only provides much higher adaptivity, but also superior performance as compared to the other algorithm in all traffic cases. But this higher performance for the second algorithm comes at a higher area cost for implementing network routers.     

Store-and-Forward Multicast Routing on the Mesh

We study the complexity of routing a set of messages with multiple destinations (multicast routing) on an n-node square mesh under the store-and-forward model. A standard argument proves that time is required to route n messages, where each message is generated by a distinct node and at most c messages are to be delivered to any individual node. The obvious approach of simply replicating each message into the appropriate number of unicast (single-destination) messages and routing these independently does not yield an optimal algorithm. We provide both randomized and deterministic algorithms for multicast routing, which use constant-size buffers at each node. The randomized algorithm attains optimal performance, while the deterministic algorithm is slower by a factor of O( log ² n). We also describe an optimal deterministic algorithm that, however, requires large buffers of size O(c). A preliminary version of this paper appeared in Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, Crete, Greece, 2001. This work was supported, in part, by MIUR under project ALGO-NEXT.     

基于总线网络的确定寻径算法剖析

通过建立一个ｎ×ｎ二维总线网络上的消息传递模型,分析了基于总线网络的确定寻径算法性能,得出了任何基于ｎ×ｎ二维总线网络的确定寻径算法都至少需要１．５ｎ步的结论。并由此推广到多维总线网络,得出结点总数为Ｎ的δ维总线网络上的确定寻径算法需要步。     

Probabilistic analysis on mesh network fault tolerance

Mesh networks are among the most important interconnection network topologies for large multicomputer systems. Mesh networks perform poorly in tolerating faults in the view of worst-case analysis. On the other hand, such worst cases occur very rarely in realistic situations. In this paper, we study the fault tolerance of 2-D and 3-D mesh networks under a more realistic model in which each network node has an independent failure probability. We first observe that if the node failure probability is fixed, then the connectivity probability of these mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacture to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. We develop a novel technique to formally derive lower bounds on the connectivity probability for 2-D and 3-D mesh networks. Our study shows that these mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. For example, it is formally proved that as long as the node failure probability is bounded by 0.5%$0.5\%$, a 3-D mesh network of up to a million nodes remains connected with a probability larger than 99%$99\%$.     

三维图形引擎中骨骼蒙皮动画的一种实现方法*

提出了三维图形引擎中骨骼蒙皮动画的一种实现方法,即将现有的关节动画与单一网格动画相结合,利用骨架的继承变换和顶点混合技术使骨骼蒙皮动画平滑逼真。实验表明该方法有良好的显示效果,并具有较好的实时性,且占用的存储空间不大,能够满足当前三维图形引擎对动画技术的要求。     

一种视相关的网格简化方法*

针对网格模型的实时显示问题提出了一种视相关的网格简化方法。在网格简化中,将影响图形对象重要性的视觉敏感度与图形对象在屏幕上投影面积两者有效结合,实现网格模型的实时大幅度简化, 实验结果表明,简化速度快,但显示并无明显失真。     

A parallel algorithm for approximate regularity

Spatial regularity amidst a seemingly chaotic image is often meaningful. Many papers in computational geometry are concerned with detecting some type of regularity via exact solutions to problems in geometric pattern recognition. However, real-world applications often have data that is approximate, and may rely on calculations that are approximate. Thus, it is useful to develop solutions that have an error tolerance.

A solution has recently been presented by Robins et al. [Inform. Process. Lett. 69 (1999) 189–195] to the problem of finding all maximal subsets of an input set in the Euclidean plane that are approximately equally-spaced and approximately collinear. This is a problem that arises in computer vision, military applications, and other areas. The algorithm of Robins et al. is different in several important respects from the optimal algorithm given by Kahng and Robins [Patter Recognition Lett. 12 (1991) 757–764] for the exact version of the problem. The algorithm of Robins et al. seems inherently sequential and runs in O(n^5/2) time, where n is the size of the input set. In this paper, we give parallel solutions to this problem.     

An efficient generation method of embedded reinforcement in hexahedral elements for reinforced concrete simulations

In this paper, an automatic procedure for the generation of embedded steel reinforcement inside hexahedral finite elements is presented. The automatic mapping of the entire reinforcement network inside the concrete hexahedral finite elements is performed using the end-point coordinates of the rebar reinforcement macro-elements. By introducing a geometrical constraint, this procedure decreases significantly the computational effort for generating the input data of the embedded rebar elements in three-dimensional finite-element analysis, particularly when dealing with relatively large-scale reinforced concrete models. The computational robustness and efficiency of the proposed mesh generation method are demonstrated through numerical experiments.     

基于网络编码的分簇无线Mesh网络路由协议

传统的网络编码算法会增加网络的复杂性.为此,引入分簇的思想,提出一种基于网络编码的分簇无线Mesh网络路由协议以及一个用于平面型无线混合Mesh网络的分簇算法,根据相关性计算网络节点的度值,实现无线Mesh网络层次结构的划分.仿真结果表明,该协议能在一定程度上减小网络编码的复杂性.     

嵌入式软件可靠性仿真测试环境框架

提出了一种针对嵌入式软件进行可靠性测试的仿真测试环境框架。分析了仿真测试环境的系统特性并对其功能组件进行了介绍，对测试环境中的测试运行时组件进行了功能需求的分析，构建出测试运行时组件的框架实现，借助于UML中的抽象类图和顺序图描述对框架的静态特征和动态特征作了介绍，总结了利用框架实现仿真测试环境的优势。