Computers have been used since the 1950s in various ways to support the design of electronic circuits, but until the mid 1970s their use was not a consequence of physical or intellectual necessity but rather convenience, cost, and efficiency. With the emergence of microprocessors and Very Large Scale Integration (VLSI), in which circuit densities approached and then exceeded a million transistors on a single chip, the design of integrated circuits became so complex that human beings, without the aid of computers, could not accomplish the necessary tasks.

Electronic design automation is the application of computer-based tools to the design of electronic systems, printed circuit boards, semiconductors or integrated circuits. Kuo and Magnuson's classic 1969 text, Computer Oriented Circuit Design, defines computer-aided design more fully as:

The case ends with the successful commercialization in the 1980s of computer-aided design software packages by firms such as Mentor Graphics and Cadence Design Systems, both members of EDAC. It begins in the 1950s and 60s with the application of computers to physical layout problems presented by placement and interconnection of discrete components such as transistors and resistors on printed circuit boards, and the development of mathematical models to simulate the behavior of simple circuits. It is a complex story about a complex technology, involving multiple streams of research and development that eventually converged in the form of complete software design packages that were introduced into the marketplace. It is also a story of varied roles taken by industry and academia, with the lead role shifting over time, and of the continuing role of the two federal agencies that dominated government support for research in computer science during the period: DARPA and the National Science Foundation.
 

II. Defining and Bounding CAD/EC

Problems unique to the CAD/EC case require that we repeat here the primary goal of the overall project: to identify whether and how the National Science Foundation was involved in the evolution of a number of significant engineering innovations. To achieve this goal, in the other five cases we were able to develop a fairly comprehensive, though hardly complete, history of the innovation. Reviews of these cases by major contributors indicated that not only had we gotten the "story right," but we had not omitted any significant contributors or substantially misrepresented their contributions. In the case of CAD/EC, such a comprehensive history proved to be an impossible task given the resources available. What follows is the "story" of CAD/EC, not a detailed technical history. We know there are weaknesses and omissions. Rather than attempt to develop a complete history of the innovation, we used the time available to concentrate on identifying potential and actual NSF involvement in the several streams of CAD/EC development, analyzed against the backdrop of the innovation's evolution. The remainder of this section describes the complexity of the innovation and illustrates the difficulties encountered in any attempt to document its history.

The field of "computer-aided design applied to electronic circuits" has been highly dynamic, driven in part by the exponential increase in the density of components on a chip. This dramatic increase in component density has periodically changed the nature of problems associated with advancement in CAD/EC. In addition, there have been multiple levels of problem-definition and problem-solving (e.g., circuit board, integrated circuit chip, system), as well as multiple facets of those problems. Further, levels of interest have changed over time; industry played the major role in the early development of the field, so that solutions tended to be company-specific and less open than if academic research had defined the state-of-the-art, but as we will see below, this relationship reversed as the problems became more complex. Finally, participants in the several different problems and levels of analysis have not used consistent terms to refer to their activities. One indication of the complexity involved is the variety of definitions of CAD/EC offered in the technical literature.

The NSF program director who introduced a 1977 workshop intended to increase interaction between academic circuit theory researchers and industry said that "Computer aided integrated circuit design requires several basic programs:

• schematic design
• logic simulation
• artwork layout
• artwork verification
• test sequence generation
• data base development." (from 1977 NSF workshop, Schutzman presentation)

• physical placement
• circuit design
• logic design

In 1972 Ralph Preiss of IBM defined "design automation" this way:

Breuer observed that the activities or functions included in CAD/EC have evolved over time because the "least creative" elements in circuit design were automated first. As each stage was successfully automated, attention turned to the next, higher, more complex level of design. However, he also observed that the process is actually more complex than this, because the underlying technology has constantly changed. For example, tasks such as placement and routing that seemed simple at the individual component/printed circuit board level became much more complex for large-scale integrated circuits, and thus needed to be continuously reexamined. Also, as underlying technology changes, the assumptions relevant to initial characteristic are no longer optimal. For example, cellular phones now place a premium on battery-operated, low power characteristics, whereas ten years ago the assumption behind chip design was that the final product would be plugged into the wall (SRI interview, 8/20/97). One could hardly ask for a more succinct description and explanation of the dynamic character of CAD/EC development.

For the purposes of this case, computer-aided physical design began in the 1950s and was soon followed by developments in simulation and testing. The two technologies evolved roughly concurrently. But, as we will see as the case unfolds, testing and simulation initially progressed largely independently of placement and routing (physical design). The science that underlay synthesis predates both physical design and simulation, but the application of that science within a CAD environment did not occur until the 1970s. The historical development of these three streams of research was a function of the inability of unaided human beings to accomplish design tasks in each stream. This threshold was first encountered in physical design, shortly thereafter in simulation and testing, and then a decade later in synthesis. As we will see, the CAD-based solutions to the problems presented by these thresholds did not require that scientific horizons be extended, but instead were largely pragmatic, incremental solutions to problems that drew upon available knowledge.

To sum up, our case will include three primary foci of work on CAD/EC: physical design, testing and simulation, and synthesis. We further limit the case by focusing solely on computer-aided design tools for integrated circuits. We do not detail work on printed-circuit board tools or on higher-order systems tools, i.e., tools that aid in the design of complete computer systems. This decision might be regarded as arbitrary, and we accept that criticism. We had to deal with resource limitations, and have attempted to acknowledge the interplay with closely related technical areas.
 

III. The Evolution of CAD/EC

Background

Unlike most other innovations targeted by this study, such as fiber optics and magnetic resonance imaging, the history of computer aided design applied to electronic circuits cannot be traced to one or more specific breakthroughs in a single stream of technological advance. The evolution of CAD as applied to electronic circuits (CAD/EC) is best characterized as the confluence of multiple streams of continual, incremental improvements, each punctuated by periodic discontinuities that were forced by advances in chip technology. These multiple streams eventually coalesced, over a thirty year period, into a discrete commercial technology. To deal with this complexity, we divided CAD/EC into three major areas: physical design, simulation and testing, and synthesis. The logic for this division was based on the Association of Computing Machinery's (ACM) 25 Years of Design Automation (ACM, 1988).
 

Physical Design

Physical design is the earliest application of CAD in electronic circuit design. Conceptually it covers everything from the placement of circuits (placement), to the wire layout (routing), to the production of the mask used in the etching process. It is somewhat deceptive to call physical design an application area of CAD, for that implies that CAD existed prior to physical design. In reality, physical design and, in particular, wire layout provided the impetus for early CAD work. Some of the first CAD programs were custom wire layout programs developed by IBM to reduce the length of copper wires in the early vacuum tube-based computers in the 1950's. But since these early applications were for board-level systems, not computer chips, they are outside the bounds of this case. Also outside the bounds of the case are innovations such as visual display terminals, the light pen, and Sketchpad (Sutherland, 1964). The contributions of these innovations were substantial; there were target to electronic circuit at the board and pre-board levels. In the early stages of CAD, defense-related requirements drove the research, as was the case in the development of the computer (Mowery, 1996; Katz and Phillips, 1982).

The physical design process became more formalized and focused on circuit level design in the mid to late 1960's with software programs such as PUZZLE (Lawrence Radiation Lab), CAMP (Motorola), MIG (Texas Instruments) and CADIC. Developments in this area were mostly incremental. The technology borrowed heavily from related technologies such as board design and broader fields such as industrial engineering. The PUZZLE program, which calculated optimal wire routes, used Lee's algorithms developed at Bell Labs for solving mazes (Kuo and Magnuson, 1969: 504). CADIC used some of the same algorithms as ACCEL (Sandia), an automated electronic circuit board design tool. The CAMP system from Motorola was one of the first systems to produce the final masks, but it required human support to optimize the layouts (Kuo and Magnuson, 1969: Chapter 13).

Despite advances in physical design technology, as time passed the physical design problem became more complex, requiring, as Breuer described in the preceding section of this case, the solution of an entirely new class of problems. This roadblock to development was due to the exponential rate at which the overall complexity of electronic circuits increased (i.e., circuit density):

• 1959-1965: Small-scale integration (SSI; up to 64 components per integrated circuit)
• 1965-1969: Medium-scale integration (MSI; up to 1000 components per chip)
• 1969-1989: Large-scale integration (LSI; up to one million components per chip)
• 1989-present: Very large-scale integration (VLSI; more than one million components per chip).

Through the 1970s and 1980s, advances in physical design technology continued to flow out of federal labs, defense contractors, civilian industry, and to some extent, academia. It appears that there were no dominant players or significant concentration of expertise (Pederson interview, 5/23/97). As late as 1980, organizations in all these sectors were churning out custom code for applications to run in specific environments. The result was that, despite the large amount of activity and considerable sharing of ideas and results, there was no attempt to standardize code or transfer code across similar applications. Industry did not regarded CAD/EC software as a potential commercial product; they all considered themselves to be in the computer hardware business. Some firms also considered CAD/EC software to be enabling technology and did not wish to sell it to competitors (Hachtel interview; Rhines interview).

The shift from LSI to VLSI appears to have changed this situation. In the late 1970's, physical design code could take over a week of computational time to run the calculations necessary for a high density chip. The desire to reduce computation costs drove efforts to further improve physical design algorithms. Major projects such as the MIT "Greedy Channel Router" project, co-sponsored by GE, DARPA, NSF, and the Air Force, addressed this problem by making advances in computationally inexpensive techniques (Rivest and Fiduccia, 1981). Large efforts such as this MIT program served to centralize and unify development.
 

Simulation and Testing

Interest in circuit simulation and testing began shortly after computers were applied to routing problems. Circuit simulation was first used because of the need for accurate timing delay models for automatic placement and routing. In this way, place and route and circuit simulation are related but separate developments (Hachtel interview, 9/17/97). The bulk of the early work (1950's and early 1960's) centered on basic modeling of discrete electronic components (i.e., transistors); that is, using mathematics to describe the electrical behavior of transistors and circuits. A key contributor to this work was Hermann Gummel of Bell Labs, described as a "giant" in the field (Pederson interview, 5/23/97), the first to describe mathematically the nonlinear behavior of transistors. This early work was applicable to both board-level and integrated circuit level design.

By 1969 there were several circuit design software tools in use in industry, although generally speaking they were not available as commercial products. Most were created by organizations working under contract to the Defense Department. Some of the more notable early programs were ECAP, developed by IBM; CIRCUS developed at Boeing and MIT; POTTLE, developed by C. Pottle; SCEPTRE, developed by IBM; NET-1, developed at Los Alamos; and CALAHAN, developed by D. A. Calahan at the University of Illinois. These early programs were followed by dozens of other programs with ever-increasing capabilities.

The development track in circuit synthesis and testing was very similar to that of physical design. The software was designed for immediate industrial and military applications. Companies would borrow from existing programs and improve on them to generate new programs. However, these new programs were usually slated to fulfill a narrow, internal requirement, so little effort was devoted to standardization. Most programs required extensive modification if they were to be used beyond the immediate industrial or defense environment for which they were designed (Sketoe, 1963). By the late 1960s, the situation was very similar to that described above for physical design: a multiplicity of software programs existed, each designed for, and applied to, the narrowly-defined requirements of individual companies or laboratories. No company considered these packages as material for commercial markets.

This situation changed in the early 1970's with the advent of SPICE. Berkeley, and in particular Donald Pederson, had been active in simulation since the early 1960s. In addition to this simulation work, in the early 1960s Pederson and his students were the first to build an integrated circuit in an American university (Pederson interview). Nearly all of the integrated circuit work was supported by the Department of Defense, while firms such as IBM and Hewlett-Packard supported some of his later simulation work. In 1972, Pederson introduced SPICE. SPICE was comprised of algorithms borrowed from a number of different industrial and military programs; it incorporated knowledge and algorithms developed at Berkeley over the previous decade, rewriting code to produce a comprehensive simulation program (written in FORTRAN) that made it compatible with any machine. Although many argue that it was not the most capable package on the market, it was the most universally applicable (Hachtel interview; Pederson interview). As McCalla describes it, Pederson's and his students' contribution was largely in simplifying the access to and use of simulators, that is, bringing it down to the level of use of practicing engineers and students (McCalla interview, 6/23/97). Pederson externalized the market for simulation and testing software by making SPICE readily available to all.

Some details on the development of SPICE reveal interesting features of the roles played by industry and universities in the field of simulation, and of the ways in which university knowledge is transferred to industry. Ron Rohrer, who received his Ph.D. in electrical engineering from Berkeley in 1963, returned to the faculty in 1966. In 1969 he took a two year leave of absence under a Ford Foundation Residency in Engineering Practice to work for Fairchild Semiconductor. At Pederson's suggestion, in 1971 Rohrer took leave from Fairchild to teach a graduate course at Berkeley. Rohrer told his students that their task was to take the existing circuit simulator programs and concepts and create the best simulator program. According to Pederson (interview, 5/23/97), the result was not perfect, but the overall set was great--and to Pederson, it was the set that was important. The key was the best set of routines, not the best routine for each component. The code was called CANCER. Rohrer made CANCER proprietary, not because he wanted to make money, but because he wanted industry to donate $25,000 to Berkeley. There were no takers (Rohrer attributes this to being ten years too early), so Pederson recast it as SPICE I in 1972. In Pederson's words,

The technologies underlying simulation and testing, such as mathematical descriptions of circuits, continued to develop through the 1970s and 1980s. Although these underlying technologies were not as sensitive to changes in integrated circuit geometry as physical design, the advent of new types of transistors (e.g., metal oxide semiconductor, or MOS) nonetheless forced several innovations in modeling circuits and components. In contrast, it was the increase in the number of circuits per chip that forced significant changes in testing procedures.
 

Synthesis

Defining and bounding synthesis is a challenge in itself. To aid in our description of the processes involved in the synthesis phase of CAD/EC, we will employ commonly-used terms that describe the several levels of electronic design: gate level, register level, and behavior level. Gate level refers to modeling logic circuits; register level refers to modeling the behavior of interconnected sets of logic circuits; behavior refers to modeling entire systems of logic circuits. Among CAD/EC researchers, work on synthesis began in the 1970s as an offshoot of their research into simulation and testing. Concurrently, researchers in the computer design field began work on register theory, and subsequently on behavior theory, but until the late 1970s did not consider these areas to be an application for CAD. Unlike the situation that faced designers conducting simulation, testing, and physical design in the mid-1970s, human designers could still handle synthesis design issues manually. Although development of the microprocessor required that higher-order synthesis issues (e.g., behavior level) be addressed on the chip itself, the threshold point at which humans could no longer carry out any of the design tasks did not occur until the advent of VLSI chips in the 1980s.

To simplify the situation somewhat, in the 1970s there were essentially two groups working on synthesis problems. The first group, which we will call the "bottom-up" developers, had strong foundations in physical design as well as simulation and testing. They were already using gate-level logic simulation software in concert with circuit simulation software. Their work was usually driven by industry, which had a strong interest in gate level problems. The work of Melvin Breuer and his colleagues and students on the ADAM project at USC in the early 1980s was typical of this stream of development. Breuer's team had a strong background in routing and placement as well as simulation and testing, including links to the Berkeley researchers and to industry. Breuer's objective was to apply their knowledge at a higher level--the systems level--to contribute to the design and fabrication of the next generation of computers. They employed system-level simulation and testing tools that paralleled those used at the board and chip level, and they developed and used placement and connection algorithms that had their analog at the chip level. The latter activities, placement and connection, drew largely upon existing operations research techniques and graph theory. Much of the ADAM project, both knowledge and students, was absorbed by AT&T. The major contributors in the larger effort were mostly from industry rather than academia; they sought solutions to immediate problems and found the mathematical tools to solve them in the existing literature.

The "bottom-up" development stream was also supported by groups focused on chip development. This group is typified by Carver Mead (Caltech) and Lynn Conway (Xerox PARC). Mead and Conway worked on the problems of producing VLSI chips as early as 1970. They were among the first to recognize that the design process and manufacturing process had to be separated. The Caltech Intermediate Form (CIF) computer language developed at Caltech in the 1970's allowed for the separation of the two critical processes. Mead and Conway recognized very early on that semiconductor design and manufacturing problems were going to become so complex that researchers and ultimately computer software had to be able to address them in isolation.

The bulk of Mead and Conway's work was done in the context of chip development, not software development. But the process of improving chip design naturally created improvement in the tools used to design chips. Much of their research was carried out under the auspices of the MOSIS project. The history of MOSIS is well documented and research into improving chips is outside the narrow bounds of this case. However, we must note that the quest to improve chips as typified by the DARPA- sponsored MOSIS project contributed greatly to expanding the pool of researchers working on semiconductor problems, pushing the CAD/EC software designers to expand their capabilities, and in some cases contributing directly to development of CAD/EC. NSF played a small role in MOSIS financially but a large role as proponent and coordinator. (Sproull, personal communication, 1998)

The second group, the "top-down" developers, was typified by Daniel Siewiorek and Stephen Director at CMU. Siewiorek and his colleagues had been working on register transfer theory throughout the 1970s. They also had been working on higher-order behavior design issues. In the late 1970s, with the addition of Stephen Director to the team, they formulated the first comprehensive software design project that incorporated nearly all aspects of integrated circuit design. This pioneering effort generated numerous incremental advances, many of which eventually were absorbed by companies such as Mentor Graphics and Cadence. This work also paved the way for future VLSI designs almost a decade before the first VLSI chips were manufactured commercially.

These two groups did not work in isolation. Researchers at Berkeley, CMU, and USC were exchanging students and faculty both among themselves and with industry. By the mid-1980s, there was a significant harmonization of approaches:

Commercialization

By the late 1970s the stage was set for the emergence of firms devoted exclusively to design software and services when it became more efficient for chip manufacturers to buy rather than make such software. McCalla's rule of thumb was that one programmer was required for every 10,000 lines of code, and that as the systems became more complex, it was not possible to grow in-house staffs at the level needed to do design at the VLSI level (McCalla interview, 6/23/97). Some in-house design groups got as large as a startup tool company. Computer and chip manufacturers experienced difficulties moving from gate level automation to the register and behavior level. According to Siewiorek, companies like Digital

Contributions of Fundamental Research and Technology Development

The basic science content in physical design was relatively low. Much of the early work centered on tinkering and optimizing heuristics and converting heuristics into codeable algorithms. The basis for the heuristics did, however, have a strong footing in science. Game theory, optimization theory, and spanning tree mathematics played central roles in early developments. But the science was already well developed by the 1960s, and advancement in physical design contributed little to expanding the science base. The same is largely true for synthesis; as Siewiorek put it, "you have to go back to Quine and McCluskey in the 1950s for Boolean logic; von Neumann and Shannon were talking in the 40s about relay computers to make them more reliable" (Siewiorek interview, 10/31/97). At the higher levels that were the target of research at CMU, there were a lot of new algorithms, some having their roots in graph theory in the 1800s. The math existed but had to be applied; progress did not cease for lack of knowledge. "There were pockets of discoveries. After enough of them, you could put them together to move ahead" (Siewiorek interview, 10/31/97).

Almost all problems in the industry required new heuristic techniques. These are "search techniques," not optimization algorithms. Developing effective heuristics is hard work and requires diligence, but it seldom contains a strong or new theoretical underpinning. There have been no great mathematical breakthroughs or related scientific advances that led to improved algorithms. Pederson describes the work he and his group were doing as engineering, not science. To quote Pederson, "we were driven by necessity." They used the simplest math and physics possible. This induced some error, but it increased the likelihood of getting code that worked. "We never waited on the science" (Breuer interview; Pederson interview). According to Breuer, the major design firms now do less and less research, preferring to obtain state-of-the-art knowledge by buying startup firms.

According to Breuer, who evidently was taking a long view spanning the two decades of CAD/EC development prior to the mid-1980s, most of the technology's development occurred within industry and universities. IBM had the largest in-house design group in the world. Other firms, such as Bell Labs, TRW, and Hughes also had major in-house groups. The shift to external sources occurred as entrepreneurs developed CAD tools. Most university work, in his view, consisted of incremental improvements. Their major contribution was students.
 

IV. Roles of Government, Industry, and Universities

As early as 1957, the Army saw the importance of circuit design and gave Berkeley a grant to set up a full circuit design lab. The justification was to develop reliable rockets. Because integrated circuits are much more reliable than traditional circuits, microelectronics was the answer to making rockets more reliable. Beginning with a $30,000 grant from the Army, Pederson and a student made the first integrated circuit in an American university. Berkeley now has a third generation microfabrication lab (Pederson interview, 5/23/97).

During the early stages of CAD/EC development, the federal labs, the military, and industry were the primary players. By the 1970s the problems became more complex, and one consequence was an increase in academic interest in the problem, made possible by the substantial infusion of computing capability in academia that resulted from DARPA and NSF support of equipment purchases (Aspray and Williams, 1994). Some of the early academic pioneers included Breuer at the USC. Prior to 1970, academic research contributed indirectly through game theory, optimization, and other supporting technologies. But it was not until the late 1960s and early 1970s that academia begin to focus on the use of these technologies in electronic circuit design applications.

As problems became increasingly complex, partnerships formed between universities and in-house design groups in firms such as Philips, Signetics, and Texas Instruments (McCalla interview, 6/23/97). Gummel observed that during the early period there was extensive interaction among major contributors from industry and universities. They attended the same conferences (IEEE, DAC, ISSCC), and industry hired the best students from the major research groups. Gummel attended liaison meetings at Berkeley; Bell and IBM sponsored faculty sabbaticals at their labs (Gummel interview, 6/24/97). As Berkeley expanded its circuit simulation work, it forged strong links with industry, including hosting IBM fellows, providing sabbatical leave in industry, and gained access via an alumni network to industry programs for students to work with. Several Berkeley students spent summers at IBM. IBM's Gary Hachtel worked on early versions of SPICE while he was a graduate student there; he later worked on optimal design issues with other Berkeley researchers.

The primary contribution of university-based work in synthesis was not software-specific packages such as SPICE that could be adapted by or used in industry, but the trained students who brought industry-relevant knowledge into the marketplace. Speaking not of synthesis alone, but of the entire evolution of CAD/EC, Breuer observed that

According to Wally Rhines of Mentor Graphics, the major centers of expertise in CAD/EC were IBM, Bell Labs, Texas Instruments, and Berkeley. Everything IBM and Bell did was for internal purposes; they made little effort to commercialize CAD/EC. They did, however, provide the researchers who became the nucleus of people to staff newly-formed design companies. One example is John Cooper, who specialized in place-and-route research for IBM and then left to work for Cadence. More recently he started his own firm, Cooper-Chyan (Rhines interview).
 

Support for Key Contributors to CAD/EC

In 1988 the Design Automation Conference, an organizational unit of the Association for Computing Machinery (ACM), published a volume of papers commemorating 25 years of progress in electronic design automation (Association for Computing Machinery, 1988). This volume, consisting of 76 selected papers published over the period 1965-1987 in the Proceedings of the ACM/IEEE Design Automation Conference (DAC), where chosen to "document seminal work that was first published at the DAC." Choices were made by the Technical Program Committee and the Executive Committee of the twenty-fifth conference. The Committee's charter was "to begin with the important concepts and ideas of today and look back for the papers that led to these choices. To qualify for a place in this issue, a paper not only presented an original contribution, but it also influenced the position of the industry today" (ACM, 1988: 6). The 1988 volume is divided into three sections, represented three separate streams of research and development: physical design; simulation and test; and synthesis, systems, and user interface. These correspond closely to our own three-part characterization of the field. As one means of identifying the influence that NSF support of research may have had in the field, we identified the institutional affiliation of the authors of these 76 papers and noted acknowledgments to sources of support when these were provided. The following tables summarize the results.
 
 

Physical Design: The NSF grant to the University of Southern California was for $120,000, for 36 months, entitled "Design Automation of Digital Systems." Although the NSF awards data base does not list a PI for this award, the paper involved was authored by Melvin Breuer of USC. Breuer received a number of NSF awards in the general field of design automation, beginning in 1967. Breuer's other awards were in 1969, 1973, 1979, 1981, 1982, and 1984. The preface to the DAC volume comments that "Breuer's 1977 paper . . . is at the root of a productive line of placement algorithms based on partitioning" (ACM, 1988: 3). The other NSF award was to Ronald Rivest of MIT, a 5-year, $477,788 grant for "Concrete Computational Complexity (Computer Research)," awarded in 1981. This award had been preceded by two additional awards for the same line of work dated 1976 and 1978, together totaling $256,000. This was a very large project jointly supported by NSF, General Electric, DARPA, and the Air Force. The preponderance of industry authors in the field of physical design suggests that automating the physical design and layout of circuits offered the prospect of more cheaply meeting the production requirements of circuits for commercial and military applications.

Simulation and Testing: NSF does not appear in the acknowledgments to papers in this field. Much of the support that was acknowledged came from defense agencies. Among private firms, Bell Labs and IBM dominated contributions to this field as well as to physical design.

Synthesis: Universities played a much larger relative role among major contributions to synthesis than they did in the other two fields of design automation. Not only did Bell Labs and IBM together contribute much less than was the case for physical design and simulation and testing, but there is evidence of closer industry-university collaboration in this field (note industry-university coauthorship in three of the papers). NSF support was significant among these contributors. NSF awarded $210,000 for 24 months to Carnegie-Mellon (Daniel Siewiorek, PI) for "Synthesis, Evaluation, and Automation of Digital Systems Architecture," and just over $500,000 in 1979, also to Carnegie-Mellon (Stephen Director and Daniel Siewiorek, PIs) for a 36-month study on "Multilevel Computer Aided Design of VLSI Digital Systems." The latter project was supported jointly by the Electrical & Optical Computing Program and the Computer Engineering Program, while the former was part of a large project at CMU supported jointly by NSF and the Army. Thus the authors of three of the 16 papers selected as top contributions to synthesis acknowledged NSF support.

Overall, of the 30 papers authored or co-authored by university-based researchers, 5 acknowledged NSF support. Together, NSF and various agencies of the Department of Defense provided almost all of the government support to university-based researchers chosen as major contributors to design automation over the 1965-87 period.

The pattern of NSF support for authors of papers chosen for inclusion in the DAC/25 volume is another method of identifying the Foundation's support for key contributors to the field of CAD/EC. During 1967-1988, NSF made 36 awards to the authors of DAC/25 papers. These awards, by data, institution and PI, are presented in the following table:
 
 
 

These awards totaled $7,373,084; the pattern of NSF investment in these particular researchers over time is displayed in the following chart.
 
 

In 1989, CMU was one of the winners of the competition for an Engineering Research Center. In that year, with Daniel Siewiorek as PI, CMU was awarded a $20 million cooperative agreement for an ERC in Engineering Design.
 

V. Role of Intellectual Property

Through the period of interest in this case, that is, until the mid-1980s, intellectual property played a minor role in the evolution of CAD/EC. As we have seen, commercial development of software packages did not take the form of discrete vendors until well into the 1980s. Prior to that time, design automation software was produced by in-house design shops, customized to each company's specific requirements. Following Pederson's lead at Berkeley, universities generally chose not to patent design automation software. As one of our interviewees put it, "My opinion is that I don't think universities should try to make money off intellectual property. If you are doing good work, industry will come and support you. It is hard to patent these things." (Siewiorek interview, 10/31/97). Finally, there was, as we have seen, considerably sharing of software between universities and industry and even among competitors. David Hodges, former Dean of Engineering at Berkeley, argues that

A search of the on-line U.S. Patent and Trademark Office data base, which begins with 1971 patents, supports this conclusion. Use of the search terms "(automated or computer) and design and electronic" yielded a set of 70 patents. When patents that clearly were not relevant were eliminated, the list contained 43 patents. All 43 were assigned to private firms, as the following table shows.
 
 

A second feature of these patents was their recent filing dates. Most filings occurred in the 1990s, and none of the patents was filed before 1980. Seventeen patents that were cited more than 10 times by the set of 70 patents, an indication of their relative significance, all were granted after 1986. Thus, patent activity in the CAD/EC field is a very recent activity.

Another feature of the 43 design automation patents is their extraordinarily heavy use of references to the academic and research literature, an indication of strong linkages to science. These patents cite a total of 655 pieces of research literature, an average of over 15 references per patent. Indeed, the "other references" sections of nearly all of these patents looks more like the reference section of an academic paper than a patent application. This indication of linkages to science is far stronger than in any of the product groups studied by CHI Research, Inc.; among CHI's product groups, the "drugs and medicines" group's citation rate is just over 5 references per patent. NSF grantees and contributors to the DAC/25 volume Melvin Breuer and John Ousterhout (Berkeley) are cited heavily in these patents: Breuer's work is cited 12 times and Ousterhout's 9 times.
 

VI. NSF Role

Organization for Support of Computer Science and Engineering

During the period of interest in this case, most of NSF's support for research in computer science and engineering was provided from the Computer Science Section (in various forms) of the Division of Mathematical and Computer Sciences, within the Division of Mathematical, Physical, and Engineering Sciences (MPE). Support for computer engineering was also provided from the Division of Electrical, Computer, and Systems Engineering in various forms, but this research focused on areas other than computer software. In 1967 NSF created a separate section, the Office of Computing Activities, The office supported research in three major areas: computer science, computer-based instructional technology, and computer applications. Three years later, in fiscal year 1971, the Office of Computing Activities was split into three new sections: the Computer Science and Engineering Section, which sponsored research in fundamental computer science, the Computer Innovation in Education Section, which supported research on computer-assisted education, and the Computer Applications in Research Section, which emphasized the use of computer techniques in the advancement of research (NSF Annual Report, 1971: 49). The facilities program was discontinued after FY 1971, and education activities were transferred to NSF's Education Directorate. In 1975 the MPE Directorate combined all programs of the Division of Computer Research under a single section of the newly formed Division of Mathematical and Computer Sciences. This enabled the Division "to devote our primary attention to computer science research" (NSF Program Report, Computer Science, vol. 1, No. 5 July 1977).

In 1986, NSF established the Directorate for Computer and Information Science and Engineering (CISE), in order to consolidate programs in computer and information science and engineering from throughout the Foundation. The Division of Computer Research, the Division of Information Science and Technology (formerly in the Directorate for Biological, Behavioral, and Social Sciences), the Office of Advanced Scientific Computing (which handled supercomputer centers and networks), and selected computer engineering and communications/signal processing activities from the Directorate for Engineering were brought together under CISE (NSF Annual Report, 1986: 72).
 

Strategies for Support of Computer Science and Engineering

Referring to the early days of the Office of Computing Activities, Program Director John Lehmann characterized the prevailing strategy as follows:

In 1974 the NSF Annual Report stated that the Division of Computer Research "places major emphasis on fundamental aspects of computer science and engineering and on research directed toward the development of techniques that increase the responsiveness of the computer to the requirements of scientific disciplines" (Annual Report, 1974: 37).

By 1981, the importance of VLSI was clear, as evidenced by the following excerpt from that year's annual report. Under the section on computer science:

• fault tolerance and reliability
• system performance measurement and evaluation
• graphics and input/output research
• logic design and major subsystems (beginning in 1974)
• VLSI design methodology (beginning between 1977 and 1980)
• computer graphics (beginning between 1977 and 1980).

The promise of VLSI chips was apparent throughout the 1970s, and NSF began to support researchers in this field. At Carnegie Mellon University, for example, PI Gordon Bell was awarded a five-year grant to look at the design of modular systems using register transfer level design notation, enabling them to wire together a minicomputer in an 8 hour day. Subsequently CMU wrote a successful proposal to explore what was beyond the register transfer level which began the university's work on microprocessors. To support this work, CMU asked NSF if they could do simulations--i.e., CAD. Later, when DARPA started to support multiprocessor work, CMU asked NSF if they could focus on CAD. By 1976, according Daniel Siewiorek of CMU, NSF fully understood the importance of CAD and provided increasing support (Siewiorek interview, 10/31/97). The chart below and the appendix to this chapter describe NSF support for VLSI research from 1978 through 1990. Particularly noteworthy are research initiation grants (6), Presidential Young Investigator awards (7), two workshops, and the two large awards in 1983 to Duke University and the University of North Carolina for "VLSI Computing Structures and Design Methods and Interactive Computer Graphics." Total support for the period 1978-1990 was $13,644,840.

Perceptions of Selected NSF Grantees

Melvin Breuer of USC described himself as having had almost continuous funding from NSF for the first 20 years of his research. Then, about ten years ago, he shifted over to (D)ARPA funding, because DARPA offered larger grants. Despite his years of funding from NSF, he reported little knowledge of NSF support strategies. He wrote proposals and was funded (Breuer interview, 8/20/97)

NSF's limited role in both physical design and simulation can be attributed partially to the absence of significant fundamental research content in the latter, and to the reactive management strategies used by NSF during the 1960s. William McCalla, a former student and colleague of Pederson's at Berkeley and now at Cadence Design Systems, noted that until the mid-70s it was possible to associate a given individual with a given technical advance; after that date, progress was largely a matter of teams. Also, not surprisingly, NSF played no visible role in the development of the technology. McCalla could recall no specific contribution of NSF. He was employed on numerous projects during his student years at Berkeley, could not recall how he was supported on Pederson and his colleagues' grants (McCalla interview, 6/23/97).

Berkeley's Pederson recalls no NSF support for the work that led up to SPICE. His NSF support was for design, not simulation. In Pederson's view, the work was "not peer reviewable" because it was engineering, not science (Pederson interview, 5/23/97). This view is supported by Wally Rhines of Mentor Graphics, who observed that the tasks associated with CAD/EC were seldom "research" issues, although there were some debates about mathematical properties; rather, they were mainly tasks of making CAD/EC practical. He believed that NSF support probably contributed to research on device modeling (Rhines interview).

As NSF's management strategies shifted in the 1970s, major grantees in the synthesis field described a more activist role, though one still based in investigator-initiated, peer-reviewed grants. In Siewiorek's view, NSF sought to influence where university researchers focused their work. As he sees it, NSF relied on a small number of key universities, at the forefront of research in an area, to help generate new ideas. NSF supported workshops, which yielded ideas for education and research that in turn led to proposals from a much wider range of institutions. CMU itself has conducted a number of workshops, particularly Siewiorek commented that NSF program directors are very good at noticing new ideas and getting people to work on them, "on a shoestring or speculation," by supporting a workshop, producing a paper, then defining a research program that will build a constituency. NSF has thus been "partners at the front. They are good at seeing something and acting on it. They were very good at moving more people into the area" (Siewiorek interview, 10/31/97).
 

VII. Conclusions

Government-Industry-University Relationships

The evolution of computer aided design software, which eventually became embodied in successful commercial products marketed by hundreds of computer software and service providers, occurred within the context of government support for computer hardware and software development and use. In the 1950s, defense missions supported development of the computer itself (in which universities played a central role) as well as a number of related technologies such as interactive graphics and visual display terminals that later would become elements of commercial products. In the 1960s, defense demands for reliability in electronic devices spurred invention of the integrated circuit and led, indirectly, to development of computer-based design aids that made component placement, wiring, and printed circuit board layout more efficient. At this time NSF, recognizing that computers were the key to advancements in many scientific fields as well as to graduate student training in science, provided massive support to universities to acquire and maintain state-of-the-art mainframe computing equipment.

To focus specifically on the development of CAD/EC, during this period there were extensive interactions between industry and academia that took various forms: consulting, visiting professorships from industry, exchanges, and student internships in industry, that kept academia closely tied to industry needs and problems. Most observers conclude that, during the 1960s, technological leadership in CAD/EC was based in industry, particularly in a few large firms such as IBM and AT&T. The university's contribution was not "science," but rather (1) pragmatic software developments in simulation and testing such as SPICE, which had wider applicability than the more powerful but highly specific tools developed internally in computer and semiconductor manufacturers; and (2) students, trained in the use of these tools, who populated industry and in many cases extended the state of the art while employed there. Industry was thus the primary source of incremental but cumulatively significant advances in CAD/EC.

In the 1970s the picture changed. Design automation had to this point been primarily the response to the high cost of routine operations handled manually, and secondarily to the increasingly complex problems that board and chip designers faced. By 1975 it was impossible to design state-of-the-art chips with the density of components required without computer aids. Industry struggled to meet these needs by expanding their in-house design staffs, while a few visionary academics looked further ahead, realizing that within ten years behavior-level synthesis, required by VLSI chips, would have to depend on computer aided design. Some of the leading universities, still closely linked to industry and, indeed, as a result of these linkages, understood yet looked beyond the short term needs of industry and proposed research that was responsive to far longer term requirements. There was a sizable response from government, primarily from NSF and DARPA, that in no small way contributed to the successful commercial development of CAD/EC software in the 1980s.
 

Fundamental Research and Technology Development

During the entire period of interest in this case, there was little evidence that the evolution of CAD/EC was retarded by the lack of fundamental scientific knowledge. The basic mathematics was there to be applied, producing incremental advances oriented more toward solving problems quickly and simply than elegantly. Advancements in CAD/EC were incremental engineering innovations, not science-based. This is not to deny the importance of fundamental knowledge--it was crucial, but it already existed (e.g., Boolean algebra) and could be applied (not without some effort) to the problem at hand.
 

Intellectual Property Protection

During the 1960s and 1970s, the major players in CAD/EC chose, for very different reasons, not to concern themselves with intellectual property protection of the software tools they produced. The central university figures were not motivated by interest in profits for themselves or for their institutions, at least through royalty payments. They felt that they, their students, and their universities would benefit more substantially through subsequent gifts and research contracts, and history seems to bear them out. Meanwhile, industry kept its software packages close to its collective chest, relying instead on the protection offered by trade secrets rather than copyrights. It may have a been a moot issue, anyway, since so many of these packages were designed for extremely narrow, internal applications. There was, at least among the industry leaders, some cross licensing, presumably a result of recognition that sharing of knowledge would benefit all more than would restricting its flow.

Once commercially available CAD/EC packages appeared on the market in the 1980s, patenting activity surged. However, it did so primarily among late entrants rather than the "old guard," possibly because the early entrants relied on know-how and their reputation for service. Recent entrants to the market are patenting extensively, but that may be for reasons related more to staking a claim than any expectation that their profits will be a consequence of intellectual property protection.
 

NSF Role

NSF supported the research of a number of key contributors to CAD/EC: Pederson, Breuer, Siewiorek and Director, and others. That support was often supplemented, in some cases dominated, by additional support from defense agencies. During the 1960s, research that was driven primarily by industry needs (e.g., Pederson, Breuer) was supported by defense agencies, while the more theoretical aspects were supported by NSF. Advances that had immediate impact in the field were practical and incremental, not theoretical. With the advent of the 1970s, NSF's new, more activist managerial stance appeared to bear fruit. Workshops involving university and industry researchers strengthened communication between the two sectors, and identified industry-related research priorities to which academic researchers could respond. At the same time, industry representatives on NSF advisory committees and peer review panels could critique proposals for research. As exciting ideas emerged from university research, NSF program directors, encouraged by the larger climate within the Foundation of willingness to identify areas of promise and support them, used the workshop strategy to enlarge the community of interested university researchers. By the 1990s, for example, the number of academic institutions involved in VLSI research had multiplied severalfold. According to our interviewees, NSF is perceived as willing to speculate on promising yet risky areas of research. In the case of CAD/EC in the 1970s and 1980s, this strategy apparently has paid off.
 

VIII. References

• Aspray, William, and Williams, Bernard O. "Arming American Scientists: NSF and the Provision of Scientific Computing Facilities for Universities, 1950-1973," IEEE Annals of the History of Computing, 16, 4 (1994): 60-74.
• Breuer, Melvin A. ed. Design Automation of Digital Systems. Englewood Cliffs, NJ: Prentice-Hall, 1972.
• Breuer, Melvin A. ed. Digital System Design Automation: Languages, Simulation & Data Base. Woodland Hills, CA: Computer Science Press, 1975.
• Kuo, Franklin, and Magnuson, Waldo, eds, Computer Oriented Circuit Design, Prentice-Hall, Englewood Cliffs, N.J., 1969.
• Katz, B. and Phillips, A. "The Computer Industry," in Richard R. Nelson, ed., Government and Technical Progress. New York: Pergamon, 1982.
• Lehmann, John R. "NSF Support of Basic Research in Computer Science," Computer, July 1978: 10-14.
• Mead, Carver, and Conway, Lynn. Introduction to VLSI Systems. Reading, MA: Addison-Wesley, 1980.
• Mowery, David C. and Langlois, Richard N. "Spinning Off and Spinning on(?): The Federal Government Role in the Development of the U.S. Computer Software Industry," Research Policy 25, 6 (September 1996): 947-966.
• Newton, A. Richard, and Preas, Bryan T. eds. 25 Years of Electronic Design Automation. New York: The Association for Computing Machinery, 1988.
• Norberg, Arthur, and O'Neill, Judy. A History of the Information Processing Techniques Office of the Defense Advanced Research Projects Agency. Minneapolis, MN: The Charles Babbage Institute, 1992.
• Pederson, D.O., "A Historical Review of Circuit Simulation," IEEE Transactions on Circuits and Systems, vol. CAS-31, no. 1, January 1984: 103-111.
• Preiss, Ralph. "Introduction," in Breuer, Melvin A. ed. Design Automation of Digital Systems. Englewood Cliffs, NJ: Prentice-Hall, 1972.
• Rivest, Ronald, and Fiduccia, Charles, "A 'Greedy' Channel Router," MIT Laboratory for Computer Science, Cambridge, Mass, and GE Research and Development Center, Schenectady, New York, 1981 [DAC-25].
• Sketoe, James G., "Computer Aided Design and Analysis," master's thesis, Naval Postgraduate School, Monterey, CA. NTIS AD 841319, June 1963.
• Sproull, Robert. Personal communication, February 1998.
• Sutherland, I. E. "Sketchpad: A Man-machine Graphical Communication System," DAC-25, 1988: 507-523.
• Vladimirescu, Andrei, The Spice Book. New York: Wiley, 1994.