Configuration of VLSI Arrays in the Presence of Defects

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Configuration of VLSI Arrays in the Presence of Defects

Full text

Pdf (1.20 MB)

Source

Journal of the ACM (JACM) archive
Volume 31 , Issue 4 (October 1984) table of contents

Pages: 694 - 717

Year of Publication: 1984

ISSN:0004-5411

Authors

Jonathan W. Greene	Information Systems Laboratory, Stanford University, Stanford, CA
Abbas El Gamal	Information Systems Laboratory, Stanford University, Stanford, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 32, Citation Count: 19

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1634.2377 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AUBUSSON, K., AND CA'l'r, I.Water-scale mtegratton--A tault tolerant procedure, ll~l~l~J ~'oilcl- State Circmts SC-13, 3 (June 1978), pp. 339-344.
	2	BILARDI, G., PRACCHt, M., AND }:~EPARATA, F.A critique and appraisal of VLSI models of computation. In VLSI Systems and Computation, H.T. Kung, B. Sproull, and G. Steele, Eds. Computer Science Press, Rockville, Md., 198 l, pp. 81-88.
	3	BROADBENT, S.R., AND HAMMERSLEY, J.M.PERcolation processes, i. Proc Cambridge Phil. Soc 53 (1957), 629-641.
	4	DOOB, J.LStochastic Processes. Wiley, New York, 1953.
	5	FELLER, W.An lntroductwn to Probability Theory and Its Applications. Vol. 1L 2rid od. Wiley, New York, 1971, pp. 194-198.
	6	Fmscs, H., HAMMERSLEY, J.M., AND WELSH, D. Monte Carlo estimates of percolation probabil. ities for various lattices. PhFs. Rev. 126, 3 (May 1, 1962), 949-951.
	7	Donald Fussell , Peter Varman, Fault-tolerant wafer-scale architectures for VLSI, Proceedings of the 9th annual symposium on Computer Architecture, p.190-198, April 26-29, 1982, Austin, Texas, United States
	8	Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
	9	GREENE, J. W.Configuration of VLSI arrays m the presence of defects. Ph.D. dissertation, Dept. of Electrical Engineering Stanford Univ., Stanford, Calif., 1983.
	10	GREENE, J.W., AND EL GAMAL, AC.onfiguration of VLSI arrays in the presence of defects,.-Part II. Submitted for publication. (See also I9}).
	11	HAMMERSLEY, J.M. Bomes suprdeures de ia probabilit6 critique dam un processus de filtration. In Le Calcul des Probabditbs et ses Applications. Centre National de la Recherche Scientifique, Paris, France, 1959, pp. 17-37.
	12	HARRIS, T. A lower bound for the critical probability in a certain percolation process. Proc. Cambrulge Phd Soc. 56 (1960), 13-20.
	13	HEDLUND, K., AND SNYDER, L.Wafer scale integration of configurable, highly parallel (CHIP), processors (extended abstracl). In Proceedings of the lmernational Conference on Parallel Processing (Bell,aim, Mich., Aug. 24-27). IEEE, New York, 1982, pp. 262-264.
	14	HSIA, Y., CHANG, G., AND ERWIN, F.Adaptive wafer scale integration. Jpn. Z App. Phys. 19, Supp. 19-1 (1980), 193-202.
	15	Israel Koren, A reconfigurable and fault-tolerant VLSI multiprocessor array, Proceedings of the 8th annual symposium on Computer Architecture, p.425-442, May 12-14, 1981, Minneapolis, Minnesota, United States
	16	LEIGHTON, F.T., AND LEISERSON, C.E.Wafer scale integration of systolic arrays (extended abstract). In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (Chicago, I11., Nov. 3-5). IEEE. New York, 1982, pp. 297-311.
	17	LINCOLN LABORATORY.Semiannual Technical Summaries. Restructurable VLSI Program. Lincoin Laboratory, Lexington, Mass., March 1981, Sept. 1981, March 1982.
	18	LOWRY, M., AND MILLER, A.Analysis of low-level computer vision algorithms for implementation on a VLSI processor array. In Proceedings of the SPIE International SocieO, of Optical Engineers (Robotws and industrial Inspection Conference) (San Diego, Calif., August 24-27), Vol. 360, 1982, pp. 143-150.
	19	MANGIR, T., AND AVIZIENIS, A.Fault tolerant design for VLSI: Effect of interconnect requirements on yield improvement of VLSI designs. IEEE Trans Comput C-31, 7 (July 1982), 609-.616.
	20	MANNING, F. An approach to htghly integrated computer-maintained cellular arrays. IEEE Trans. Comput. C.26, 6 (June 1977), 536-552.
	21	MtNATO, 0., MASUHAS.A, T., SASAm, T., S^KAI, Y., At~D YosmzAm, K. HI-CMOS II 4K static RAM. Digest of Technical Papers, IEEE Sohd State Circuits Conference. IEEE, New York, 1981, pp. 14-15.
	22	PE~NISl, L.Elements of Complex Variables, 2rid ed. Holt, Ranehart & Winston, New York, 1976, pp, 177-178, 190.
	23	RAFFEL, J. On the use of nonvolatile programmable hnks for restrueturable VLSI. In Proceedings of the Cahech Conference on Very Large Scale Integration (Pasadena, Calif., Jan. 22-24). Caitech, Pasadena, Calif., 1979, pp. 95-104.
	24	ROSENBERG, A.The Diogenes approach to testable fault-tolerant networks of processors. Rep. CS- 1982-6.1, Compuler Science Dept., Duke Univ., Durham, N.C., May 1982.
	25	SM,TH, R.T., CHL{PALA, J., BINDELS, J., NELSON, R., F}SCtmR, F., AND MANTZ, T. Laser programmable redundancy and yield improvemem in a 64K DRAM. IEEE J. Sohd-State Circuits SC-16, 5 (Oct. 1981), 506-513.
	26	Clark David Thompson, A complexity theory for vlsi, 1980
	27	WANG, D-L., AND WANG, P.Extremal configurations on a discrete toms and a generalization of the generalized Macaulay theorem. SIAM ~ AppL Math. 33, 1 (1977), 55-59.
	28	WIERMAN, J.C,Percolation theory. Ann. Prob. 10, 3 (1982), 509-524.

CITED BY 19

	Vwani P. Roychowdhury , Jehoshua Bruck, On finding non-intersecting paths in grids and its application in reconfiguring VLSI/WSI arrays, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.454-464, January 22-24, 1990, San Francisco, California, United States
	J. Hastad , T. Leighton , M. Newman, Reconfiguring a hypercube in the presence of faults, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.274-284, January 1987, New York, New York, United States
	Richard Cole , Bruce Maggs , Ramesh Sitaraman, Multi-scale self-simulation: a technique for reconfiguring arrays with faults, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.561-572, May 16-18, 1993, San Diego, California, United States
	John Lach , William H. Mangione-Smith , Miodrag Potkonjak, Efficiently supporting fault-tolerance in FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.105-115, February 22-25, 1998, Monterey, California, United States
	Lenwood S. Heath , Arnold L. Rosenberg , Bruce T. Smith, The physical mapping problem for parallel architectures, Journal of the ACM (JACM), v.35 n.3, p.603-634, July 1988
	E. H. -M. Sha , K. Steiglitz, Reconfigurability and Reliability of Systolic/Wavefront Arrays, IEEE Transactions on Computers, v.42 n.7, p.854-862, July 1993
	Geng Lin, Fault tolerant planar communication networks, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.133-139, May 04-06, 1992, Victoria, British Columbia, Canada
	Wu Jigang , Thambipillai Srikanthan, An improved reconfiguration algorithm for degradable VLSI/WSI arrays, Journal of Systems Architecture: the EUROMICRO Journal, v.49 n.1-2, p.23-31, July 2003
	V. P. Roychowdhury , Jehoshua Bruck , Thomas Kailath, Efficient Algorithms for Reconfiguration in VLSI/WSI Arrays, IEEE Transactions on Computers, v.39 n.4, p.480-489, April 1990
	Prithviraj Banerjee, The Cubical Ring Connected Cycles: A Fault Tolerant Parallel Computation Network, IEEE Transactions on Computers, v.37 n.5, p.632-636, May 1988
	S.-Y. Kung , S.-N. Jean , C.-W. Chang, Fault-Tolerant Array Processors Using Single-Track Switches, IEEE Transactions on Computers, v.38 n.4, p.501-514, April 1989
	A. D. Singh, Interstitial Redundancy: An Area Efficient Fault Tolerance Scheme for Large Area VLSI Processor Arrays, IEEE Transactions on Computers, v.37 n.11, p.1398-1410, November 1988
	Weiping Shi , Ming-Feng Chang , W. Kent Fuchs, Harvest Rate of Reconfigurable Pipelines, IEEE Transactions on Computers, v.45 n.10, p.1200-1203, October 1996
	Tadayoshi Horita , Itsuo Takanami, Fault-Tolerant Processor Arrays Based on the 1$\frac{1}{2}$-Track Switches with Flexible Spare Distributions, IEEE Transactions on Computers, v.49 n.6, p.542-552, June 2000
	Nobuo Tsuda, Fault-Tolerant Processor Arrays Using Additional Bypass Linking Allocated by Graph-Node Coloring, IEEE Transactions on Computers, v.49 n.5, p.431-442, May 2000
	A. A. Bertossi , M. A. Bonuccelli, A Gracefully Degradable VLSI System for Linear Programming, IEEE Transactions on Computers, v.38 n.6, p.853-861, June 1989
	Bruno Codenotti , Roberto Tamassia, A Network Flow Approach to the Reconfiguration of VLSI Arrays, IEEE Transactions on Computers, v.40 n.1, p.118-121, January 1991
	Jason A. Cheatham , John M. Emmert , Stan Baumgart, A survey of fault tolerant methodologies for FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.2, p.501-533, April 2006
	Wu Jigang , Thambipillai Srikanthan , Xiaodong Wang, Integrated Row and Column Rerouting for Reconfiguration of VLSI Arrays with Four-Port Switches, IEEE Transactions on Computers, v.56 n.10, p.1387-1400, October 2007

INDEX TERMS

Classification:
B. Hardware
B.7 INTEGRATED CIRCUITS
B.7.1 Types and Design Styles
Subjects: VLSI (very large scale integration)
B.7.3 Reliability and Testing**
Subjects: Redundant design**

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Routing and layout

General Terms:
Algorithms, Measurement, Reliability, Theory, Verification

REVIEW

"Sekharipuram Subramaniam Ravi : Reviewer"

Recent developments in VLSI technology have made it possible to realize entire digital systems on a single wafer. Such a realization is referred to as wafer scale integration [1]. This approach is particularly suitable for memories an more...

Collaborative Colleagues:

Jonathan W. Greene: colleagues

Abbas El Gamal: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player