1988 Reports

Concurrent Algebras for VLSI Design

Balraj, Timothy S.

As the size and complexity of VLSI chips increases, designers are beginning to rely more and more on automated chip design systems to help layout, route, or even design circuits. silicon compilers convert the functional description of a system to a mask level design of a chip that implements the system. In order to ease the task of describing the system, and to help analyse and verify its working, the description languages are based on algebraic systems. A typical circuit has a number of actions occurring at any given time. So we use concurrent algebras as the basis for the description languages. In this paper, we survey algebras that enable the description and analysis of concurrent systems. We examine them particularly from the point of view of using them to implement systems in VLSI. We therefore concentrate on the basics of each algebra, and omit features that are not readily implementable, such as recursion. We will look at four algebras: trace theory, path expressions, Milner's calculus of communicating systems (CCS), and an algebra of finite events (CAFE). We choose the first three since each has been used in some form of silicon compiler or other automated hardware design s)"Item, and together they demonstrate all the features found in higher level description systems for hardware. The fourth is an algebra that we are developing to address the problems of describing systems of events of finite duration. In chapter 2 we introduce an informal net notation and the concept of observers, which we use in the next four chapters to describe each algebra briefly. In chapter 7, we compare the algebras in terms of their treatment of independence, the type of parallel composition they use, and the inter-event dependencies they allow. We end by explaining the relative advantages and disadvantages of the algebras in various situations. The goal hoped that this comparative discussion of the algebras is to aid in the design of process description languages to be used in silicon compilers.