ACM Home Page
Please provide us with feedback. Feedback
A Survey of Microcellular Research
Full text PdfPdf (3.57 MB)
Source Journal of the ACM (JACM) archive
Volume 14 ,  Issue 2  (April 1967) table of contents
Pages: 203 - 241  
Year of Publication: 1967
ISSN:0004-5411
Author
Robert C. Minnick  Montana State University, Bozeman, Montana
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 3,   Downloads (12 Months): 29,   Citation Count: 14
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/321386.321387
What is a DOI?

ABSTRACT

This paper is a survey of research on microcellular techniques. Of particular interest are those techniques that are appropriate for realization by modern batch-fabrication processes, since the rapid emergence of reliable and economical batch-fabricated components represents probably the most important current trend in the field of digital circuits. First the manufacturing methods for batch-fabricated components are reviewed, and the advantages to be realized from the application of the principles of cellular logic design are discussed. Also two categorizations of cellular arrays are made in terms of the complexity of each cell (only low-complexity cells are considered) and in terms of the various application areas. After a survey of very early techniques that can be viewed as exemplifying cellular approaches, modern-day cellular arrays are discussed on the basis of whether they are fixed cell-function arrays or variable cell-function arrays. In the fixed cell-function arrays the switching function produced by each cell is fixed; the cell parameters are used only in the modification of the interconnection structure. Several versions of NOR gate arrays, majority gate arrays, adder arrays, and others are reviewed in terms of synthesis techniques and array growth rates. Similarly, the current status of research is summarized in variable cell-function arrays, where not only the interconnection structure but also the function produced by each cell is determined by parameter selection. These arrays include various general function cascades, outpoint arrays, and cobweb arrays, for example. Again, the various cell types that have been considered are pointed out, as well as synthesis procedures and growth rates appropriate for them. Finally, several areas requiring further research effort are summarized. These include the need for more realistic measures of array growth rates, the need for synthesis techniques for multiple-function arrays and programmable arrays, and the need for fault-avoidance algorithms in integrated structures.


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
AMAREL, S., COOKE, G., AND WINDER, R.O. Majority gate networks. Scientific Rep. to AFCRL, No. 793, AD268907 (Aug. 1961).
 
2
---- AND BRZOZOWSKI, J. A. Theoretical considerations on reliability properties of recursive triangular switching networks. In Redundancy Techniques for Computing Systems, Spartan Books, Washington, D. C., 1962.
 
3
----, COOKE, G., AND WINDER, R.O. Majority gate networks. IEEE Trans. EC-13, 1 (Feb. 1964), 4-13.
 
4
----. (Review of two papers {52, 53} by John Holland). IRE Trans. EC-9, 3 (Sept. 1960), 384-385.
 
5
ATRURIN, A.J. A study of several planar iterative switching circuits. S.M. thesis, MIT' Electrical Eng. Dept., 1958.
 
6
BALL, J. R., BOLLINGER, R. C., JEEVES, T. A., McEYNOLDS, R. C., AND SHAFFER, D. H. On the use of the Solomon parallel-processing computer. Proc. AFIPS 1962 Fall Joint Comput. Conf., Vol. 22, pp. 137-146 (Spartan Books, Washington, D. C.).
 
7
BALL, W. W. R. Mathematical Recreations and Essays. Macmillan Paperbacks, The Macmillan Co., New York, 1962, pp. 106-108.
 
8
BLUM, H. A machine for performing visual recognition by use of antenna propagationL concepts. Proc. of the Western Electronic Show and Convention, 1962, Paper 6.4.
 
9
BROOKING, M. E., KING, W. F., III, AND GIUSTI, A. Survey of in-house work on cellular logic. Unpubl. memorandum, AFCRL, 1965.
 
10
BROWN, D.R. A high-speed multi-position electronic switch. S.M. thesis, Course VI, MIT, May 1947.
 
11
--- AND ROCHESTER, N. Rectifier networks for multiposition switching. Proc. IRE 37 (Feb. 1949), 139-147.
 
12
CALDWELL, S.H. Switching Circuits and Logical Design. Wiley, New York, 1958, Chap. 11, pp. 414-452.
 
13
CANADAY, i. H. Two-dimensional iterative logic. MIT Electronic Systems Lab., Rep- ESL-R-210, MIT Project DSB 9891, Contract AF-33(657)-11311, AF Task 4421 (Sept. 1964).
 
14
--. Two-dimensional iterative logic. Proc. AFIPS 1965 Fall Joint Comput. Conf., Vol. 27, Pt. 1, pp. 343-353.
 
15
CEN, T. C. Diode Coincidence and mixing circuits for digital computers. Proc. IRE 38 (1950), 511-514.
 
16
CHV, Y. Matrix logic microelectronic computer. Research Div., Metpar, Inc., Arliugton, Va., June 1962.
 
17
COMFOaT, W.T. Higtly parallel machines. IBM Rep. No. 62-825-496, Oct. 1962.
 
18
----. Highly parallel iaachines. In Proc. 1962 Workshop on Computer Organization, Spartan Books, Washington, D. C., 196, pp. 126-155.
 
19
----. A modified Holland machine. Proc. AFIPS 196B Fall Joint Comput. Conf., Vol. 24, pp. 481-488 (Spartan Books, Washington, D. C.),
 
20
COXETEa, H. S. M., LONGUET-HIGGINS, M. S., AND MILLEtR, J. C, P. Uniform polyhedra. Phil, Trans. Roy. Soc. London {A}, 246 (1954), 401-450.
 
21
CRANE, B. A., AND GITHENS, J.A. Bulk processing in distributed logic memory. IEEE Trans. EC-I4, 2 (April 1965), 186-196.
 
22
----. Economics of the DLM, a batch-fabricatable parallel computer. Proc. Nat. Syrup. on the Impact of Batch Fabrication on Future Computers, IEEE Pub. 16cl, April 1965, pp. 144-149.
 
23
CHAWFOaD, P.O. Automatic control by arithmetic operations. S.M. thesis, MIT, 1942.
 
24
DITIIICK, N. H., MITCHELL, M. M., AND SEKELY, N.E. Integrated direct-coupled unipolar transistor logic element. Final Report, Contract AF 19(628)-428, AFCRL Rep. 63-525, Oct. 1963.
 
25
DOMENICO, R. J., .AND HENLE, R. A. All-purpose computer circuits. Electronics 35 (Aug. 19, 1960), 56-58.
 
26
DUNNING, M., KOLM.AN, B., AND STEINBERG, L. Reliability and fault-masking in nvariable NOI trees. Scientific Rep. 1, Contract AF 19(628)-4051, Project 4641, Task 464104, AFCRL Rep. 65-295, April 1965.
 
27
EAaL, J. Boolean algebra won't give the answer. Electronic Design 12 (Dec. 1964), 33-52.
 
28
EDELSTIN, L. A. Some applications of Backus, picture logic computer. Proc. Nat. Symp. on the Impact of Batch Fabrication on Future Computers, IEEE Pub. 16cl, April 1965, pp. 133-143.
 
29
ELSPAS, B., AND SHORT, R.. A, A bound on the run measure of switching functions. fEEETrans. EC-18, 1 (Feb. 1964), 1-4,
30
 
31
FORRESTER, J. W. Digital information storage in three-dimensions using magnetic cores. J. Appl. Phys. 22 (Jan. 1951), 44-48.
32
 
33
GAINES, R. S., AND LEt:, C.Y. An improved cell memory. IEEE Trans. EC-14 (Feb. 1965), 72-75 (under Short Notes).
 
34
GARNER, H. L., ANn SQuirE, J.S. Iterative circuit computers. Proc. 1962 Workshop on Computer Organization, Spartan Books, Washington, D. C., 1963, pp. 156-181.
 
35
-- ET AL. A study of iterative circuit computers. Teeh. Documentary Rep. No. AL- TDR-64-24, Project 4160, Task 416005, U. of Michigan, April 1964.
 
36
GLUCKSMAN, H.A. A parapropagation pattern classifier. AFCRL Rep, 62-109, March 1962.
 
37
--. Pattern classification by characteristic loci. AFCRL Rep. 63-11, Jan. 1963.
 
38
GONZ.A.LES, R. A multilayer iterative circuit computer. Tech. Note, Contract AF 33(657)-7301, U. of Michigan, Aug. 1962.
 
39
----. A multilayer iterative circuit computer. IEEE Trans. EC-12, 6 (Dec. 1963), 781- 790.
 
40
--. A multilayer iterative circuit computer. ACM 18th Nat. Conf., Aug. 1963, paper 4C.3.
 
41
GRASSELLt, A. Iterative switching networks having completion signals, Alta Frequenza 31, 12 (1962), 832-8;7 (in Italian).
 
42
GnEGORY, J., AND MCINOLDS, ... The Solomon computer. IEEE Trans. EC-12, 6 (Dec. 1963), 774-781.
 
43
GaIswoLn, R .E . A study of iteratlve switching networks. Stanford Electronics Lab. Tech. Rep. No. 098-2, Jan. 1962.
 
44
HAWKINS, J. K., AND MUNSEY, C.J. A two-dimensional iterative network computig technique and mechanizations. P.'oc. 196'2 Wo%hop on Computer Organization, Spartan Books, Washington, D. C., 1963, pp. 93-125.
 
45
---- AND -- . A parallel computer organization and mechanizations. IEEE Trans. EC-12, 3 (June 1963), 251-262.
 
46
HENNIE, F .C . Analysis of one-dimensional iterative logical circuits. S.M. thesis, MIF Electrical Eng. Dept., 1958.
 
47
- ...... . Analysis of bilateral iterative networks. IRE Trans. CT-6, 1 (March 1959), 35-45.
 
48
- --. Two-dimensional iterative networks and their decision problems. General Elec_ tric Res. Lab. Rep., Schenectady, New York, 1960.
 
49
--. Iterative Arrays of Logical Circuits. MIT Press, Cambridge, Mass., and Wiley, New York, 1961.
 
50
HEICZOG, G. Active logic elements using non-galvanic modifying inputs. Scientific Reid . No. 1, Contract AF 19(628)-1629, AFCRL Rep. 63-567, Oct. 1963.
 
51
----., Hu, K. C., AND LEW1N, M.H. Active logic elements using non-galvanic modifying inputs. Final Report, Contract AF 19(628)-1629, AFCRL Rep. 64-896, Oct. 1964.
 
52
HOLLAND, J. A universal computer capable of executing an arbitrary number of sub - programs simultaneously. Proc. AFIPS 1959 Eastern Joint Comput. Conf., Vol. 16, pp. 108-113.
 
53
--. Iterative circuit computers. Proc. AFIPS 1960 Western Joint Comput. Conf., Vol. 17, pp. 259-265.
54
 
55
KEISTER, W., IITCHIE, A. E., AND WASHBURN, S .H . The Design of Switching Circuits. D. Van Nostrand, New York, 1951.
 
56
KILMER, W. L. Transient behavior in iterative combinational switching networks. Proc. Second Annual Symp. on Switching Circuit Theory and Logical Design, AIEE Pub. S134, Sept. 1961.
 
57
----. Iterative switching networks composed of combinational cells. IRE Trans. EC-11, 2 (Aril 1962), 123-131.
 
58
----. On cycling behavior in 1-dimensional bilateral iterative networks. Scientific Rep. 3, AFCRL Contract AF 19(604)-6619, Electronics Res. Lab., Endowment and R e s . Found., Montana State College, Bozeman, Montana, Aug. 1962.
 
59
--. On dynamic switching ill one-dimensional iterative logic networks. Inf. Cortr. 6 (1963), 399-415.
 
60
--. Topics in the theory of one-dimensional iterative networks. Inf. Contr. 7 (1964), 180-199.
 
61
KING, W. F. State-logic relations in an iterative structure for autonomous sequenti1 machine. AFCRL Rep. 65-439, June 1965.
 
62
-- AND GIUSTI, A. Can logic arrays be kept flexible? Electronic Design 13 (May 24, 1965), 57--61.
 
63
LEE, C.Y. An algorithm for path connections and its applications. IRE Trans. EC-1O, 3 (Sept. 1961), 346-365.
 
64
--. Intercommmficating cells, basis for a distributed logic computer. Proc. AFIIS 1962 Fall Joint Comput. Conf., Vol. 22, pp. 130-136 (Spartan Books, Washington, D. C .) -
 
65
AND PAULL, M. C. A content addressable distributed logic memory with applica - tions to information retrieval. Proc. IRE 51,6 (June 1963), 924-932.
 
66
--. Synthesis of a cellular computer using the 29-state model of Von Neumann. Bell Labs. Memo. MM63-344-5, Dec. 1963.
 
67
LEE, E .S . Associative techniques with complementing flip-flops. Proc. AFIPS 1963 Spring Joint Comput. Conf., Vol. 23, pp. 381-394 (Spartan Books, Washington, D. C .).
 
68
LENDARIS, G. G-, AND STANLEY, G.L. On the structure-dependent properties of adptire logic networks. TR 63-219, General Motors Defense Research Labs., Santa Barbara, Calif., July 1963.
 
69
LEVIEN, R .E . The synthesis of cascade switching circuits. Proc. Third Annual AIIF-, Symp. on Switctfing Circuit Theory and Logical Design, Pub. S141, 1962, pp. 104-121.
 
70
----. Determining the best ordering of variables in cascade switching circuits. Proc. of the Fourth Annual AIEE Syrup. on Switching Circuit Theory and Logical DesigL AEE Pub. S156, 1963, pp. 83-104.
 
71
LEVY, S. The reliability of triangular switching networks built of rectifier gates. In Redundancy Techniq'es for Computing System.% Spartau Books, Washington, D. C., 1962.
 
72
--, W1NDaR, R. O., AND MOTr, T, H., JR. A note oi1 tributary switching networks. IEEE Trans. EC-18, 21 (April 1964), 148-151 (Correspondence).
 
73
Low, P. R., O'CONNELL, J. A., AND SKIKO, E .J . Au EL-PC device to implement flowtable logic for variable pattern recognition. Digest of Papers, Solid State Circuit.s Conference, 1961, pp. 34-35.
 
74
-- ANn MALEY, G.A. Flow table logic. Proc. IRE 49, 1 (Jan. 1961), 221-228.
 
75
MACKINTOSH, I. M., AND (}REEN, D. Programmed interconnections--a release from tyranny. Proc. IEEE 52, 12 (Dec. 1964), 1648-1651.
 
76
MAITRA, K.K. Cascaded switching networks of two-input flexible cells. IRE Trans. EC-If, 2 (April 1962), 136-143.
 
77
McCnusKEY, E. J., JR. Iterative combinational switchig circuits--genet'al design considerations. IRE Trans. EC-7, 4 (Dec. 1958), 285-291.
 
78
--. A comparison of sequential and iterative circuits. Trans. AIEE 78, Pt. I, Communication and Electronics, Jan, 1960, pp. 1039-1044.
 
79
----.. Reduction of feedback loops in sequential circuits and carry leads in itertive networks. Princeton U., Digital Systems Lab., Tech. R, ep. 28, Aug. 1962; also Proc. Third Annual AIEE Syrup. on Switching Circuit Theory and Logical Design, Pub. 141, 1962, pp. 91402; also Inf. Contr. 6 (June 1963), 99-118.
 
80
McCoIMmK, B. H. The Illinois pattern recognition computer--ILLIAC IH. iEEE Trans. EC-12, 6 (Dec. 1963), 791-813; also appeared as Rep. No. 148, Digital Computer Lab,, U. of Illinois, Aug. 20, 1963; also presented at ACM 18th Nat. Conf., Denver, Colo., Aug. 27, 1963.
 
81
--., RoY, S. R., SMITH, K. C., AND YAMAOA, S. ILLIAC III: A processor of visual information. U. of Illinois, Dept. of Computer Science, Rep. No. 183, June 1965; also in Proc. IFIP Congress, 1965.
 
82
McKEEwm, B. T. The associative memory structure. Proc. AFIPS 1965 Fall Joint Comput. Conf., Vol. 27, Pt. 1, pp. 371-388.
 
83
MINNICK, R. C. Magnetic comparators and code converters. In Switching Theory in Space Technology, Aiken and Main (Eds.), Stanford U. Press, 1963, pp. 193-204.
 
84
---- nND SHORT, R. A. Cellular linear-input logic. Final Report, SgI Project 4122, Contract AF 19(628)-498, Stanford Research Institute, Menlo Park, Calif., AFCRL 64-6; DDC No. AD 433802, Feb. 1964.
 
85
--. Cutpoint cellular logic. IEEE Trans. EC-13, 6 (Dec. 1964), 685--698.
 
86
--. Application of cellular logic to the design of monolithic digital systems. Proc. Syrup. on Microelectronics and Large Systems, Spartan Books, Washington, D. C., 1965.
 
87
- ET AL. Cellular logic. Final Report, SRI Project 5087, prepared ff)r AFCRL on Contract AF 19(628)-4233; AFCI{L 66-613, April 1966.
 
88
----. Cobweb cellular arrays. Proc. AFIPS 1965 Fall Joint Comput. Conf., Vol. 27, Pt. 1, pp. 327-341.
 
89
MIYATA, F. Realization of arbitrary logical functions using majority elements. IEEE Trans. EC-12, 3 (June 1963), 183-191.
 
90
MULLER, D.E. Complexity in electronic switching circuits. IRE Trans. EC-5, 1 (March 1956), 15-19.
 
91
POAGE, J .F . Memory and cycling ia bilateral iterative networks. Tech. Rep. No. 7, Princeton U. Digital Systems Lab., May 1961.
 
92
Proc. Nat. Syrup. on the Impact of Batch Fabrication on Future Computers, IEEE Pub. 16cl, April 1965.
 
93
RA.CnMAN, J .A . Static magnetic matrix memory and switching circuits. RCA Review 13 (June 1952), 183-201.
 
94
ROCHESTR, N., HOLLAND, J. U., HAIBT, L. H., AND DUDK, W.L. Tests on a cell assembly theory of the action of the brain, using a large digital computer. IRE Trans. IT-2 (Sept. 1956), 80-93.
 
95
ROSIN, IK F. An organization of an associative cryogenic computer. Proc. AFiPS 1962 Spring Joint Comput. Conf., Vol. 21, pp. 203-212.
 
96
SACK, E. A., AND LYMAN, R.C. Evolution of the concept of a computer on a slice. Proc. IEEE 52, 12 (Dee. 1964), 1713-1720.
 
97
SCARLOTT, C.A. Planning for the next stage of electronic miniaturization. Stanford{0 Res. Inst. J . 8, 1 (1964), 14-15.
 
98
SCUDDER, F. J., AND REYNOLDS, J .N . Crossbar dial telephone switching system. Trans. AIEE 58 (May 1939), 179-192.
 
99
SIIORT, R.A. Two-rM1 cellular cascades. Proc. AFIPS 1965 Fall Joint Comput. Conf., Vol. 27, Pt. 1, pp. 355-369.
 
100
SIMMONS, G. J., AND ROOK, L.W. A description of the computer organization imposed by large iterative systems. Proc. Nat. Symp. on the Impact of Batch Fabrication on Future Computers, IEEE Pub. 16el, April 1965, pp. 191-196.
 
101
SKLANSKY, J. General synthesis of tributary switching networks. IEEE Trans. EC-I2, 5 (Oct. 1963), 464-469.
 
102
----, KORENJAK, A. J., AND STONE, H .S . CanonicM tributary networks. IEEE Trans. EC-14, 6 (Dec. 1965), 961-963 (under Short Notes).
 
103
SLOTNICK, D. L., BORCK, W. C., AND McREYNOLDS, R. C. The Solomon computer. Proc. AFIPS 1962 FM1 Joint Comput. Conf., Vol. 22, pp. 97-107.
 
104
, AND ----. The Solomon computer--a preliminary report. Proc. 1962 Workshop on Computer Organization, Spartan Books, Washington, D. C., 1963, pp. 66-92.
 
105
SPANDORFER, L. M., AND MURPHY, J .V . Synthesis of logic functions on an array of integrated circuits. Scientific Rep. No. 1 for UNIVAC Project 4645, AFCRL-63-528, Contract AF 19(628)2907, Sperry Rand Corp., UNIVAC Engineering Center, Bluebell, Pa., Oct. 31, 1963.
 
106
AND .... . Synthesis of logic functions on an array of integrated circuits. Scientific Rep. No. 2 for UNIVAC Project 4645, prepared for AFCRL on Contract AF 19(628)2907, Oct. 31, 1964.
 
107
---- AND TONIK, A.B. Planar Interconnect Logic. Proc. of a Symp. on Microelectronies and Large Systems, Spartan Books, Washington, D. C., 1965.
 
108
----. Synthesis of logic functions on an array of integrated circuits. Final Rep. for UNIVAC Project 4645, prepared for AFCRL on Contract 19(628)2907, Nov. 30, 1965.
 
109
SQUIRE, J. S. Programming and design considerations of highly parallel computer. Proc. AFIPS 1963 Spring Joint Comput. Conf., Vol. 23 (Spartan Books, Washington, D. C.), pp. 395-400.
 
110
Staff of the Harvard Computation Laboratory. Synthesis of Electronic Computing and Control Circuits. Annals 27, Harvard U. Press, Cambridge, Mass., 1951.
 
111
STEWART, R.M. Notes on the structure of logic nets. Proc. IRE ,9, 8 (Aug. 1961), 1322-1323 (Correspondence).
 
112
----. Theory of structurally homogeneous logic nets. Biological Prototypes and Synthetic Systems 1 (1962), 370-380.
 
113
----. Adaptable Cellular Nets. Progress in Biocybernetics 1 (1964), 96-105.
 
114
----. Design for a structurMly-homogeneous peripheral-access functionally-universal electrochemicM machine. Research Menlo. No. 25, Space-General Corp., June 1965.
 
115
STONE, H .S . On the number of equivalence classes of functions realizable by cellular cascades. Proc. Nat. Symp. on the Impact of Batch Fabrication on Future Computers, IEEE Pub. 16cl, April 1965, pp. 81-87.
 
116
-- AND KORENJAK, A .J . Canonical form and synthesis of cellular cascades. IEEE Trans. EC-14, 6 (Dec. 1965), 852-862.
 
117
UBER, E. F., AND DORENICO, A .J . A universal logic function wafer. Lockheed Microsystems Electronics Rep. 6-90-64-8, 1964.
 
118
UNGER, S. II. A computer oriented toward spatial problems. Proc. IRE 6, 10 (Oct. 1958), 1744-1750.
 
119
----. Pattern detection and recognition. Proc. IRE 47, 10 (Oct. 1959), 1737-1752.
 
120
--- Pattern recognition using two-dimensionM, bilateral, iterative, combinational switching circuits. Proc. Symp. on Mathematical Theory of Automata, Microwave Research Institute Symposia Series, Vol. 12, Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn, N. Y., 1963, pp. 577-591.
 
121
URBANO, R. H. On the convergence and ultimate reliability of iterated neural nets. IEEE Trans. EC-IS, 3 (June 1964), 204-225.
 
122
----. Matrix criteria for arbitrary reliability in iterated neural nets. IEEE Trans. EC44, 4 (Aug. 1965), 627-629 (Short Note).
 
123
----. Some new results on he convergence, oscillation, and reliability of polyfunetional ilets. IEEE Trans. EC-I4, 6 (Dec. 1965), 769-781. A preliminary version of this paper appears in Proc. Fifth Annual Syrup. Switching Circuit Theory and Logical Design, IEEE Pub. S-164, Oct. 1964, 138-148.
 
124
WANG, A., AND WOO, W.D. Static magnetic storage and delay line. J. Appl. Phys. 21, 1 (Jan. 1950), 49-54.
 
125
WASHBURN, S. H. Itelay "trees" and symmetric circuits. Trans. AIEE 68, Part I (1949), 582-586.
 
126
YANG, C. C., AND YAU, S .S . A eutpoint cellular associative nlemory. IEEE Trans. EC-15, 4 (Aug. 1966), 522-534.
 
127
YEVREINOV, E. U., AND KOSAREV, Y.G. High efficiency computing system s. Engineering Cybernetics, No. 4 (1963), 1-19.
 
128
YOEL1, M. A group-theoretical approach to two-rail cascades. {EEE Trans. EC-14, 6 (Dec. 1965), 815--822.
 
129
ZSCHIRNT, H.H. Miscellaneous notes on cellular logic structures and their synthesis in eight-neighbor nets. Unpub. Memo., AFCRL, 1966.

CITED BY  14