Shortest Path Search Algorithm in Optimal Two-Dimensional Circulant Networks: Implementation for Networks-on-Chip
For a family of optimal two-dimensional circulant networks with an analytical description, two new improved versions of the shortest path search algorithm with a constant complexity estimate are obtained. A simple, based on the geometric model of circulant graphs, proof of the formulas used for the shortest path search algorithm is given. Pair exchange algorithms are presented, and their estimates are given for networks-on-chip (NoCs) with a topology in the form of the considered graphs. New versions of the algorithm improve the previously proposed shortest path search algorithm for optimal generalized Petersen graphs with an analytical description. The new proposed algorithm is a promising solution for the use in NoCs which was confirmed by an experimental study while synthesizing NoC communication subsystems and comparing the consumed hardware resources with those when other previously developed routing algorithms.
For analytically defined families of three-dimensional circulant networks with a parametric description, an analytical algorithm for finding shortest paths which has a common scheme for all networks of the family based on a given generating function was developed. A comparative analysis of three routing algorithms (analytical Two-terminal routing algorithm, Coefficients search on graph generators, and Dijkstra’s algorithm) for a variety of circulant networks from an analytically defined family was carried out. Estimates of the effectiveness of the considered routing algorithms for use in networks-on-chip were obtained.
We address the complexity class of several problems related to finding a path in a properly colored directed graph. A properly colored graph is defined as a graph G whose vertex set is partitioned into X(G) stable subsets, where X(G) denotes the chromatic number of G. We show that to find a simple path that meets all the colors in a properly colored directed graph is NP-complete, and so are the problems of finding a shortest and longest of such paths between two specific nodes.
The article gives a review of existing methods of networks-on-chip design, based on the approach, in which the projection of the characteristic tasks graph is performed on a given regular topology. The general problem of the synthesis of networks-on-chip is characterized. The network topology can be foreknown (usually a regular topology) or selected in accordance with the tasks that will be performed by the network-on-chip. The first method of synthesis of networks-on-chip is widespread among the developers due to its relative simplicity and obviousness and presented in a variety of implementations, which are reviewed in this article. The advantages and disadvantages of this approach, the effect achieved by its application to various implementations of networks-on-chip and the way of its improvement, which is to extend the scope of solutions for regular network topologies on the predetermined irregular topologies with better characteristics are offered.
We consider the problem of describing 𝑛-vertex trees of diameter 𝑑 containing as few independent sets as possible. This problem is solved for 𝑑=6 and 𝑛>160, as well as for 𝑑=7 and 𝑛>400.
Modern transport systems are characterized by the development and implementation of intelligent transport technologies. Today, dynamic forecast models are not used in practice in the operation of a passenger terminal. Decision making is based on some regulatory values for passenger traffic, but this is not sufficient for efficient terminal management. Modern passenger terminals are characterized by dynamic process variability and consideration of diverse options, taking into account the criteria of safety, reliability analysis, and the continuous research of passenger processing. For any modern marine passenger terminal, it is necessary to use the tool to simulate passenger flows in dynamics. Only in this way it is possible to obtain the analytical information and use it for decision making when solving the problem of the amount of personnel required for passenger service, transport safety, some forecasting tasks and so on. Of particular relevance is the choice of the mathematical transport model and the practical conditions for the implementation of the model in the real terminal operation. In this article, the analysis technique of intelligent simulation-based terminal services provides a new mathematical model of passenger movement inside the terminal and presents a new software instrument. Moreover, the conditions of implementation of some transportation models during the operation of marine passenger terminal are examined. The study represents an example of analytical information used for the forecast of the terminal operations, the analysis of the workload and the efficiency of the organization of the marine terminal.
This book constitutes the joint refereed proceedings of the 17th International Conference on Next Generation Wired/Wireless Advanced Networks and Systems, NEW2AN 2017, the 10th Conference on Internet of Things and Smart Spaces, ruSMART 2017. The 71 revised full papers presented were carefully reviewed and selected from 202 submissions. The papers of NEW2AN focus on advanced wireless networking and applications; lower-layer communication enablers; novel and innovative approaches to performance and efficiency analysis of ad-hoc and machine-type systems; employed game-theoretical formulations, Markov chain models, and advanced queuing theory; grapheme and other emerging material, photonics and optics; generation and processing of signals; and business aspects. The ruSMART papers deal with fully-customized applications and services. The NsCC Workshop papers capture the current state-of-the-art in the field of molecular and nanoscale communications such as information, communication and network theoretical analysis of molecular and nanonetwork, mobility in molecular and nanonetworks; novel and practical communication protocols; routing schemes and architectures; design/engineering/evaluation of molecular and nonoscale communication systems; potential applications and interconnections to the Internet (e.g. the Internet of Nano Things).
The conference “2021 Systems of signals generating and processing in the field of on board communications” is organized with technical sponsorship of Russian (Moscow) IEEE Circuits and Systems (CAS04) Chapter IEEE Region 8, Russian Section Chapter, MTT/ED and Institute of Radio and Information Systems Association (IRIS), Vienna, Austria. The conference featured invited researchers, educators, managers, and graduate students, whose research activity, case studies or best practices, are shedding light on the theory or practice of engineering, include modern digital transportation systems design and technical operation, radio waves propagation, transmitting, receiving and processing signals in television and radio broadcasting devices, information technologies in transport. The main areas of the conference “Systems of signals generating and processing in the field of on board communications” include modern digital transportation systems design and technical operation, radio waves propagation, transmitting, receiving and processing signals in television and radio broadcasting devices, information technologies in transport. FIELD OF INTEREST: Components, Circuits, Devices and Systems; General Topics for Engineers; Signal Processing and Analysis. Reports presented at the conference are grouped in 6 sections: 1. Antennas and Radio Waves Propagation. 2. Navigation and Mathematical Algorithms of an Object Space Orientation. 3. Radiofrequency Applications. 4. Wire and Optical Communication and Control Systems. 5. Intelligent Transport Systems (ITS): Sub-section 1: Use of digital ITS infrastructure in telematic control systems on urban passenger transport Sub-section 2: Peculiarities of data exchange in cooperative ITS Sub-section 3: Theoretical Aspects of Artificial Intelligence Systems Development for Transportation Engineering Sub-section 4: Test methods of motor vehicles integrated into an intelligent transport environment 6. Digital signal processing in on-board radio systems
Описывается созданный макет манипулятора с биоэлектрическим управлением. Манипулятор сделан в форме человеческой ладони, движение пальцев которой управляется через электромиосигналы оператора. В среде LabVIEW разработан виртуальный прибор, позволяющий с помощью дискретного вейвлет-преобразования осуществить анализ электромиосигналов оператора, определить моменты мышечной активности и сформировать по результатам анализа сигналы управления манипулятором.
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