Home
>
Journals & magazines
>
IEE Proceedings - Computers and Digital Technique...
>
Volume 143
Issue 3
IEE Proceedings - Computers and Digital Techniques
Volume 143, Issue 3, May 1996
Volumes & issues:
Volume 143, Issue 3
May 1996
-
- Author(s): M. Golden and T. Mudge
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 3, p. 161 –167
- DOI: 10.1049/ip-cdt:19960359
- Type: Article
- + Show details - Hide details
-
p.
161
–167
(7)
Two pipeline structures that are employed in commercial microprocessors are examined. The first is the load-use interlock (LUI) pipeline, which employs an interlock to ensure correct operation during load-use hazards. The second is the address-generation interlock (AGI) pipeline. It eliminates the load-use hazard but has an address-generation hazard, which requires an address-generation interlock for correct operation. The performance of these two pipelines on existing binaries and on applications that have been recompiled with a local code scheduler that understands the difference in the pipeline structures is compared. Under the assumption of perfect branch prediction, the AGI pipeline outperforms the LUI pipeline on the SPEC92 integer benchmarks, even on binaries that have been compiled for the LUI pipe. When branch prediction is considered the AGI pipeline performs significantly better than the LUI pipeline if branch prediction is more than 80% accurate and the data cache access time is greater than two cycles. Recompiling the benchmarks with a new local code scheduler optimised for the AGI pipeline provides little additional performance improvement. - Author(s): C.-H. Chen and D.-L. Yang
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 3, p. 168 –173
- DOI: 10.1049/ip-cdt:19960380
- Type: Article
- + Show details - Hide details
-
p.
168
–173
(6)
Distance transformation has been widely applied to image matching and shape analysis. The hardware implementation of distance transformation is necessary because real-time (video rate) processing is required for most applications. The paper proposes a four-pass algorithm for distance transformation. Its computation complexity is the same as a two-pass raster scan algorithm but the data dependencies are simpler and therefore more suitable for designing hardware architectures. Systolic arrays are very amenable to VLSI implementation. They are especially suited to a special class of computation-bound algorithms with regular, localised data flow. In the paper the authors design a systolic array for the proposed four-pass algorithm and use the multilevel pipelining technique to improve the performance. Its speed is 2.4 times, and the cost is 2/3 times, that of a systolic array designed using the two-pass raster scan algorithm. - Author(s): S. Bhattacharjee ; S. Sinha ; C. Chattopadhyay ; P.P. Chaudhuri
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 3, p. 174 –180
- DOI: 10.1049/ip-cdt:19960381
- Type: Article
- + Show details - Hide details
-
p.
174
–180
(7)
The paper utilises a particular class of nongroup CA as a mathematical tool to derive solutions of XOR-dominated Boolean equations. Some problems in digital circuits (such as logic synthesis, test pattern generation etc.) demand efficient schemes for the solution of Boolean equations. A large number of combinational benchmarks and real-life circuits used in the fields of built-in self-test (BIST) structures, cryptography, error-correcting codes etc. can be found to have dominance of such XOR functionality. The proposed scheme is suited to such XOR dominated circuits. A comparison between the execution time of the proposed method and popular schemes based on tabular algebra shows a maximum speedup of up to ten times. In the worst case, the performance of the algorithm presented is equivalent to that of tabular algebra, which is inescapable since the problem is inherently NP-hard. - Author(s): V.B. Muchnick and A.V. Shafarenko
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 3, p. 181 –188
- DOI: 10.1049/ip-cdt:19960333
- Type: Article
- + Show details - Hide details
-
p.
181
–188
(8)
The placement of elemental operations (as opposed to data) of a data-driven data-parallel computation in a network of processors is examined. A fast suboptimal algorithm is proposed for such placement which tends to minimise the overall network load when the computation is essentially nonlocal. The cases of grid, torus and hypercube topology are considered. It is shown that the proposed algorithm, while having moderate computational complexity, demonstrates up to a 50% reduction in required network throughput over some straightforward placement schemes in the practical range of network sizes. - Author(s): K.P. Lam and C.W. Tong
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 3, p. 189 –195
- DOI: 10.1049/ip-cdt:19960379
- Type: Article
- + Show details - Hide details
-
p.
189
–195
(7)
The Bellman–Ford algorithm is well known for providing a dynamic programming solution for the shortest path problem. Alternatively, the closed semiring is an algebraic structure which unifies a family of path problems, including all-pairs shortest path, transitive closure and minimum spanning tree, defined on directed or undirected graphs. This paper proposes a connectionist network architecture, called the binary relation inference network, which incorporates the Bellman–Ford computation for solving closed semiring problems. The extension and summary operators of closed semirings correspond to the site and unit functions of the network. The inference network structure offers an obvious advantage of being simply extensible for asynchronous and continuous-time operation. Implementation in analogue processing circuits promises a practical problem size independence in the solution time. VLSI circuits are also presented and limiting factors of performance are discussed, with particular reference to the minimum spanning tree problem. - Author(s): N.-Y. Lee and T. Hwang
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 3, p. 196 –198
- DOI: 10.1049/ip-cdt:19960335
- Type: Article
- + Show details - Hide details
-
p.
196
–198
(3)
In 1994, Harn proposed a digital signature scheme which was claimed to be unbreakable if the factorisation and the discrete logarithms are simultaneously unsolvable. The paper shows that ‘hackers’ can forge the signatures of Harn schemes with high probabilities, if they can solve the discrete logarithms modulo a large prime number. The Harn signature scheme is modified to give it the same degree of security as was originally claimed. - Author(s): A.A. Amin ; A.A. Hamzah ; R.E. Abdel-Aal
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 3, p. 199 –202
- DOI: 10.1049/ip-cdt:19960334
- Type: Article
- + Show details - Hide details
-
p.
199
–202
(4)
The testability problem of word-oriented memories (WOMs) for pattern sensitive faults is addressed. A novel design for testability (DFT) strategy allows efficient built-in self-testing (BIST) of WOMs. By proper selection of the memory array tiling scheme, it is possible to implement O(√n) BIST algorithms which test WOMs for various types of neighbourhood pattern sensitive faults (NPSFs). The inputs of the column decoders are modified to allow parallel writing into multiple words, and coincidence comparators are added to allow parallel verification of row data with minimal effect on chip area and performance. - Author(s): B.J. Falkowski
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 3, p. 203 –204
- DOI: 10.1049/ip-cdt:19960382
- Type: Article
- + Show details - Hide details
-
p.
203
–204
(2)
Comparison of two common pipeline structures
Fast algorithm and its systolic realisation for distance transformation
Cellular automata based scheme for solution of Boolean equations
Dynamic evaluation strategy for fine-grain data-parallel computing
Closed semiring connectionist network for the Bellman–Ford computation
Modified Harn signature scheme based on factorising and discrete logarithms
Generic DFT approach for pattern sensitive faults in word-oriented memories
Comment on ‘KGPMAP: library-based technology-mapping technique for antifuse based FPGAs’
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.