Home
>
Journals & magazines
>
IEE Proceedings - Computers and Digital Technique...
>
Volume 144
Issue 3
IEE Proceedings - Computers and Digital Techniques
Volume 144, Issue 3, May 1997
Volumes & issues:
Volume 144, Issue 3
May 1997
-
- Author(s): B. Albert and A.P. Jayasumana
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 3, p. 149 –154
- DOI: 10.1049/ip-cdt:19971127
- Type: Article
- + Show details - Hide details
-
p.
149
–154
(6)
Simulators are valuable tools; they help in understanding how complex systems will operate and perform without actually having to build a physical model to test. However, they often require extensive development and run times. This is especially true for many networks such as FDDI, where a large number of nodes and priority classes are involved. A high-level algorithm is presented to evaluate the performance characteristics of a token LAN. The goal of the research was to find a method for obtaining an estimate of the average access delay, and the average end-to-end delay of advanced token-ring networks. The FDDI (fibre distributed data interface) standards were used as the basis of a FFOL (FDDI follow-on LAN) solution. A method was developed that will generate exact results for such networks at low- to medium-load network environments. As the load level increases, the error rate of the estimate also increases; this however is monitored and can be used as a confidence measure for the results obtained. A symmetric multimedia environment is used in the model, with bimodal traffic consisting of short data packets, and longer video packets. A short introduction to the network setup and the examination of the method developed is presented in single and multinetwork environments. Specific network parameters were chosen for these experiments, but the method is easy to customise to other network parameters. - Author(s): L.-P. Ku and H.W. Leong
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 3, p. 155 –162
- DOI: 10.1049/ip-cdt:19971158
- Type: Article
- + Show details - Hide details
-
p.
155
–162
(8)
The authors consider the optimum partitioning problem defined as follows: given a rectilinear layout ℒ consisting of n rectangles, it is desirable to partition (decompose) the remaining free space into rectangular free blocks using horizontal and/or vertical partition edges such that the number of free blocks is minimised. The authors give a new formula for counting the number of free blocks in any partition of a given layout. Based on the new formula, they show that the optimum partitioning problem reduces to the problem of finding a maximum independent vertex set (MIS) in a bipartite graph. They then give an O(n2.5) optimum partitioning algorithm (OPA) for computing an optimum partition. This optimum partitioning algorithm can be used to improve the space and time complexities of many applications where space partitioning is encountered. One example is the corner stitching data structure used for design rule checker (DRC) in the layout system Magic. In the experiments, the space complexity of the corner stitching data structure can be improved by an average of 13% by using the proposed optimum partitioning. Other applications are also presented. - Author(s): K.P. Lam and C.W. Tong
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 3, p. 163 –168
- DOI: 10.1049/ip-cdt:19970824
- Type: Article
- + Show details - Hide details
-
p.
163
–168
(6)
Dynamic programming is well known as a powerful modelling technique for dealing with the issue of making optimal decisions sequentially. Many practical problems, such as finding shortest paths in route planning, and multi-stage optimal control, can be formulated as special cases of the general sequential decision process. The paper proposes a connectionist network architecture, called the binary-relation inference network, which solves a special class of dynamic programming problems in the continuous time. They include the all-pair solutions for a family of closed semi-ring path problems, such as shortest paths, transitive closure, minimum spanning tree, and minimax path problems. The all-pair inference network specifies a basic and uniform computation of its individual units, which then collectively emerge towards a global optimal solution. The computational order in its discrete-time variants, either as synchronous or asynchronous networks, bears a close resemblance to the Floyd–Warshall algorithm and doubling algorithm. However, the continuous-time inference network offers a significant speed advantage if its non-sequential computation nature can be exploited. Simulation results of using analogue VLSI implementation of the inference network for solving shortest-path problems are promising. - Author(s): S.-C. Chern ; T.-C. Tuan ; J.-S. Jwo
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 3, p. 169 –173
- DOI: 10.1049/ip-cdt:19970914
- Type: Article
- + Show details - Hide details
-
p.
169
–173
(5)
In the paper, the authors show that the two uni-directional hypercubes, namely UHC1n and UHC2n, proposed by Chou and Du as interconnection schemes, are Hamiltonian. In addition, the authors show that if n is even, both architectures are vertex symmetric, and that if n is odd, both architectures have exactly two vertex-symmetric components. Furthermore, the study of the symmetry leads to an effective analysis of the maximum delay of one-port one-to-all broadcasting for either architecture which is at most ⌈1.5n⌉. - Author(s): A.J. Field and P.G. Harrison
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 3, p. 175 –186
- DOI: 10.1049/ip-cdt:19970823
- Type: Article
- + Show details - Hide details
-
p.
175
–186
(12)
The authors present a new analytical performance model of the IEEE P1596 Standard Coherent Interface, which is a distributed cache-coherency protocol for shared-memory multiprocessors. The paper focuses upon an implementation of the protocol on a unidirectional ring architecture (the ‘default’ architecture for SCI systems). The authors identify the possible memory and cache-line states and corresponding processor actions for a memory access, and derive the equilibrium line state probabilities by solving a Markov model expressed as a set of fixed-point equations. The probabilities of a processor performing a particular action then follow, from which the message transmission profile for each processor is derived. These traffic equations are then fed into an M/G/1 model for the ring architecture, in which the ring traffic at a node has priority over traffic originating in that node. Further analysis then leads to the mean message transmission time, and hence the mean memory access time and processor utilisation. The application of the model is illustrated by undertaking a performance comparison of two alternative node architectures and report some numerical results are reported for various parameterisations. - Author(s): R. Drechsler and B. Becker
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 3, p. 187 –193
- DOI: 10.1049/ip-cdt:19971154
- Type: Article
- + Show details - Hide details
-
p.
187
–193
(7)
An overview on decision diagrams (DDs) is given. DDs are the state-of-the-art data structure in verification and logic synthesis. They are widely used, and are integrated into commercial tools. The overview is incomplete in the sense that not all DDs are considered, but the authors mention the most important DDs, with practical relevance. DDs with special emphasis on the aspect of function representation at bit-level and word-level are considered. - Author(s): B.R. Swim ; M. Benmaiza ; M. Tayli ; M.C. Woodward
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 3, p. 195 –207
- DOI: 10.1049/ip-cdt:19970825
- Type: Article
- + Show details - Hide details
-
p.
195
–207
(13)
Future dynamic distributed hard real-time systems may control unpredictable environments, and will need predictable and flexible runtime systems that can handle unknown and changing task populations. In this extreme case not only is task scheduling dynamic, but the system topology and architecture might be adapted to unforeseen configurations. The paper addresses the difficult problem of dynamic distributed task scheduling. A new predictable dynamic deadline guarantee scheme has been designed and implemented in the authors' real-time distributed operating system (RTDOS). The algorithms have been proven to guarantee task deadlines even during transient overloads. RTDOS is designed to tackle unpredictable and highly dynamic environments; therefore its task model is quite unrestrictive, supporting periodic and aperiodic tasks both with arbitrary release times and deadlines. The authors place no restriction on the inter-arrival times between successive aperiodic task instances. Moreover, their resource scheduling considers precedence constraints, device allocation and communication requirements. As a consequence, the results can be generalised and applied to many real-time domains. Furthermore, the complexity of the authors' schedulability test has been proved to be O(n). A domain-wide scheduler is described, which maintains its predicted maximum response time even when local nodes are under heavy load. Experimental results confirm the proven expectations of our scheduling scheme.
Performance analysis of FDDI LANs using numerical methods
Optimum partitioning problem for rectilinear VLSI layout
Connectionist network for dynamic programming problems
Hamiltonicity, vertex symmetry, and broadcasting of uni-directional hypercubes
Stochastic model of a cache-coherency overhead in SCI rings
Overview of decision diagrams
Predictable distributed dynamic scheduling in RTDOS
Most viewed content for this Journal
Article
content/journals/ip-cdt
Journal
5
Most cited content for this Journal
We currently have no most cited data available for this content.
