Development of routing algorithms in networks-on-chip based on two-dimensional optimal circulant topologies
This work is devoted to the study of application of new topologies in the design of networks‑on‑chip (NoCs). It is proposed to use two‑dimensional optimal circulant topologies for NoC design, and it is developed an optimized routing algorithm with the decreased memory usage. The proposed routing algorithm was compared with Table routing, Clockwise routing, and Adaptive routing algorithms, previously developed for ring circulant topologies, and specialized routing algorithm for multiplicative circulants. The results of synthesis of routers implementing proposed routing algorithms are presented. The cost of ALM and register resources for the implementation of communication subsystems in NoCs with circulant topologies is estimated.
The main approaches to the synthesis of networks-on-chip based on regular and specialized topologies are analyzed. The optimality criteria of the topologies of networks-on-chip and a new class of quasi-optimal topologies and methods for their synthesis are proposes. The requirements for quasi-optimal topologies are defined. By using the mathematical methods of optimization the analysis of the obtained quasi-optimal topologies for the number of nodes of 25 is performed. It is shown, that their properties are close to the theoretically possible optimal topologies to not less than 96.3%.
This article gives a review of existing methods of designing of networks‑on‑chip (NoC), based on the approach that makes the projection of the characteristic task graph on a given regular topology. The general problem of NoC synthesis is characterized. The network topology can be either specialized and selected depending on the tasks to be performed or can be known in advance, in most cases, a regular topology. The method of NoC synthesis by adjusting for a specific task is analyzed. The advantages and disadvantages of this approach and the effect, achieved by its use for various implementations of NoCs are shown. The way to improve the NoC synthesis by using pre-defined irregular topologies with better characteristics is proposed.
Various approaches to networks on chip organizing are considered. Тhe main drawback of networks on chip packet switching is identified – an excessively large buffers amounts of input and output buffers of routers. The new router architecture with improved resource consumption and high speed action is offered. Figs: 5. Ref.: 12 titles.
The synthesis of network-on-chip topologies, based on the evolutionary computations method is proposed. The optimality criteria of the network-on-chip topologies and a new class of quasi-optimal topologies are proposed. The requirements for quasi-optimal topologies are defined. The genetic algorithm GeNoC for the synthesis of quasi-optimal networks-on-chip topologies with the number of nodes up to 100 is developed. By using the mathematical methods of optimization the analysis of the obtained quasi-optimal topologies is performed. The importance coefficients correction method of the objective function in the synthesis of quasi-topologies is proposed; as a result, the difference in their performance compared to theoretically possible optimal topologies is reduced up to 1.8%.
On the basis of an integrated network-on-chip (NoC) topologies optimality criterion, as well as applying the adjacency matrix to describe NoC topologies, exhaustive search method and its modification by using branch and bound and Monte Carlo methods are extended to the synthesis of NoC quasi-optimal topologies. Designed ScaNoC suboptimal topology synthesis algorithm is implemented on a high-level programming language which makes it possible to generate quasi-optimal topological solutions in accordance with the requirements to reduce hardware costs and the average distance between nodes. Proposed quasi-optimal topologies synthesis algorithm improvement by using the method of parallel computing allows speeding up the process of synthesis to 2117 times and getting topologies with the number of nodes up to 18.
A model for organizing cargo transportation between two node stations connected by a railway line which contains a certain number of intermediate stations is considered. The movement of cargo is in one direction. Such a situation may occur, for example, if one of the node stations is located in a region which produce raw material for manufacturing industry located in another region, and there is another node station. The organization of freight traﬃc is performed by means of a number of technologies. These technologies determine the rules for taking on cargo at the initial node station, the rules of interaction between neighboring stations, as well as the rule of distribution of cargo to the ﬁnal node stations. The process of cargo transportation is followed by the set rule of control. For such a model, one must determine possible modes of cargo transportation and describe their properties. This model is described by a ﬁnite-dimensional system of diﬀerential equations with nonlocal linear restrictions. The class of the solution satisfying nonlocal linear restrictions is extremely narrow. It results in the need for the “correct” extension of solutions of a system of diﬀerential equations to a class of quasi-solutions having the distinctive feature of gaps in a countable number of points. It was possible numerically using the Runge–Kutta method of the fourth order to build these quasi-solutions and determine their rate of growth. Let us note that in the technical plan the main complexity consisted in obtaining quasi-solutions satisfying the nonlocal linear restrictions. Furthermore, we investigated the dependence of quasi-solutions and, in particular, sizes of gaps (jumps) of solutions on a number of parameters of the model characterizing a rule of control, technologies for transportation of cargo and intensity of giving of cargo on a node station.
Generalized error-locating codes are discussed. An algorithm for calculation of the upper bound of the probability of erroneous decoding for known code parameters and the input error probability is given. Based on this algorithm, an algorithm for selection of the code parameters for a specified design and input and output error probabilities is constructed. The lower bound of the probability of erroneous decoding is given. Examples of the dependence of the probability of erroneous decoding on the input error probability are given and the behavior of the obtained curves is explained.
Event logs collected by modern information and technical systems usually contain enough data for automated process models discovery. A variety of algorithms was developed for process models discovery, conformance checking, log to model alignment, comparison of process models, etc., nevertheless a quick analysis of ad-hoc selected parts of a journal still have not get a full-fledged implementation. This paper describes an ROLAP-based method of multidimensional event logs storage for process mining. The result of the analysis of the journal is visualized as directed graph representing the union of all possible event sequences, ranked by their occurrence probability. Our implementation allows the analyst to discover process models for sublogs defined by ad-hoc selection of criteria and value of occurrence probability
Let G be a semisimple algebraic group whose decomposition into the product of simple components does not contain simple groups of type A, and P⊆G be a parabolic subgroup. Extending the results of Popov , we enumerate all triples (G, P, n) such that (a) there exists an open G-orbit on the multiple flag variety G/P × G/P × . . . × G/P (n factors), (b) the number of G-orbits on the multiple flag variety is finite.
I give the explicit formula for the (set-theoretical) system of Resultants of m+1 homogeneous polynomials in n+1 variables