6244297
A layered communication system generator
Abstract Although many approaches have been proposed for modeling and automatically validating communication protocol entities, no approaches have been proposed for automatically implementing various layered communication systems. In the article, we propose a layered communication system generator that can automatically implement various layered communication systems. The layered communication system generator is established on the basis of a generalized communication system framework. In addition, a layered communicating finite state machine is introduced to specify the layered communication systems, and a matrix approach is proposed for protocol validation. We have implemented the proposed layered communication system generator in DOS and UNIX environments, in which several real-world protocols from Department of Defense and IEEE 802 standards organizations have been successfully developed.
30765152
On the Quickest Path Problem
Abstract Let N be an input network and σ be the amount of data to be transmitted. We present an O( mn 2 ) time algorithm that finds all-pairs quickest paths, for a given value of σ, and show that the quickest path between any two nodes for any value of σ can be found in O(log m ) time, provided O( mn 2 ) preprocessing time is spent.
35779178
On the Quickest Path Problem
In this paper, we propose an O(mn2) time algorithm that finds all-pairs quickest paths in a given network N, where n and m are the numbers of nodes and arcs, respectively, in N. Besides, the quickest path between any two nodes can be determined in O(log m) time, provided O(mn2) time preprocessing is made.
11356017
Loop Transformations for Reducing Data Space Requirements of Resource-Constrained Applications
Embedded computing platforms are often resource constrained, requiring great design and implementation attention to memory, power and heat related parameters. An important task for a compiler in such platforms is to simplify the process of developing applications for limited memory devices and resource constrained clients. Focusing on array-intensive embedded applications, this work explores how loop-based compiler optimizations can be used for increasing memory location reuse. Our goal is to transform a given application in such a way that the resulting code has fewer cases (as compared to the original code) where the lifetimes of array elements overlap. The reduction in lifetimes of array elements can then be exploited by reusing memory locations as much as possible. Our results indicate that the proposed strategy reduces data space requirements of ten resource constrained applications by more than 40% on the average.
5887540
An Algorithm for Computing a New Normal Form for Dynamical Systems
We propose in this paper a new normal form for dynamical systems or vector fields which improves the classical normal forms in the sense that it is a further reduction of the classical normal forms. We give an algorithm for an effective computation of these normal forms. Our approach is rational in the sense that if the coefficients of the system are in a field K(which, in practice, is Q, R), so is the normal form and all computations are done inK . As a particular case, if the matrix of the linear part is a companion matrix then we reduce the dynamical system to a single differential equation. Our method is applicable for both the nilpotent and the non-nilpotent cases. We have implemented our algorithm in Maple V and obtained many examples of the further reduced normal forms up to some finite order.
41643555
A Fuzzy Dead Reckoning Algorithm for Distributed Interactive Applications
A fuzzy Dead Reckoning (DR) algorithm for distributed interactive applications is proposed in this paper. Since fixed threshold cannot adequately handle the dynamic relationships between moving entities, some multi-level threshold DR algorithms were proposed in the past few years. In these algorithms the level of threshold is adaptively adjusted based on the distance between entities. The proposed fuzzy DR algorithm is based on multi-level threshold DR algorithm and takes all properties of entity (e.g. position, size and view angle etc.) into consideration when adjusting the level of threshold. This algorithm employs fuzzy correlation degree to measure the relationships between entities and determine the level of threshold for DR algorithm. Fuzzy consistent relation is used to distribute weight for each property. Simulation results indicate that fuzzy DR algorithm can achieve a considerable reduction in the number of state update messages while maintaining adequate accuracy in extrapolation.
11193384
Compiler-directed voltage scaling on communication links for reducing power consumption
Reducing power consumption of communication networks is an important optimization goal in many application domains, ranging from large-scale simulation codes to embedded multi-media applications. Most of the prior efforts on network power optimization are hardware-based schemes. These schemes are predictive by definition as they control communication link status based on the observations made In the past. Since prediction may not be very accurate most of the time, these approaches can result in overheads in terms of both performance and power. This paper proposes a compiler driven approach to communication link voltage management. In this approach, an optimizing compiler analyzes the application code and extracts the data communication pattern among parallel processors. This information along with network topology is used for identifying the link access patterns. These patterns and the inherent data dependence information of the underlying code help the compiler decide the optimum voltages/frequencies to be used for communication links at a given time frame. Our focus in this work is on loop-intensive codes which frequently appear in data intensive video and image processing. We exploit the regularity in data accesses of these codes to abstract out their inter-processor communication patterns, which In turn enable us select the most appropriate voltage/frequency level to employ for each communication link at any time.
11486473
Circumference of Graphs with Bounded Degree
Karger, Motwani, and Ramkumar Algorithmica, 18 (1997), pp. 82--98] have shown that there is no constant approximation algorithm to find a longest cycle in a Hamiltonian graph, and they conjectured that this is the case even for graphs with bounded degree. On the other hand, Feder, Motwani, and Subi [SIAM J. Comput., 31 (2002), pp. 1596--1607] have shown that there is a polynomial time algorithm for finding a cycle of length $n^{\log_32}$ in a 3-connected cubic n-vertex graph. In this paper, we show that if G is a 3-connected n-vertex graph with maximum degree at most d, then one can find, in O(n3) time, a cycle in G of length at least $\Omega(n^{\log_b2})$, where $b=2(d-1)^2+1$.