Home
>
Journals & magazines
>
IEE Proceedings - Computers and Digital Technique...
>
Volume 144
Issue 5
IEE Proceedings - Computers and Digital Techniques
Volume 144, Issue 5, September 1997
Volumes & issues:
Volume 144, Issue 5
September 1997
-
- Author(s): S. Coury and P.G. Harrison
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 249 –254
- DOI: 10.1049/ip-cdt:19971285
- Type: Article
- + Show details - Hide details
-
p.
249
–254
(6)
A new approach to the analysis of asymptotic properties of closed queuing networks with both constant service rates and, in certain cases, load-dependent service rates is developed. The method is based on a decomposition of the generating function of the normalising constant into simpler node functions which are easily inverted term by term. An exact closed form is obtained for the normalising constant in some cases and an approximation, based on an integral formula, in others. These results are applied to model a large computer system with terminals, which is also used to illustrate the main properties of the normalising constant and the system throughput function as the population increases. The authors' method is compared with others in terms of both accuracy and efficiency. Finally, it is indicated how multiclass networks can be handled, essentially by reduction to a collection of single class networks. - Author(s): K.H. Yeung and T.S. Yum
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 255 –260
- DOI: 10.1049/ip-cdt:19971466
- Type: Article
- + Show details - Hide details
-
p.
255
–260
(6)
RAID (redundant arrays of inexpensive disks) has gained much attention in the recent development of fast I/O systems. Of the five levels, the traditional mirrored disk array still provides the highest I/O rate for small ‘write’ transfers. This is because the mirrored disk array has no small ‘write’ problem which is found in other levels of RAID. The authors propose a novel RAID architecture for fast engineering database systems, called dynamic parity logging (DPL) disk array. DPL disk array has no small ‘write’ problem and can provide much higher ‘write’ throughput than other RAID architectures. DPL disk array also has journalling capability, which means that some older design versions are kept for future references. A queueing model for DPL disk array is built. Analytical results, supported by simulation, show that the DPL disk array can provide the highest ‘write’ throughput when compared to RAID levels 1, 4, and 5. - Author(s): F.-M. Yeh and S.-Y. Kuo
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 261 –266
- DOI: 10.1049/ip-cdt:19971370
- Type: Article
- + Show details - Hide details
-
p.
261
–266
(6)
An efficient variable ordering strategy for ordered binary decision diagrams (OBDD) based on interleaving the compacted clusters is proposed in this paper. The novelty of this method is to apply the divide-and-conquer approach to find a good variable ordering efficiently for circuits with a large number of I/Os. First, a given circuit is partitioned into a number of clusters according to the correlations among the fan-in cones. A good ordering for each cluster is obtained and then a good global ordering is derived by interleaving the orderings of individual clusters. In this way, the time-consuming process of searching good orderings is restricted within individual clusters each with a manageable number of input variables. This divide-and-conquer approach is able to obtain a good variable ordering more efficiently than existent methods for circuits with a large number of I/Os. One notable result from the method is that we are able to build the OBDD for the cs38417 circuit within 1000 seconds on a SPARC 20 with 128 M byte memory. - Author(s): S.N. Yanushkevich
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 267 –272
- DOI: 10.1049/ip-cdt:19971368
- Type: Article
- + Show details - Hide details
-
p.
267
–272
(6)
A method to solve logic Differential equations, i.e. equations containing Logic Derivatives of k-valued logic (MVL) functions is proposed. An initial Differential equation is represented by a system of k logic equations of k variables given as 0-polarity Reed-Muller canonical expansion. This system is solved by means of a truncated orthogonal transform algorithm. - Author(s): S.L. Hary and F. Özgüner
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 273 –278
- DOI: 10.1049/ip-cdt:19971369
- Type: Article
- + Show details - Hide details
-
p.
273
–278
(6)
Real-time applications are becoming increasingly demanding in terms of the computational power and the I/O bandwidth required. Massively parallel computers using wormhole routing are the most promising architectures to deliver scalable computational power efficiently. It follows that real-time applications will want to take advantage of these architectures. However, before real-time applications can exploit massively parallel architectures, mechanisms need to be developed to ensure that critical hard-deadline messages meet their deadlines. An off-line feasibility test for real-time wormhole-routed messages is presented. The test will work for any static priority assignment scheme. The effectiveness of several proposed priority assignment methods is evaluated using random (uniform) traffic patterns. Simulations using a flit level simulator (FLS) are performed to validate the test. Simulations show that a high degree of schedulability can be achieved with a finite number of virtual channels, and that packetising long messages increases the overall schedulability of the network. - Author(s): Ç.K. Koç and A.M. Apohan
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 279 –284
- DOI: 10.1049/ip-cdt:19971518
- Type: Article
- + Show details - Hide details
-
p.
279
–284
(6)
An algorithm for inverting an iteration of the one-dimensional cellular automaton is presented. The algorithm is based on the linear approximation of the updating function, and requires less than exponential time for particular classes of updating functions and seed values. For example, an n-cell cellular automaton based on the updating function CA30 can be inverted in O(n) time for certain seed values, and, at most, 2n/2 trials are required for arbitrary seed values. The inversion algorithm requires at most 2(q-1)(1-α)n trials for arbitrary nonlinear functions and seed values, where q is the number of variables of the updating function, and α is the probability of agreement between the function and its best affine approximation. The inversion algorithm coupled with the method of Meier and Staffelbach becomes a powerful tool to cryptanalyse the random number generators based on one-dimensional cellular automata, showing that these random number generators provide less security than their state size would imply. - Author(s): D.C. Hendry and D.S. Sananikone
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 285 –294
- DOI: 10.1049/ip-cdt:19971367
- Type: Article
- + Show details - Hide details
-
p.
285
–294
(10)
COSYN is an hardware/software partitioning tool for embedded systems with multiple hardware processes. It produces a system hardware/software partition whilst satisfying system constraints, where feasible. COSYN uses a CIPN (coloured interpreted Petri net) to model systems, and to provide simulation data for the partitioning algorithm. The CIPN provides modelling capability for multiple processes and interprocess communication primitives. The partitioning algorithm, which adopts a fine-grained approach to system partitioning (it considers moving nodes at the basic block level), is based on selecting blocks based on their potential speedup and extra hardware requirements, using hardware and software execution time estimators. The interdependence between interprocess communication primitives is exploited to achieve a better hardware/software partition. Results for an input example pdi using different partitioning algorithms are given which illustrate the benefits of the approach presented in this paper. - Author(s): S.-M. Moon
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 295 –303
- DOI: 10.1049/ip-cdt:19971283
- Type: Article
- + Show details - Hide details
-
p.
295
–303
(9)
Modern microprocessors that exploit instruction-level parallelism (ILP) require higher data cache bandwidth than sequential machines, since at least the same number of cache references (or more due to speculative execution) must be made in fewer clock cycles. To support the required bandwidth, multiport caches have been proposed, allowing the execution of multiple load/store instructions in a single cycle. Deciding the minimal number of cache ports that do not deeply affect performance is one of major resource allocation problems of ILP machines. Unfortunately, this decision is difficult to make for machines that exploit ILP in non-numerical code due to its irregularity. In this short paper, a comprehensive empirical study is performed on selected integer benchmarks using an aggressive ILP compiler aimed at characterising a suitable number of cache ports and at evaluating the metric of cache bandwidth. This study differs from previous ones in that the compiler can successfully exploit ILP in proportion to the amount of resources, thus measuring the performance impact of multiport caches more accurately. The results indicate that multiport caches that provide high bandwidth significantly improve the performance of ILP machines (i.e. as much as a geometric mean of 50%), yet there is a consistent upper bound on the number of required ports. - Author(s): C.-J. Hou ; K.S. Tsoi ; C.-C. Han
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 304 –316
- DOI: 10.1049/ip-cdt:19971527
- Type: Article
- + Show details - Hide details
-
p.
304
–316
(13)
The paper presents an effective application-transparent checkpointing/rollback scheme for multiple processes that communicate via message passing in a distributed system. The authors first propose a checkpointing scheme that uses the unforced checkpointing strategy and dynamically varies checkpoint intervals with respect to the frequency of message sending to reduce process rollback propagation. Additional forced checkpoints are taken only to achieve checkpoint consistency among processes and to avoid the domino effect. The authors then discuss both global rollback and minimal rollback approaches, and incorporate them into the proposed checkpointing scheme. The combined checkpointing/rollback scheme can handle out-of-order messages, achieve high concurrency during checkpointing/rollback operations, and allow multiple invocations of checkpointing/rollback instances. To reduce the space overhead a global recovery line determination approach to purge the checkpoints to which processes shall never rollback is proposed. Experiences with event-driven simulation indicate that the proposed scheme can effectively reduce rollback propagation, while incurring little control message overhead and maintaining at any time only a few checkpoints at each process. - Author(s): M.K. Dhodhi and I. Ahmad
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 317 –323
- DOI: 10.1049/ip-cdt:19971033
- Type: Article
- + Show details - Hide details
-
p.
317
–323
(7)
Tabu search is a promising optimisation heuristic that has been successfully applied to the solution of many combinatorial optimisation problems, yielding optimal or near optimal results. An efficient algorithm based on tabu search is presented, designated as TASS, for the problem of scheduling a tree-like task graph (task tree) onto linear arrays of processors, with the aim of minimising the system response time. The linear processor arrays implemented in VLSI/ULSI technology provide an affordable and cost-effective solution for special applications that can be represented by task trees. The performance of the proposed tabu search-based algorithm is evaluated for a set of test problems selected from the literature. Comparison of results obtained by the proposed algorithm with results reported by previous techniques, shows a considerable improvement in the system response time. - Author(s): K.-Y. Lam ; V.C.S. Lee ; S.-L. Hung ; B.C.M. Kao
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 324 –330
- DOI: 10.1049/ip-cdt:19971496
- Type: Article
- + Show details - Hide details
-
p.
324
–330
(7)
In the studies of distributed real-time database systems (DRTDBS), it is always assumed that earliest deadline first (EDF) is employed as the CPU scheduling algorithm. However, using purely (ultimate) deadline for priority assignment may not be suitable because different kinds of transactions, such as global and local transactions, may exist in the system. To improve the performance, more sophisticated priority assignment heuristics have to be employed. In the paper, the performance of different priority assignment heuristics for subtransactions in DRTDBS using optimistic concurrency control (OCC) protocol are investigated. It is found that purely deadline-driven heuristics, which suffice for distributed real-time systems, are not suitable for DRTDBS. On the other hand, the proposed heuristic, which considers both deadline constraint and data contention, can give the best performance. - Author(s): A. Basu ; A.K. Majumdar ; S. Sarkar
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 331 –341
- DOI: 10.1049/ip-cdt:19971442
- Type: Article
- + Show details - Hide details
-
p.
331
–341
(11)
To expedite the design process of a complex system, it is required to view the system as interactions of complex subsystems which are not necessarily RTL components and synthesise the hardware from such a specification. In the paper, an automated design and synthesis environment called DOORS has been proposed that can accept a complex system specification at such a high level of abstraction and synthesises the circuit. DOORS is based on an object-oriented design methodology. Circuit elements are treated as classes. The designer describes the circuit behaviour as a sequence of state transitions in response to external messages. The method executed in response to a message is transparent to the external world. The specification may involve presynthesised components whose functionalities are invoked by sending messages to them. The synthesis system of DOORS accepts the specification and synthesises the circuit in terms of these components. The authors have mainly concentrated on the datapath synthesis mechanism of DOORS. - Author(s): E. Macii and M. Poncino
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 343 –347
- DOI: 10.1049/ip-cdt:19971366
- Type: Article
- + Show details - Hide details
-
p.
343
–347
(5)
The use of symbolic data structures to store pseudo-Boolean (i.e. integer-valued) functions has proved to be extremely effective in handling both transform matrices and spectral representations of large Boolean functions. The authors propose a novel application of symbolic spectral analysis techniques to the prediction of the complexity of a combinational circuit. They present a symbolic formulation of the problem, and propose an implicit algorithm for its solution that performs well, in terms of both execution time and accuracy in the computation, on circuits that are sensibly larger than the ones usually handled by the tools currently available. Experimental results, collected on standard examples, are discussed to support this claim. - Author(s): T.H. Pan and C.L. Wey
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 144, Issue 5, p. 348 –352
- DOI: 10.1049/ip-cdt:19971517
- Type: Article
- + Show details - Hide details
-
p.
348
–352
(5)
Technology mapping is an important logic synthesis task transforming a multi-level logic network onto a set of library gates. Its primary goal is to achieve a realisable circuit which meets design constraints. Inverter pairs are generally inserted to all internal nodes of a network to increase the flexibility of mapping the subject network onto the library gates, but introducing inverter pairs may also increase the number of unwanted inverters in the mapped network. Thus, inverter minimisation is used during or after technology mapping to reduce the unwanted inverters and to further improve the quality of the mapped network. An efficient gate reassignment algorithm GRASS is presented for inverter minimisation in post technology mapping. Minimisation is achieved by re-assigning a gate to one of its NPN-equivalent gates to reduce the number of inverters and/or to use a smaller gate. Simulation results show that GRASS achieves 5.1% area improvement and 5.6% delay improvement for the recommended MCNC benchmark circuits. GRASS also achieves more than 25% inverter reduction over that in a former system.
Asymptotic properties of queuing networks
Dynamic parity logging disk arrays for engineering database systems
Variable ordering for ordered binary decision diagrams by a divide-and-conquer approach
Matrix method for solving multivalued logic differential equations
Feasibility test for real-time communication using wormhole routing
Inversion of cellular automata iterations
Hardware/software partitioning of embedded systems with multiple hardware processes
Increasing cache bandwidth using multiport caches for exploiting ILP in non-numerical code
Effective and concurrent checkpointing and recovery in distributed systems
Task tree scheduling onto linear arrays using tabu search
Priority assignment in distributed real-time databases using optimistic concurrency control
DOORS: An object-oriented CAD system for high level synthesis
Predicting the complexity of large combinational circuits through symbolic spectral analysis of their functional specifications
GRASS: An efficient gate re-assignment algorithm for inverter minimisation in post technology mapping
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.