Jonathan W. Greene
- 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.Google Scholar
- 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.Google Scholar
- 3 BROADBENT, S.R., AND HAMMERSLEY, J.M.PERcolation processes, i. Proc Cambridge Phil. Soc 53 (1957), 629-641.Google Scholar
- 4 DOOB, J.LStochastic Processes. Wiley, New York, 1953.Google Scholar
- 5 FELLER, W.An lntroductwn to Probability Theory and Its Applications. Vol. 1L 2rid od. Wiley, New York, 1971, pp. 194-198.Google Scholar
- 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.Google Scholar
- 7 FUSSELL, D., AND VARMAN, P.Fault tolerant wafer-scale architectures for VLSI. In Proceedings of the 9th Annual Symposium on Computer Archuecture (Auslm, Tex., Apr. 26-29). IEEE, New York, 1982, pp. 190-198. Google Scholar
- 8 GALLAGER, R.G.Informatwn Theory and Rehable Communicatwn. Wiley, New York, 1968, pp. 126-128. Google Scholar
- 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.Google Scholar
- 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}).Google Scholar
- 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.Google Scholar
- 12 HARRIS, T. A lower bound for the critical probability in a certain percolation process. Proc. Cambrulge Phd Soc. 56 (1960), 13-20.Google Scholar
- 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.Google Scholar
- 14 HSIA, Y., CHANG, G., AND ERWIN, F.Adaptive wafer scale integration. Jpn. Z App. Phys. 19, Supp. 19-1 (1980), 193-202.Google Scholar
- 15 KOREN, I.A reconfigurable and fault tolerant VLSI multiproeessor army. In Proceedings of the 8th Annual Symposlum on Computer Architecture (Minneapolis, Minn., May 12-14). IEEE, New York, 1981, pp. 425-442. Google Scholar
- 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.Google Scholar
- 17 LINCOLN LABORATORY.Semiannual Technical Summaries. Restructurable VLSI Program. Lincoin Laboratory, Lexington, Mass., March 1981, Sept. 1981, March 1982.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 20 MANNING, F. An approach to htghly integrated computer-maintained cellular arrays. IEEE Trans. Comput. C.26, 6 (June 1977), 536-552.Google Scholar
- 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.Google Scholar
- 22 PE~NISl, L.Elements of Complex Variables, 2rid ed. Holt, Ranehart & Winston, New York, 1976, pp, 177-178, 190.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 26 THOMPSON, C.D. A complexity theory for VLSI Ph.D. dissertation, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa., 1980, pp. 41-44. Google Scholar
- 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.Google Scholar
- 28 WIERMAN, J.C,Percolation theory. Ann. Prob. 10, 3 (1982), 509-524.Google Scholar
Index Terms
- Configuration of VLSI Arrays in the Presence of Defects
Recommendations
High-Speed Arithmetic Arrays
High-speed multifunction arithmetic arrays for multiplication, division, square and square-root operations are presented in this paper. These arrays seem attractive due to their versatility and speed. A recently described quotient-bit evaluation ...
A VLSI Modulo m Multiplier
A novel method to compute the exact digits of the modulo m product of integers is proposed, and a modulo m multiply structure is defined. Such a structure can be implemented by means of a few fast VLSI binary multipliers, and a response time of about ...
Reviews
Sekharipuram Subramaniam Ravi
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 and processor arrays due to the high degree of regularity in their structure. The major problem with the approach is that some of the processors (cells) on the wafer may be defective. Thus, the development of techniques that allow a designer to configure arbitrary networks of nonfaulty (active) cells on a wafer has assumed importance. This paper by Greene and Gamal is an important step in that direction. The analytical model used in this paper assumes that each cell fails with a probability p independent of the other cells on the wafer. In order to configure networks around inactive cells, the interconnect between the cells is programmed to avoid the inactive cells. (For details on how the interconnect may be programmed, see [2].) It is assumed that the interconnect does not fail. This assumption is reasonable, since the interconnect requires a much smaller number of fabrication steps compared to that of the cells. When the active cells are connected together through the programmable interconnect, the area of the circuit increases. Further, since it is possible to encounter a string of inactive cells, the length of the interconnect between active cells (and hence also the propagation delay) increases. Thus, the performance measures used to characterize an interconnection algorithm are the Area Overhead Ratio (denoted by AOR; this is the ratio of the circuit to the number of cells in the circuit) and the maximum connection length ( d). The results presented in this paper provide tight bounds for AOR and d for various interconnection problems. First, the problem of interconnecting RN external pins (where R<1? p) to distinct active cells of an N element linear array is shown to require d=&THgr;( log N) and AOR=&THgr;( log N). Next, the problem of interconnecting RN pairs of elements from two N element linear arrays is shown to require only constant d and AOR, despite its close resemblance to the first problem. Finally, the construction of a K× K lattice, where K= :.PC12 :3Wz:H:CR:A:9U N, from an N× N array, is shown to require d=&THgr;( log N) and AOR=&THgr;( log N). The proofs of the last two results use ideas from statistical physics. Some of the results presented in this paper have been obtained independently by Leighton and Leiserson [2]. This reviewer recommends both of these papers to the interested reader.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments