IEEE Transactions on Computers, Volume 47

Volume 47, Number 1, January 1998

Special Issue on Dependability of Computing Systems

• 
  Dinos Moundanos, Jacob A. Abraham, Yatin Vasant Hoskote:
  Abstraction Techniques for Validation Coverage Analysis and Test Generation. 2-14
• 
  Fran Hanchek, Shantanu Dutt:
  Methodologies for Tolerating Cell and Interconnect Faults in FPGAs. 15-33
• 
  Elias Procópio Duarte Jr., Takashi Nanya:
  A Hierarachical Adaptive Distributed System-Level Diagnosis Algorithm. 34-45
• 
  Seungjae Han, Kang G. Shin:
  A Primary-Backup Channel Approach to Dependable Real-Time Communication in Multihop Networks. 46-61
• 
  Michael Nicolaidis:
  Fail-Safe Interfaces for VLSI: Theoretical Foundations and Implementation. 62-77
• 
  Jean-Charles Fabre, Tanguy Pérennou:
  A Metaobject Architecture for Fault-Tolerant Distributed Systems: The FRIENDS Approach. 78-95
• 
  Sachin Garg, Antonio Puliafito, Miklós Telek, Kishor S. Trivedi:
  Analysis of Preventive Maintenance in Transactions Based Software Systems. 96-107
• 
  David T. Stott, Gregory L. Ries, Mei-Chen Hsueh, Ravishankar K. Iyer:
  Dependability Analysis of a High-Speed Network Using Software-Implemented Fault Injection and Simulated Fault Injection. 108-119

Brief Contributions

• 
  Mario Blaum, Jehoshua Bruck, Kurt Rubin, Wilfried Lenth:
  A Coding Approach for Detection of Tampering in Write-Once Optical Disks. 120-125
• 
  Richard W. Linderman, Ralph L. R. Kohler, Mark H. Linderman:
  A Dependable High Performance Wafer Scale Architecture for Embedded Signal Processing. 125-128
• 
  Lama Nachman, Kewal K. Saluja, Shambhu J. Upadhyaya, Robert Reuse:
  A Novel Approach to Random Pattern Testing of Sequential Circuits. 129-134
• 
  Fong Pong, Michael C. Browne, Gunes Aybay, Andreas Nowatzyk, Michel Dubois:
  Design Verification of the S3.mp Cache-Coherent Shared-Memory System. 135-140

Volume 47, Number 2, February 1998

Computer Arithmetic

• 
  Jean-Michel Muller, Alexandre Scherbyna, Arnaud Tisserand:
  Semi-Logarithmic Number Systems. 145-151
• 
  Elisardo Antelo, Tomás Lang, Javier D. Bruguera:
  Computation of sqrt(x/d) in a Very High Radix Combined Division/Square-Root Unit with Scaling. 152-161
• 
  Christof Paar, Peter Fleischmann, Peter Roelse:
  Efficient Multiplier Architectures for Galois Fields GF(2 ⁴ⁿ). 162-170

Logic (Design and) Synthesis

• 
  Yuke Wang, Carl McCrosky:
  Solving Boolean Equations Using ROSOP Forms. 171-177

Multiprocessor Scheduling

• 
  Emilia Rosti, Evgenia Smirni, Lawrence W. Dowdy, Giuseppe Serazzi, Kenneth C. Sevcik:
  Processor Saving Scheduling Policies for Multiprocessor Systems. 178-189

Theory and Algorithms

• 
  Shih-Yi Yuan, Sy-Yen Kuo:
  A New Technique for Optimization Problems in Graph Theory. 190-196
• 
  Majid Sarrafzadeh, Wei-Liang Lin, C. K. Wong:
  Floating Steiner Trees. 197-211

Brief Contributions

• 
  Pen-Yuang Chang, Jong-Chuang Tsay:
  An Approach to Designing Modular Extensible Linear Arrays for Regular Algorithms. 212-216
• 
  Winfrid G. Schneeweiss:
  On the Polynomial Form of Boolean Functions: Derivations and Applications. 217-221
• 
  Avi Ziv, Jehoshua Bruck:
  Analysis of Checkpointing Schemes with Task Duplication. 222-227
• 
  Anujan Varma, Quinn Jacobson:
  Destage Algorithms for Disk Arrays with Nonvolatile Caches. 228-235
• 
  Marcelo Lubaszewski, Bernard Courtois:
  A Reliable Fail-Safe System. 236-241
• 
  Gagan Hasteer, Prithviraj Banerjee:
  A Parallel Algorithm for State Assignment of Finite State Machines. 242-246
• 
  Zheng Tang, Okihiko Ishizuka:
  A Learning Multiple-Valued Logic Network: Algebra, Algorithm, and Applications. 247-251
• 
  Ali R. Hurson, Krishna M. Kavi, Joford T. Lim:
  Cyclic Staggered Scheme: A Loop Allocation Policy for DOACROSS Loops. 251-255
• 
  Seongmoon Wang, Sandeep K. Gupta:
  ATPG for Heat Dissipation Minimization During Test Application. 256-262
• 
  Michael Barbehenn:
  A Note on the Complexity of Dijkstra's Algorithm for Graphs with Weighted Vertices. 263
• 
  Ahmed El-Amawy, Priyalal Kulasinghe:
  On the Complexity of Designing Optimal Branch-and-Combine Clock Networks. 264-269

Volume 47, Number 3, March 1998

Computer Arithmetic

• 
  Paul F. Stelling, Charles U. Martel, Vojin G. Oklobdzija, R. Ravi:
  Optimal Circuits for Parallel Multipliers. 273-285

Fault Tolerance, Diagnosis and Testing

• 
  Bernard Mans, Nicola Santoro:
  Optimal Elections in Faulty Loop Networks and Applications. 286-297
• 
  Andrzej Pelc:
  Optimal Diagnosis of Heterogeneous Systems with Random Faults. 298-304
• 
  Jacob Savir:
  Random Pattern Testability of Memory Control Logic. 305-312
• 
  Dimitris Nikolos:
  Optimal Self-Testing Embedded Parity Checkers. 313-321

Load Balancing

• 
  Jie Li, Hisao Kameda:
  Load Balancing Problems for Multiclass Jobs in Distributed/Parallel Computer Systems. 322-332

Brief Contributions

• 
  Yutai Ma:
  A Slimplified Architecture for Modulo (2ⁿ + 1) Multiplication. 333-337
• 
  Brian Chess, Tracy Larrabee:
  Logic Testing of Bridging Faults in CMOS Integrated Circuits. 338-345
• 
  Raghu Sastry, N. Ranganathan:
  A VLSI Architecture for Approximate Tree Matching. 346-352
• 
  Çetin Kaya Koç, Berk Sunar:
  Low-Complexity Bit-Parallel Canonical and Normal Basis Multipliers for a Class of Finite Fields. 353-356
• 
  Simone Bettola, Vincenzo Piuri:
  High Performance Fault-Tolerant Digital Neural Networks. 357-363
• 
  Weiming Guo, A. Yavuz Oruç:
  Regular Sparse Crossbar Concentrators. 363-368

Volume 47, Number 4, April 1998

Special Section - Papers from the 17th IEEE International Conference of Distributed Computing

• 
  Partho Pratim Mishra, Mani B. Srivastava:
  Effect of Connection Rerouting on Application Performance in Mobile Networks. 371-390
• 
  Aniruddha S. Gokhale, Douglas C. Schmidt:
  Measuring and Optimizing CORBA Latency and Scalability Over High-Speed Networks. 391-413
• 
  Kritchalach Thitikamol, Peter J. Keleher:
  Per-Node Multithreading and Remote Latency. 414-426
• 
  Markos Zaharioudakis, Michael J. Carey:
  Hierarchical, Adaptive Cache Consistency in a Page Server OODBMS. 427-444
• 
  Pei Cao, Chengjie Liu:
  Maintaining Strong Cache Consistency in the World Wide Web. 445-457
• 
  Robert E. Strom, Guruduth Banavar, Kevan Miller, Atul Prakash, Michael Ward:
  Concurrency Control and View Notification Algorithms for Collaborative Replicated Objects. 458-471

Brief Contributions

• 
  Cesare Alippi, Luciano Briozzo:
  Accuracy vs. Precision in Digital VLSI Architectures for Signal Processing. 472-477
• 
  Sheng Uei Guan, Hsiao-Yeh Yu, Jen-Shun Yang:
  A Prioritized Petri Net Model and Its Application in Distributed Multimedia Systems. 477-481
• 
  Francis Chung-Ming Lau, W. C. Poon:
  Throughput Analysis of B-Networks. 482-485
• 
  Jacob Savir:
  Salvaging Test Windows in BIST Diagnostics. 486-491
• 
  Ching-Nung Yang, Chi-Sung Laih:
  DC_m Codes for Constructing t-EC/AUED Codes. 492

Volume 47, Number 5, May 1998

Cache Memory

• 
  Wei-Chung Hsu, James E. Smith:
  A Performance Study of Instruction Cache Prefetching Methods. 497-508
• 
  John Tse, Alan Jay Smith:
  CPU Cache Prefetching: Timing Evaluation of Hardware Implementations. 509-526
• 
  Guohua Jin, Zhiyuan Li, Fujie Chen:
  An Efficient Solution to the Cache Thrashing Problem Caused by True Data Sharing. 527-543

Coding Theory

• 
  Luca G. Tallini, Bella Bose:
  Theory and Design of Adjacent Asymmetric Error Masking Codes. 544-555
• 
  Luca G. Tallini, Bella Bose:
  Design of Balanced and Constant Weight Codes for VLSI Systems. 556-572

Communication Protocols

• 
  Matti A. Hiltunen, Richard D. Schlichting:
  A Configurable Membership Service. 573-586

CORDIC Algorithms

• 
  Dhananjay S. Phatak:
  Double Step Branching CORDIC: A New Algorithm for Fast Sine and Cosine Generation. 587-602

Fault Tolerance

• 
  Tein-Hsiang Lin, Kang G. Shin:
  Damage Assessment for Optimal Rollback Recovery. 603-613

Performance Evaluation

• 
  Eskil Dekker:
  Architecture Scalability of Parallel Vector Computers with a Shared Memory. 614-624

Volume 47, Number 6, June 1998

Compiler Techniques

• 
  Josep Llosa, Mateo Valero, Eduard Ayguadé, Antonio González:
  Modulo Scheduling with Reduced Register Pressure. 625-638

Fault Tolerance

• 
  G. Robert Redinbo:
  Generalized Algorithm-Based Fault Tolerance: Error Correction via Kalman Estimation. 639-655
• 
  Nitin H. Vaidya:
  A Case for Two-Level Recovery Schemes. 656-666

Modeling and Performance Evaluation

• 
  Gregory R. Ganger, Yale N. Patt:
  Using System-Level Models to Evaluate I/O Subsystem Designs. 667-678

Networks

• 
  Yuguang Fang, Imrich Chlamtac, Yi-Bing Lin:
  Channel Occupancy Times and Handoff Rate for Mobile Computing and PCS Networks. 679-692
• 
  Mikhail J. Atallah, Douglas Comer:
  Algorithms for Variable Length Subnet Address Assignment. 693-699

Real-Time Systems

• 
  Chang-Gun Lee, Joosun Hahn, Yang-Min Seo, Sang Lyul Min, Rhan Ha, Seongsoo Hong, Chang Yun Park, Minsuk Lee, Chong-Sang Kim:
  Analysis of Cache-Related Preemption Delay in Fixed-Priority Preemtive Scheduling. 700-713

Brief Contributions

• 
  Thomas M. Conte, Mary Ann Hirsch, Wen-mei W. Hwu:
  Combining Trace Sampling with Single Pass Methods for Efficient Cache Simulation. 714-720

Volume 47, Number 7, July 1998

Special Section-Papers from the 13th IEEE Symposium on Computer Arithmetic

• 
  Mircea R. Stan, Alexandre F. Tenca, Milos D. Ercegovac:
  Long and Fast Up/Down Counters. 722-735
• 
  Tomás Lang, Elisardo Antelo:
  CORDIC Vectoring with Arbitrary Target Value. 736-749
• 
  Walter Krämer:
  A Priori Worst Case Error Bounds for Floating-Point Computations. 750-756
• 
  Colin D. Walter:
  Exponentiation Using Division Chains. 757-765
• 
  Jean-Claude Bajard, Laurent-Stéphane Didier, Peter Kornerup:
  An RNS Montgomery Modular Multiplication Algorithm. 766-776
• 
  Mark G. Arnold, Thomas A. Bailey, John R. Cowles, Mark D. Winkel:
  Arithmetic Co-Transformations in the Real and Complex Logarithmic Number Systems. 777-786

Regular Papers

• 
  Takeshi Ikenaga, Takeshi Ogura:
  CAM²: A Highly-Parallel Two-Dimensional Cellular Architecture. 788-801
• 
  Venkatesh Akella, Nitin H. Vaidya, G. Robert Redinbo:
  Asynchronous Comparison-Based Decoders for Delay-Insensitive Codes. 802-811

Brief Contributions

• 
  Sanjoy K. Baruah, Shun-Shii Lin:
  Pfair Scheduling of Generalized Pinwheel Task Systems. 812-816

Volume 47, Number 8, August 1998

Testing Algorithms, Methods and Tools

• 
  Santanu Chattopadhyay, Dipanwita Roy Chowdhury, Subarna Bhattacharjee, Parimal Pal Chaudhuri:
  Cellular-Automata-Array-Based Diagnosis of Board Level Faults. 817-828
• 
  Soumitra Bose, Prathima Agrawal, Vishwani D. Agrawal:
  Deriving Logic Systems for Path Delay Test Generation. 829-846

Neurocomputer Architecture

• 
  Howard C. Card, G. K. Rosendahl, Dean K. McNeill, Robert D. McLeod:
  Competitive Learning Algorithms and Neurocomputer Architecture. 847-858

Petri Nets

• 
  Jordi Cortadella, Michael Kishinevsky, Luciano Lavagno, Alexandre Yakovlev:
  Deriving Petri Nets for Finite Transition Systems. 859-882

Brief Contributions

• 
  Huapeng Wu, M. Anwarul Hasan:
  Low Complexity Bit-Parallel Multipliers for a Class of Finite Fields. 883-887
• 
  Jie Wu, Guanghui Guo:
  Fault Tolerance Measures for m-Ary n-Dimensional Hypercubes Based on Forbidden Faulty Sets. 888-893
• 
  Riccardo Rovatti, Michele Borgatti, Roberto Guerrieri:
  A Geometric Approach to Maximum-Speed n-Dimensional Continuous Linear Interpolation in Rectangular Grids. 894-899
• 
  Yuanyuan Yang:
  A Class of Interconnection Networks for Multicasting. 899-906
• 
  Shlomo Reches, Shlomo Weiss:
  Implementation and Analysis of Path History in Dynamic Branch Prediction Schemes. 907-912

Volume 47, Number 9, September 1998

Computer Arithmetic

• 
  J Strother Moore, Thomas W. Lynch, Matt Kaufmann:
  A Mechanically Checked Proof of the AMD5_K86^TM Floating Point Division Program. 913-926
• 
  Romesh M. Jessani, Michael Putrino:
  Comparison of Single- and Dual-Pass Multiply-Add Fused Floating-Point Units. 927-936
• 
  Germain Drolet:
  A New Representation of Elements of Finite Fields GF(2^m) Yielding Small Complexity Arithmetic Circuits. 938-946
• 
  Alejandro F. González, Pinaki Mazumder:
  Multiple-Valued Signed-Digit Adder Using Negative Differential-Resistance Devices. 947-959
• 
  M. Anwarul Hasan:
  Double-Basis Multiplicative Inversion Over GF(2^m). 960-970

Logic Design

• 
  Zeljko Zilic, Zvonko G. Vranesic:
  Using Decision Diagrams to Design ULMs for FPGAs. 970-982

Networks

• 
  Tsern-Huei Lee, Jin-Jye Chou:
  Some Topological Properties of Bitonic Sorters. 983-997
• 
  Gregory Gravenstreter, Rami G. Melhem:
  Realizing Common Communication Patterns in Partitioned Optical Passive Stars (POPS) Networks. 998-1013

Brief Contributions

• 
  Luis A. Montalvo, Keshab K. Parhi, Alain Guyot:
  New Svoboda-Tung Division. 1014-1020
• 
  Chin-Long Wey, Ming-Der Shieh:
  Design of a High-Speed Square Generator. 1021-1026
• 
  Sanjoy K. Baruah, Mary Ellen Hickey:
  Competitive On-Line Scheduling of Imprecise Computations. 1027-1032
• 
  Jagan Agrawal, Yixin Zhang:
  A Fast and Low Cost Self-Routing Permutation Network. 1033-1036

Comments

• 
  Dhananjay S. Phatak:
  Comments on Duprat and Muller's Branching CORDIC Paper. 1037-1040

Volume 47, Number 10, October 1998

Cache Coherence

• 
  Fredrik Dahlgren, Michel Dubois, Per Stenström:
  Performance Evaluation and Cost Analysis of Cache Protocol Extensions for Shared-Memory Multiprocessors. 1041-1055
• 
  Steven K. Reinhardt, Robert W. Pfile, David A. Wood:
  Hardware Support for Flexible Distributed Shared Memory. 1056-1072

Communication

• 
  Thomas E. Truman, Trevor Pering, Roger Doering, Robert W. Brodersen:
  The InfoPad Multimedia Terminal: A Portable Device for Wireless Information Access. 1073-1087
• 
  Jennifer Rexford, John Hall, Kang G. Shin:
  A Router Architecture for Real-Time Communication in Multicomputer Networks. 1088-1101

Fault Tolerance, Diagnosis and Testing

• 
  Mihir Pandya, Miroslaw Malek:
  Minimum Achievable Utilization for Fault-Tolerant Processing of Periodic Tasks. 1102-1112
• 
  J. Hamilton Slye, E. N. Elnozahy:
  Support for Software Interrupts in Log-Based Rollback-Recovery. 1113-1123
• 
  Irith Pomeranz, Sudhakar M. Reddy:
  Location of Stuck-At Faults and Bridging Faults Based on Circuit Partitioning. 1124-1135
• 
  Lan Zhao, D. M. H. Walker, Fabrizio Lombardi:
  IDDQ Testing of Bridging Faults in Logic Resources of Reconfigurable Field Programmable Gate Arrays. 1136-1152

Security

• 
  Markus G. Kuhn:
  Cipher Instruction Search Attack on the Bus-Encryption Security Microcontroller DS5002FP. 1153-1157

Brief Contributions

• 
  Ran Libeskind-Hadas:
  A Tight Lower Bound on the Number of Channels Required for Deadlock-Free Wormhole Routing. 1158-1160
• 
  Jyh-Huei Guo, Chin-Liang Wang:
  Systolic Array Implementation o Euclid's Algorithm for Inversion and Division in GF(2^m). 1161-1167

Volume 47, Number 11, November 1998

Built-In Selft-Test

• 
  Krishnendu Chakrabarty, Brian T. Murray, John P. Hayes:
  Optimal Zero-Aliasing Space Compaction of Test Responses. 1171-1187
• 
  Janusz Rajski, Jerzy Tyszer, Nadime Zacharia:
  Test Data Decompression for Multiple Scan Designs with Boundary Scan. 1188-1200

Computer Arithmetic

• 
  Hesham A. Al-Twaijry, Michael J. Flynn:
  Technology Scaling Effects on Multipliers. 1201-1215
• 
  Naofumi Takagi:
  Powering by a Table Look-Up and a Multiplication with Operand Modification. 1216-1222
• 
  Huapeng Wu, M. Anwarul Hasan, Ian F. Blake:
  New Low-Complexity Bit-Parallel Finite Field Multipliers Using Weakly Dual Bases. 1223-1234
• 
  Vincent Lefèvre, Jean-Michel Muller, Arnaud Tisserand:
  Toward Correctly Rounded Transcendentals. 1235-1243
• 
  Rajit Manohar, José A. Tierno:
  Asynchronous Parallel Prefix Computation. 1244-1252

Theory and Algorithms

• 
  Jun Dong Cho, Salil Raje, Majid Sarrafzadeh:
  Fast Approximation Algorithms on Maxcut, k-Coloring, and k-Color Ordering vor VLSI Applications. 1253-1266
• 
  James D. Fix, Richard E. Ladner:
  Sorting by Parallel Insertion on a One-Dimensional Subbus Array. 1267-1281
• 
  Arlindo L. Oliveira, Luca P. Carloni, Tiziano Villa, Alberto L. Sangiovanni-Vincentelli:
  Exact Minimization of Binary Decision Diagrams Using Implicit Techniques. 1282-1296
• 
  Achilleas Papakostas, Ioannis G. Tollis:
  Interactive Orthogonal Graph Drawing. 1297-1309

Brief Contributions

• 
  Tamra Carpenter, Steven Cosares, Joseph L. Ganley, Iraj Saniee:
  A Simple Approximation Algorithm for Two Problems in Circuit Design. 1310-1312

Volume 47, Number 12, 1998

Coding Theory and Application

• 
  Eiji Fujiwara, Tepparit Ritthongpitak, Masato Kitakami:
  Optimal Two-Level Unequal Error Control Codes for Computer Systems. 1313-1325
• 
  Ching-Tien Ho, Jehoshua Bruck, Rakesh Agrawal:
  Partial-Sum Queries in OLAP Data Cubes Using Covering Codes. 1326-1340

Communication Protocols

• 
  Roberto Baldoni:
  A Positive Acknowledgment Protocol for Causal Broadcasting. 1341-1350

Computer Security

• 
  Michael K. Reiter, Stuart G. Stubblebine:
  Resilient Authentication Using Path Independence. 1351-1362

Instruction and Schedule Cache

• 
  Josep Torrellas, Chun Xia, Russell L. Daigle:
  Optimizing the Instruction Cache Performance of the Operating System. 1363-1381
• 
  Sanjeev Banerjia, Sumedh W. Sathaye, Kishore N. Menezes, Thomas M. Conte:
  MPS: Miss-Path Scheduling for Multiple-Issue Processors. 1382-1397

Brief Contributions

• 
  Rolf Drechsler, Bernd Becker, Andrea Jahnke:
  On Variable Ordering and Decomposition Type Choice in OKFDDs. 1398-1403
• 
  Feng Cao, David Hung-Chang Du, Allalaghatta Pavan:
  Topological Embedding into WDM Optical Passive Star Networks with Tunable Transmitters. 1404-1413
• 
  Mahmoud S. Elsaholy, Samir I. Shaheen, Reda H. Seireg:
  A Unified Analytical Expression for Aliasing Error Probability Using Single-Input. 1414-1417
• 
  Duraisamy Sundararajan, M. Omair Ahmad:
  Indexing Mapping Approach of Deriving the PM DFT Algorithms. 1418-1424

Errata

• 
  Jien-Chung Lo:
  Correction to "A Fast Binary Adder with Conditional Carry Generation" IEEE Transaction on Computers 46(2) 248-253 (1997). 1425
• 
  Nicola Nicolici, Bashir M. Al-Hashimi:
  Correction to the Proof of Theorem 2 in "Parallel Signature Analysis Design with Bounds on Aliasing". 1426