V Is For Vortex – More Categorical Programming

Vortex, A Categorical Database

In the early 90’s I led a product team of three folks to create Vortex, a database for electronic design automation (EDA).  This work at Intergraph Electronics/Dazix/Veribest was based on the categorical programming technique previously developed for the Clipper microprocessor.  As it happens the product was never released.  The one remaining artifact is a single slide.  However it shows a fair number of aspects of how the various objects are related.

Inversion Or Fibration Operator

We do not see the calculation for shorts and opens as explained in the prior article, but it does show more about Vortex’s inversion operation as shown in the following snippet.  Perhaps a better name for the operator is fibration, but at the time with the CAD team the word “inverting” was chosen as in “turning the arrow around”.

Choices of inversions for a given X–>AxB

Start with a mapping from X to the Cartesian product AxB as you see at the center of the above diagram.  The six other heavy-headed arrows represent the possible inversions.  In the Intro To Categorical Programming, we only had X to A, and the only option was to go back from A to X.  By having the codomain be a product, we have more choices for an inversion’s domain and codomain.

As an example consider again the problem of electrical connectivity.  In this case we want to know which polygons touch which other polygons as that is quite important for electrical conductivity.  The input to the Vortex touch operator is then a list of polygons represented as a mapping A–>edge where edge refers to the space of all edge sets.  Many algorithms need polygons represented as edge sets versus a nominal polygon’s point list, so edge sets used here.  The output is a list of pairs of polygons that touch, represented as X–>AxA.  By taking the inversion f from the first factor of A to the second factor of A we have a means of tracing electrical conductivity since for any a in A, a touches f(a).

Touch And Merge Operators

The main diagram above shows the merge operator, which does more than the touch operator:

Merge operator

One output from both merge and touch is Rel2Lyr:K–>XxY which is a list of pairs of indices of touching polygons.  The additional work done by merge is to produce OutLyr which has the touching polygons merged together.  As  you might expect, touch is much faster than merge.

Basic Cell Structure

In EDA, cells are the basic unit of design.  So if you have a polygon, you must put it into a cell.  The following diagram has a structure defining such a cell.  The table following explains the domains seen in the diagram.

Basic cell structure

c Component instances:  These are the references from this cell to other cells to be placed wholly into this cell.  This is the primary technique by which computer chips are designed by giving them hierarchy.  The uppermost cell is called the top cell.
ct Component types:  A single cell may be placed thousands of times.  For example, an inverter is a common device that takes a signal of 1 and converts it to 0, as well as 0 to 1.  This inverter is then a type, and an instance is where it is placed elsewhere in the design.
iotyp IO types:  The set of all IO types, such as ‘in’, ‘out’, or ‘bidirect’.
n Nets:  These are the designed electrical nets representing how electricity is connected from one point to another.
p Pins:  The pins show how nets connect to the lower level cells referenced from this cell.  In other words, the pins on a cell instance are then the external pins are that cell type.
pr Properties:  Various properties assigned to objects.
prtyp Property Types:  The set of all property types.
strng Strings:  The set of all strings.  We use this for the names of nets, cells, pins, and so on as seen in the pnam, nnam, … maps.
xp External Pins:  The connections to this device required of the outside world.  For an inverter, it has two external pins: IN and OUT.
Z Integers:  The set of all integers.

The above structure is essentially what is referred to as the netlist.  There are no manufacturable polygons as yet.  These relations were stored on disk.  Diagrams based on these arrows then produce programs driving the production flow.