IEEE Transactions on Computers, Volume 45

Volume 45, Number 1, January 1996

Cellular Automata

• 
  S. Nandi, Parimal Pal Chaudhuri:
  Analysis of Periodic and Intermediate Boundary 90/150 Cellular Automata. 1-12

Error Correction and Detection

• 
  Rajendra S. Katti:
  A New Residue Arithmetic Error Correction Scheme. 13-19

Logic Design

• 
  Irith Pomeranz, Sudhakar M. Reddy:
  On Removing Redundancies from Synchronous Sequential Circuits with Synchronizing Sequences. 20-32
• 
  Chien-Chung Tsai, Malgorzata Marek-Sadowska:
  Generalized Reed-Muller Forms as a Tool to Detect Symmetries. 33-40

Privacy and Security

• 
  Jovan Dj. Golic:
  Linear Models for Keystream Generators. 41-49

Testing and Design for Testability

• 
  Irith Pomeranz, Sudhakar M. Reddy:
  On the Number of Tests to Detect All Path Delay Faults in Combinational Logic Circuits. 50-62
• 
  Sandeep K. Gupta, Dhiraj K. Pradhan:
  Utilization of On-Line (Concurrent) Checkers During Built-In-Self-Test and Vice Versa. 63-73
• 
  Dimitrios Kagaris, Spyros Tragoudas:
  Retiming-Based Partial Scan. 75-87
• 
  Oliver Chiu-sing Choy, Lap-kong Chan, Ray Chan, Cheong-fat Chan:
  Test Generation with Dynamic Probe Points in High Observability Testing Environment. 88-96

Brief Contributions

• 
  Qing Hu, Xiaojun Shen, Weifa Liang:
  Optimally Routing LC Permutations on k-Extra-Stage Cube-Type Networks. 97-103
• 
  Chi-Sung Laih, Ching-Nung Yang:
  On the Analysis and Design of Group Theoretical T-syEC/AUED Codes. 103-108
• 
  Michael D. Smith, Pinaki Mazumder:
  Generation of Minimal Vertex Covers for Row/Column Allocation in Self-Repairable Arrays. 109-115
• 
  Suresh Rai, Weian Deng:
  Hyperneural Network-An Efficient Model for Test Generation in Digital Circuits. 115-121

Volume 45, Number 2, February 1996

Fault Tolerance

• 
  Alex Orailoglu, Ramesh Karri:
  Automatic Synthesis of Self-Recovering VLSI Systems. 131-142
• 
  Ge-Ming Chiu, Shui-Pao Wu:
  A Fault-Tolerant Routing Strategy in Hypercube Multicomputers. 143-155

Interconnection Network Topology

• 
  Jaroslav Opatrny, Dominique Sotteau, N. Srinivasan, Krishnaiyan Thulasiraman:
  DCC Linear Congruential Graphs: A New Class of Interconnection Networks. 156-164

Routing and Broadcasting Algorithms

• 
  Yossi Azar, Joseph Naor, Raphael Rom:
  Routing Strategies for Fast Networks. 165-173
• 
  Paraskevi Fragopoulou, Selim G. Akl:
  Edge-Disjoint Spanning Trees on the Star Network with Applications to Fault Tolerance. 174-185

Theory and Algorithms

• 
  Saïd Bettayeb, Bin Cong, Mike Girou, Ivan Hal Sudborough:
  Embedding Star Networks into Hypercubes. 186-194
• 
  B. John Oommen, Edward V. de St. Croix:
  Graph Partitioning Using Learning Automata. 195-208
• 
  Jun Gu, Qian-Ping Gu, Ding-Zhu Du:
  Convergence Properties of Optimization Algorithms for the SAT Problem. 209-219
• 
  Shahid H. Bokhari:
  Multiphase Complete Exchange: A Theoretical Analysis. 220-229

Brief Contributions

• 
  Shahram Latifi, Pradip K. Srimani:
  Transposition Networks as a Class of Fault-Tolerant Robust Networks. 230-238
• 
  Amber Roy-Chowdhury, Prithviraj Banerjee:
  A New Error Analysis Based Method for Tolerance Computation for Algorithm-Based Checks. 238-243
• 
  Rajendra S. Katti:
  A Note on SEC/AUED Codes. 244-246
• 
  Yung-Te Lai, Massoud Pedram, Sarma B. K. Vrudhula:
  Formal Verification Using Edge-Valued Binary Decision Diagrams. 247-255

Volume 45, Number 3, March 1996

Built-In Self-Test

• 
  Chih-Ang Chen, Sandeep K. Gupta:
  BIST Test Pattern Generators for Two-Pattern Testing-Theory and Design Algorithms. 257-269
• 
  Kazuhiko Iwasaki, Shigeo Nakamura:
  Aliasing Error for a Mask ROM Built-In Self-Test. 270-277

Compiler Techniques

• 
  Meng-chou Chang, Feipei Lai:
  Efficient Exploitation of Instruction-Level Parallelism for Superscalar Processors by the Conjugate Register File Scheme. 278-293

Subject Area

• 
  Vojin G. Oklobdzija, David Villeger, Simon S. Liu:
  A Method for Speed Optimized Partial Product Reduction and Generation of Fast Parallel Multipliers Using an Algorithmic Approach. 294-306
• 
  Herbert Dawid, Heinrich Meyr:
  The Differential CORDIC Algorithm: Constant Scale Factor Redundant Implementation without Correcting Iterations. 307-318
• 
  Sebastian T. J. Fenn, Mohammed Benaissa, David Taylor:
  GF(2^m) Multiplication and Division Over the Dual Basis. 319-327
• 
  Vitit Kantabutra:
  On Hardware for Computing Exponential and Trigonometric Functions. 328-339
• 
  Alessandro De Gloria, Mauro Olivieri:
  Statistical Carry Lookahead Adders. 340-347
• 
  Luigi Dadda, Vincenzo Piuri:
  Pipelined Adders. 348-356

Memory Management

• 
  J. Morris Chang, Edward F. Gehringer:
  A High-Performance Memory Allocator for Object-Oriented Systems. 357-366

Brief Contributions

• 
  Arif Merchant, Philip S. Yu:
  Analytic Modeling of Clustered RAID with Mapping Based on Nearly Random Permutation. 367-373
• 
  Chao-Ju Hou, Kang G. Shin:
  Determination of an Optimal Retry Time in Multiple-Module Computing Systems. 374-379
• 
  Sandip Kundu, Egor S. Sogomonyan, Michael Gössel, Steffen Tarnick:
  Self-Checking Comparator with One Periodic Output. 379-380
• 
  Martin Knor:
  A Note on Radially Moore Digraphs. 381-383

Correction to Previous Paper

• 
  Jien-Chung Lo, Suchai Thanawastien, T. R. N. Rao:
  Berger Check Prediction for Array Multipliers and Array Dividers. 383

Volume 45, Number 4, April 1996

Algorithm-Based Fault Tolerance and Result-Checking

• 
  Manuel Blum, Hal Wasserman:
  Reflections on the Pentium Bug. 385-393
• 
  Amber Roy-Chowdhury, Nikolaos Bellas, Prithviraj Banerjee:
  Algorithm-Based Error Detection Schemes for Iterative Solution of Partial Differential Equations. 394-407
• 
  Shantanu Dutt, Fikri T. Assaad:
  Mantissa-Preserving Operations and Robust Algorithm-Based Fault Tolerance for Matrix Computations. 408-424
• 
  Jan-Lung Sung, G. Robert Redinbo:
  Algorithm-Based Fault Tolerant Synthesis for Linear Operations. 425-438

Consensus and Agreement

• 
  Mohammad H. Azadmanesh, Roger M. Kieckhafer:
  New Hybrid Fault Models for Asynchronous Approximate Agreement. 439-449

Concurrent Error Detection

• 
  Jien-Chung Lo, Eiji Fujiwara:
  Probability to Achieve TSC Goal. 450-460
• 
  Stanislaw J. Piestrak:
  Design of Self-Testing Checkers for Borden Codes. 461-469

Brief Contributions

• 
  Spyros Tragoudas:
  Min-Cut Partitioning on Underlying Tree and Graph Structures. 470-474
• 
  Nader Bagherzadeh, Martin Dowd, Nayla Nassif:
  Embedding an Arbitrary Binary Tree into the Star Graph. 475-481
• 
  Jovan Dj. Golic, Slobodan V. Petrovic:
  Correlation Attacks on Clock-Controlled Shift Registers in Keystream Generators. 482-486
• 
  Santanu Chattopadhyay, Samir Roy, Parimal Pal Chaudhuri:
  Synthesis of Highly Testable Fixed-Polarity AND-XOR Canonical Networks-A Genetic Algorithm-Based Approach. 487-490
• 
  Hédi Nabli, Bruno Sericola:
  Performability Analysis: A New Algorithm. 491-494
• 
  Cauligi S. Raghavendra, M. A. Sridhar:
  Global Commutative and Associative Reduction Operations in Faulty SIMD Hypercubes. 495-498
• 
  V. S. S. Nair, Jacob A. Abraham, Prithviraj Banerjee:
  Efficient Techniques for the Analysis of Algorithm-Based Fault Tolerance (ABFT) Schemes. 499-503
• 
  Nitin H. Vaidya:
  Comparison of Duplex and Triplex Memory Reliability. 503-507
• 
  Sihai Xiao, Xiaofa Shih, Guilang Feng, T. R. N. Rao:
  A Generalization of the Single b-Bit Byte Error Correcting and Double Bit Error Detecting Codes for High-Speed Memory Systems. 508-511

Corrections

• 
  Qutaibah M. Malluhi, Magdy A. Bayoumi, T. R. N. Rao:
  Correction to "Efficient Mapping of ANNs on Hypercube Massively Parallel Machines". 511

Volume 45, Number 5, May 1996

Generalized Spectral Analysis

• 
  Michael J. Corinthios:
  A Weighted Z Spectrum, Parallel Algorithm, and Processors for Mathematical Model Estimation. 513-528

Interconnection Networks

• 
  Sanguthevar Rajasekaran:
  Mesh Connected Computers with Fixed and Reconfigurable Buses: Packet Routing and Sorting. 529-539
• 
  Sang-Bang Choi, Arun K. Somani:
  Desgin and Performance Analysis of Load-Distributing Fault-Tolerant Network. 540-551

Memory and Memory Mangement

• 
  Manoj Franklin, Gurindar S. Sohi:
  ARB: A Hardware Mechanism for Dynamic Reordering of Memory References. 552-571

Modeling and Performance Evaluation

• 
  Jong Kim, Kang G. Shin:
  Execution Time Analysis of Communicating Tasks in Distributed Systems. 572-579
• 
  Lizy Kurian John, Yu-cheng Liu:
  Performance Model for a Prioritized Multiple-Bus Multiprocessor System. 580-588

Processor Architecture

• 
  Yooichi Shintani, Toru Shonai, Hiroshi Kurokawa, Kazunori Kuriyama, Akira Yamaoka:
  Hierarchical Execution to Speed Up Pipeline Interlock in Mainframe Computers. 589-599

Brief Contributions

• 
  Prasant Mohapatra, Chansu Yu, Chita R. Das:
  Allocation and Mapping Based Reliability Analysis of Multistage Interconnection Networks. 600-606
• 
  Rajendra S. Katti, Mario Blaum:
  An Improvement on Constructions of t-EC/AUED Codes. 607-608
• 
  Rafic A. Ayoubi, Qutaibah M. Malluhi, Magdy A. Bayoumi:
  The Extended Cube Connected Cycles: An Efficient Interconnection for Massively Parallel Systems. 609-614
• 
  Chor Ping Low, Hon Wai Leong:
  A New Class of Efficient Algorithms for Reconfiguration of Memory Arrays. 614-618
• 
  Antonios Symvonis, Jonathon Tidswell:
  An Empirical Study of Off-Line Permutation Packet Routing on Two-Dimensional Meshes Based on the Multistage Routing Method. 619-625
• 
  Yuke Wang, Carl McCrosky:
  Negation Trees: A Unified Approach to Boolean Function Complementation. 626-630
• 
  Wang-Jiunn Cheng, Wen-Tsuen Chen:
  A New Self-Routing Permutation Network. 630-636

Comments

• 
  Behrooz Parhami:
  Comments on "High-Speed Area-Efficient Multiplier Design Using Multiple-Valued Current-Mode Circuits". 637-638
• 
  Shoji Kawahito, Makoto Ishida, Tasuro Nakamura, Michitaka Kameyama, Tatsuo Higuchi:
  Author's Reply. 639

Volume 45, Number 6, June 1996

Fault Tolerant Communication

• 
  Yuh-Rong Leu, Sy-Yen Kuo:
  A Fault-Tolerant Tree Communication Scheme for Hypercube Systems. 641-650
• 
  Patrick T. Gaughan, Binh Vien Dao, Sudhakar Yalamanchili, David E. Schimmel:
  Distributed Deadlock-Free Routing in Faulty, Pipelined, Direct Interconnection Networks. 651-665
• 
  Chien-Chun Su, Kang G. Shin:
  Adaptive Fault-Tolerant Deadlock-Free Routing in Meshes and Hypercubes. 666-683

Routing Algorithms and Switching Schemes

• 
  Kang G. Shin, Stuart W. Daniel:
  Analysis and Implementation of Hybrid Switching. 684-692
• 
  Emmanouel A. Varvarigos, Dimitri P. Bertsekas:
  A Conflict Sense Routing Protocol and Its Performance for Hypercubes. 693-703
• 
  Sergio A. Felperin, Prabhakar Raghavan, Eli Upfal:
  A Theory of Wormhole Routing in Parallel Computers. 704-713
• 
  Sandeep N. Bhatt, Gianfranco Bilardi, Geppino Pucci, Abhiram G. Ranade, Arnold L. Rosenberg, Eric J. Schwabe:
  On Bufferless Routing of Variable Length Messages in Leveled Networks. 714-729

Task Assignment

• 
  David M. Nicol, Rahul Simha, Donald F. Towsley:
  Static Assignment of Stochastic Tasks Using Majorization. 730-740

Brief Contributions

• 
  Martine D. F. Schlag, F. Joel Ferguson:
  Detection of Multiple Faults in Two-Dimensional ILAs. 741-746
• 
  Anup Kumar, Dharma P. Agrawal:
  Parameters for System Effectiveness Evaluation of Distributed Systems. 746-752
• 
  Adit D. Singh, C. Mani Krishna:
  On the Effect of Defect Clustering on Test Transparency and IC Test Optimization. 753-757
• 
  Mayez A. Al-Mouhamed, Steven S. Seiden:
  Minimization of Memory and Network Contention for Accessing Arbitrary Data Patterns in SIMD Systems. 757-762
• 
  K. Lai, Parag K. Lala:
  Multiple Fault Detection in Fan-Out Free Circuits Using Minimal Single Fault Test Set. 763-765
• 
  Barak A. Pearlmutter:
  Doing the Twist: Diagonal Meshes Are Isomorphic to Twisted Toroidal Meshes. 766-767

Comments

• 
  Carles Padró, Paz Morillo, Miguel Angel Fiol:
  Comments on "Line Digraph Iterations and Connectivity Analysis of de Bruijn and Kautz Graphs". 768

Volume 45, Number 7, July 1996

Cellular Automata

• 
  Supratik Chakraborty, Dipanwita Roy Chowdhury, Parimal Pal Chaudhuri:
  Theory and Application of Nongroup Cellular Automata for Synthesis of Easily Testable Finite State Machines. 769-781
• 
  Kevin Cattell, Jon C. Muzio:
  Analysis of One-Dimensional Linear Hybrid Cellular Automata over GF(q). 782-792

Processor Design

• 
  Arif Merchant, Benjamin Melamed, Eugen Schenfeld, Bhaskar Sengupta:
  Analysis of a Control Mechanism for a Variable Speed Processor. 793-801

Real-Time Scheduling

• 
  Jayanta K. Dey, James F. Kurose, Donald F. Towsley:
  On-Line Scheduling Policies for a Class of IRIS (Increasing Reward with Increasing Service) Real-Time Tasks. 802-813
• 
  Ching-Chih Han, Kwei-Jay Lin, Chao-Ju Hou:
  Distance-Constrained Scheduling and Its Applications to Real-Time Systems. 814-826

Theory and Algorithms

• 
  Weijia Shang, Edin Hodzic, Zhigang Chen:
  On Uniformization of Affine Dependence Algorithms. 827-840
• 
  Thang Nguyen Bui, Byung Ro Moon:
  Genetic Algorithm and Graph Partitioning. 841-855

Brief Contributions

• 
  Christof Paar:
  A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields. 856-861

Comments

• 
  Bin Wei:
  Comments on "A Multiaccess Frame Buffer Architecture". 862

Volume 45, Number 8, August 1996

Fault Tolerance

• 
  Nicholas S. Bowen, Dhiraj K. Pradhan:
  The Effect of Program Behavior on Fault Observability. 868-880
• 
  Charles R. Yount, Daniel P. Siewiorek:
  A Methodology for the Rapid Injection of Transient Hardware Errors. 881-891
• 
  Arun K. Somani, Ofer Peleg:
  On Diagnosability of Large Fault Sets in Regular Topology-Based Computer Systems. 892-903

Testing Algorithms, Methods and Tools

• 
  Amitava Majumdar:
  On Evaluating and Optimizing Weights for Weighted Random Pattern Testing. 904-916
• 
  José Salinas, Yinan N. Shen, Fabrizio Lombardi:
  A Sweeping Line Approach to Interconnect Testing. 917-929
• 
  Jacob Savir:
  Reducing the MISR Size. 930-938
• 
  Sanjay Gupta, Janusz Rajski, Jerzy Tyszer:
  Arithmetic Additive Generators of Pseudo-Exhaustive Test Patterns. 939-949
• 
  Ronald D. Blanton, John P. Hayes:
  Testability of Convergent Tree Circuits. 950-963

Brief Contributions

• 
  Priyalal Kulasinghe, Ahmed El-Amawy:
  Optimal Realization of Sets of Interconnection Functions on Synchronous Multiple Bus Systems. 964-969
• 
  S. Rai, V. P. Kirpalani:
  A Modified TRAM Architecture. 969-974
• 
  D. Todd Smith, Barry W. Johnson, Joseph A. Profeta III:
  System Dependability Evaluation via a Fault List Generation Algorithm. 974-979
• 
  Hari Lalgudi, Ian F. Akyildiz, Sudhakar Yalamanchili:
  Augmented Binary Hypercube: A New Architecture for Processor Management. 980-984
• 
  Sreejit Chakravarty:
  A Study of Theoretical Issues in the Synthesis of Delay Fault Testability Circuits. 985-991

Volume 45, Number 9, September 1996

Complexity Theory

• 
  Beate Bollig, Ingo Wegener:
  Improving the Variable Ordering of OBDDs Is NP-Complete. 993-1002

Encoding and Decoding

• 
  Koppolu Sasidhar, Santanu Chattopadhyay, Parimal Pal Chaudhuri:
  CAA Decoder for Cellular Automata Based Byte Error Correcting Code. 1003-1016
• 
  C. L. Chen, Brian W. Curran:
  Switching Codes for Delta-I Noise Reduction. 1017-1021
• 
  Jien-Chung Lo:
  A Hyper Optimal Encoding Scheme for Self-Checking Circuits. 1022-1030

Logic Design

• 
  Daniel H. Linder, James C. Harden:
  Phased Logic Supporting the Synchronous Design Paradigm with Delay-Insensitive Circuitry. 1031-1044

Brief Contributions

• 
  Ming Zhang, Stamatis Vassiliadis, José G. Delgado-Frias:
  Sigmoid Generators for Neural Computing Using Piecewise Approximations. 1045-1049
• 
  Luigi Ciminiera, Paolo Montuschi:
  Carry-Save Multiplication Schemes without Final Addition. 1050-1055
• 
  Zhen Liu, Ting-Yi Sung:
  Routing and Transmitting Problems in de Bruijn Networks. 1056-1062
• 
  Stamatis Vassiliadis, Sorin Cotofana, Koen Bertels:
  2-1 Additions and Related Arithmetic Operations with Threshold Logic. 1062-1067
• 
  Elisardo Antelo, Javier D. Bruguera, Emilio L. Zapata:
  Unified Mixed Radix 2-4 Redundant CORDIC Processor. 1068-1073
• 
  Charles U. Martel, W. Melody Moh, Teng-Sheng Moh:
  Dynamic Prioritized Conflict Resolution on Multiple Access Broadcast Networks. 1074-1079
• 
  Chung-Len Lee, Meng-Lieh Sheu:
  A Multiple-Sequence Generator Based on Inverted Nonlinear Autonomous Machines. 1079-1083
• 
  Haomin Wu, Marek A. Perkowski, Xiaoqiang Zheng, Nan Zhuang:
  Generalized Partially-Mixed-Polarity Reed-Muller Expansionand Its Fast Computation. 1084-1088

Volume 45, Number 10, October 1996

Computer Architecture

• 
  Chung-Ho Chen, Arun K. Somani:
  Architecture Technique Trade-Offs Using Mean Memory Delay Time. 1089-1100
• 
  Michel Banâtre, Alain Gefflaut, Philippe Joubert, Christine Morin, Peter A. Lee:
  An Architecture for Tolerating Processor Failures in Shared Memory Multiprocessors. 1101-1115
• 
  Shenze Chen, Donald F. Towsley:
  A Performance Evaluation of RAID Architectures. 1116-1130

Diagnosis and Testing

• 
  Sreejit Chakravarty, Paul J. Thadikaran:
  Simulation and Generation of IDDQ Tests for Bridging Faults in Combinational Circuits. 1131-1140
• 
  Michael Nicolaidis:
  Theory of Transparent BIST for RAMs. 1141-1156
• 
  Chao Feng, Laxmi N. Bhuyan, Fabrizio Lombardi:
  Adaptive System-Level Diagnosis for Hypercube Multiprocessors. 1157-1170

Memory and Memory Menagement

• 
  Zeng-ou Wang:
  A Bidirectional Associative Memory Based on Optimal Linear Associative Memory. 1171-1179
• 
  Bruce L. Jacob, Peter M. Chen, Seth R. Silverman, Trevor N. Mudge:
  An Analytical Model for Designing Memory Hierarchies. 1180-1194

Brief Contributions

• 
  Sartaj Sahni:
  Scheduling Master-Slave Multiprocessor Systems. 1195-1199
• 
  Weiping Shi, Ming-Feng Chang, W. Kent Fuchs:
  Harvest Rate of Reconfigurable Pipelines. 1200-1203
• 
  Yi-Chieh Chang, Kang G. Shin:
  Load Sharing in Hypercube-Connected Multicomputers in the Presence of Node Failures. 1203-1211
• 
  Janusz Rajski, Jerzy Tyszer:
  On Linear Dependencies in Subspaces of LFSR-Generated Sequences. 1212-1216

Volume 45, Number 11, November 1996

Fault Tolerance

• 
  Hagbae Kim, Kang G. Shin:
  Design and Analysis of an Optimal Instruction-Retry Policy for TMR Controller Computers. 1217-1225
• 
  Francisco V. Brasileiro, Paul D. Ezhilchelvan, Santosh K. Shrivastava, Neil A. Speirs, Sha Tao:
  Implementing Fail-Silent Nodes for Distributed Systems. 1226-1238
•