The History of KARL and ABL
of KARL and ABL Development
This survey is derived from the
This paper is not a tutorial. Because of limited space available here this paper gives only a limited survey on the evolution of the hardware description language KARL and its derivatives. We intend to stress such features, which are different from most other hardware languages. Before a comparison of KARL to other languages it is useful, to introduce a classification scheme for computer hardware description languages (CHDLs). There are graphic and textual languages. The number of abstraction levels covered differs between languages. That’s why we start with a look at the language classification scheme (also see). We may distinguish at least four different kinds of descriptions (Fig.1 a):
Fig.1 a is a modified version of the Gajski-Kuhn diagram, which does not distinguish functional and procedural descriptions as subclasses of behavioral descriptions. Another difference to Gajski-Kuhn is it, to distinguish pseudo-structural elements (to express partitioning without a physical meaning) from really structural descriptive elements (with a physical meaning). A third difference stems from the fact, that CHDLs do not deal with geometry (Fig.1 b). But there are only two CHDLs which are capable to express topology (which is close to geometry): uFP (by Mary Sheran ) and KARL (Fig.1 c).
KARL-1 through KARL-3 are non-procedural
including topology features, such as being characterized by Fig.1c.
All three textual languages (see sections 1.1.1thru 1.1.3) have been
designed to fit to a graphical companion notation ABL (such as logic
fit to Boolean equations). For more details on ABL and its
see 2) The coexistence of ABL and KARL is illustrated by Fig.4.
Later on some extended versions of KARL have been introduced, by new language implementations (languages CVS_BK and KARL-4) and by implementation of preprocessors being filter programs to existing KARL compilers (languages superKARL and hyperKARL). CVS_BK and KARL_4 also cover procedural descriptions, so that they are fully dichotomic languages (see Fig.1 d). However, hyperKARL and superKARL have no procedural part, but have features to support functional extraction from personality matrixes of gate matrix layout (what we called MOL (Matrix-oriented Logic). For more details on CBS_BK and KARL-4 see sections 1.2.1 and 1.2.2. For more on extensions by filter programs see section 1.3 .
KARL-1 through KARL-3 are non-procedural
including topology features, such as being characterized by Fig.1
c. All three textual languages have been carefully designed to fit to a
graphical companion notation ABL (such as logic diagrams fit to Boolean
equations). ABL stands for "A Block diagram Language".
ABL has already been introduced together with KARL-1 . In order to support structured VLSI design also featuring wiring by abutment all three languages include topology operators like “:“ for horizontal abutment and “@“ or "("...")" for vertical abutment (KARL-3 and up), as well as juxtaposition ("•" for subword catenation and "|" for array catenation). These features are reflected by the Domino notation having been introduced with KARL-1 by the book . Fig.4 illustrates this by a simple example (textual: fig. c) the use of block diagrams (a) and the Domino notation (fig. b). The language elements of KARL-3 are summarized by a number of tables in Fig.5 thru Fig.8.
The first version of KARL (KArlsruhe Register transfer Language) is the non-procedural hardware description language KARL-1 . KARL has been introduced together with a graphic language called ABL (A Blockdiagram Language). Like the textual notation of Boolean equations and the graphic notation of logic diagrams also KARL and ABL are companion notations. With ABL the Domino notation (Fig.16, also see above and Fig.4 b) has been introduced. KARL and ABL are used throughout a text book on structured LSI design . There has also been a KARL-1 implementation effort at Politecnico di Milano .
The second version KARL-2 has been developed at Kaiserslautern   (now KA in KARL stands for KAiserslautern). Parsers and Simulators have been implemen-ted at Kaiserslautern and elsewhere , running on VAX under VMS and UNIX. The language has spread, also through courses, summer schools and similar events, as well as by license agreements and by mailing manuals and other material. An interesting semi-typological feature is the ":" horizontal abutment constructor for lateral abutment of functions as a concise notation for merging data paths. This lateral abutment includes automatic check and connection of ripple flow.
Immediately after talks on KARL and its
during a summer school at Schuola Reiss-Romoli (L’Aquila, Italy),
has been asked to join the CVT proposal (CVT stands for CAD for
in Telecommunications). This proposal and its successor CVS (CAD
for VLSI Systems) have been approved by the Commission
the European Communities for being funded within the ESPRIT program.
two very large projects have been headed by Dr. Leproni at CSELT
Italy) provided a major break-through for KARL and ABL. During CVT the
version KARL-3 has been developed and implemented at Kaiserslautern 
(running on a number of different platforms) and integrated into the
software system. Finally several simulators have been available
RTcode, the intermediate form generated by KARL compilers 
A physical modeling extension has been implemented  to connect a
DAS 9100 hardware analyzer to a KARL simulator.
Also the first behavioral extension of KARL has been developed within CVT: a behavioral shell has been written around the KARL simulation system  . To derive KARL-descriptions from matrix-oriented logic (MOL, such as PLAs and others) and for generic KARL descriptions 2 filter programs have been written . These generic languages accepted by these preprocessors are called superKARL, or, hyperKARL, respectively.
KARL-4 and CVS_BK. Within the CVS project (the
successor of the CVT project) the language CVS_BK (CVS Behavioral KARL)
has been implemented , so that also sources for high level
  and systolic array synthesis   could be formulated.
Until beyond the end of the CVS project an improved version of CVS_BK has been developed at Kaiserslautern: KARL-4, especially polished also to fully support generic hardware descriptions .
To extract KARL-descriptions from matrix-oriented logic (MOL, such as PLAs and others) and for generic KARL descriptions 2 filter programs have been written . These generic languages accepted by these preprocessors are called superKARL, or, hyperKARL, respectively. These generic languages provide means to parameterize dimensions such as data path width, array size, fan-out size etc., and for recursive hardware descriptions of iteratively structured hardware. The behavioral extraction is supported by such features as well as by the bus de-scription primitives of KARL, which permit gate splitting needed to map transistor arrays.
Like software engineering, also hardware system
design has complexity problems. In both areas bad design styles may
to incomprehensible unmanageable structures. The term software
having been coined 1968 indicates common awareness of the problem.
two approaches have been advocated by the field: teaching structured
rules or similar concepts and discipline to follow such rules. Only
management (if available at all) has been really successful to achieve
such discipline. That’s why now, after 25 years, the software quality
has not yet been really solved. A more recent trend goes toward computer-aided
guidance, by CASE (global guidance) and OOP (object-oriented
more local guidance. VLSI system design has learned from software
hierarchical partitioning is one of the most important common concepts.
Now CAD framework R&D efforts have goals similar to those of CASE:
global guidance. But we also believe in local guidance in hardware
object-oriented design. A very efficient way is guidance by languages.
e. g. by block structure and data types.
The level of description of such hardware block
structures is that known from the PMS notation  (PMS
stands for Processor, Memory, Switch , where the term Switch
denotes memory managers, I/O channels, LAN servers and similar
and has no associations at all to the switching level). PMS is mainly a
structural notation for hardware platforms. Although most parts in such
structures are procedurally implemented, their behavior is hidden by
looking external views. Boxes at that level represent non-procedural
for procedural implementations.
Fig.10 shows a few simple
PMS notation examples, where the following abbreviations are used: M
memory, Mp for primary memory, Ms for secondary memory, P for
Pc for central processor, L for link, T for transducer, K for
D for Data Operation, and X for external world. Fig.11
shows more complex PMS examples, where S stands for Switch, and
C stands for stored program
Computer. A Computer is defined to be
an independent unit which includes a processor, private primary memory
and switch (compare Fig.11 a). The examples
that the PMS scheme is hierarchical. scheme.
The PMS scheme is merely a structural hardware
scheme. It does not reflect the relations of procedural objects hidden
inside its boxes. An improvement is provided by the HIM scheme
, which partly is a generalization of the PMS scheme (HIM
for Hierarchy of Interpretive
also supports nested machines  and semi machines and maps the
relations between modules by structural restrictions.
The HIM scheme provides for KARL-5 structural
rules and data types strictly distinguishing data side and control
crossing (information) flow (evoke, feed back,
see Fig.9 b, literals, etc.), crossing
boundary line, other horizontal flow, vertical flow
boundaries of hierarchy levels, like initialize etc., see Fig.12).
ABL. An interactive graphic ABL editor called
  has been implemented jointly by CSELT and Kaiserslautern
a CVT subtask headed by Guglielmo Girardi. ABLED is running on Apollo
under AEGIS and GKS. This hardware platform has been decided at a time,
where SUN did not have distributors in Europe, and DEC did not offer
The version GENMON has been derived from ABLED for design methodology
ABLED includes several interfaces, such as a PICT generator . An ABL2KARL translator helps to enter designs produced with ABLED into the KARL simulation system. Such ABL data structure translated into KARL may be further compiled into RTcode accepted by a number of other tools (see Fig.33).
To support design and especially teaching
a hardware description language should be simple and concise (i. e. it
should be compact and precise). To support and teaching structured
a language needs to be powerful without being baroque. To meet these
a good language should not have too much philosophy. Rather it should
natural modeling and familiar semantics. It should be self-explanatory
to support intuitive use.
Fig.19 shows a 4 input multiplexer (a), its partial VHDL description (c) and its complete KARL description (b). In (b) you write down a case expression similar to that known from programming languages like Pascal and connect it to the terminal node (Out1). In VHDL (c), however, you have to introduce delays (defined elsewhere) and a separate transport clause for each input: a lot of artifacts are needed, far away from the desired model.
Fig.22 shows the description of a bus with two drivers (a), the VHDL description (b), the KARL description (c) and the model in the KARL description (d). The open collector outputs of two and gates are drivers to a pullup bus (Fig.22 a).
Within VHDL description (b) a user-defined
function is needed, since buses are not included in the language
That’s because VHDL does not permit more than one signal source to a
This resolution function has to be defined in a procedural way - far
from the world of the hardware designer.
The inclusion of the bit value "undefined" in
KARL semantics also supports built-in ambiguous delay models. This is
for realistic modeling of racing conditions, what will be illustrated
the following example. Fig.24 a shows an intended
transition from 00 to 11, which due to races could end up in an faulty
transition to 01 or 10. This race condition will not be detected by a
Fig.25 illustrates, that
only a language level being too low, but also a language level being
high, lead to a strong increase of description cost. From this point of
view KARL is closer to
algorithms in silicon than VHDL. VHDL
also is very verbose. The above examples have shown that, compared to
VHDL is not simple and does not support conciseness. The user is forced
to create a huge framework around his problem, which does not directly
contribute to the desired model. Missing semantics forces the creation
of libraries of many natural things, which in case of KARL are part of
the language semantics. These user-defined libraries needed for VHDL
incompatibility problems. Because of the need to cope with all these
problems VHDL creates jobs - for consultants and organizers of courses
and user group workshops.
Using KARL as a calculus to obtain a regularly structured design is illustrated by the following multiplier design example. The problem is the multiplication of a non-negative integer multiplicand X with a non-negative integer multiplier Y to obtain a non-negative integer product P. First we define a set of theorems (1) thru (5) for integer multiplication.
means, that multiplication of w by 2i equals w shifted left by i bit positions.
means: shift left by i positions equals shift right by -1 positions.
means, that shifting by i, and then shifting by j, is equivalent to shifting by i+j.
means, that shifting by i first, and then adding equals adding and then shifting. From (2) and (3) we may derive the following:
When we apply (3) to (5) we obtain:
Now let us use these for designing an integer multiplier. We use an example with two 4-bit operands: a multiplicand X and a multiplier Y of the following form.
The product P is obtained by the following mathematical formula.
Application of rule (1) converts this into the following form.
By theorem (5) we obtain the following form.
By reversing the accumulation sequence from I = 0, 1, 2, 3 to i = 3, 2, 1, 0 we obtain:
The following detailed form of this does not represent a regularly structured design.
The shift left by 4 at the output, which is not really significant, will be discussed later. By consecutive application of rule (3) we obtain the following form.
Adding C is permitted if C = 0. This leads to the form.
This represents a regularly structured design, since we may partition it into four layers which we call MultLayer. Since yi is a single bit only we obtain a multiplexer within MultLayer:
From (2) we obtain the cell MultLayer as
by the ABL diagram in Fig.26 a.
Now we need another circuit, which generates
yi with i = 0, ... 3 to feed all ConAddShi layers. We call this
circuit the Condition Bit Generator or, briefly CoBiGen.
From the word Y(0) (Fig.26 c) the
y0 is derived by selecting the least significant bit (Fig.26
c) by using the lsb standard function of KARL. The selector y1
the next ConAddShi we obtain from Y shifted to the right: from Y(1)
= shr(Y(0)) (see Fig.26 e),
y1 = lsb(Y(1)) of the next layer. To
all yi for i = 0, ... 3 we assemble an iterative sequence of
layers: the multiplier bit generator CoBiGen shown by Fig.27.
Finally we abut the CoBiGen (on the
side) with the 4 layers of ConAddShi (on the left side). We
the complete integer multiplier as shown by Fig.28
a. Both shr operators in each layer we serially connect from
to right, so that the adder overflow in producing intermediate products
P(1), P(2), etc. finds room in the neighbor CoBiGen
cell, which has been made available by the series of Y(1), Y(2),
etc. with shrinking word length.
Language features for recursive hardware descriptions are important ingredients for flexible support of generic description methods. The most compact and comprehensible textual recursive descriptions are obtained by using an extended functional notation, an alternative of the abutment expressions developed for KARL-3: slice expressions which are more mathematical and less topological. To derive floor plans from such descriptions it can easily be transformed back into the topology notation having been introduced above. The basic idea is the modeling vertically abutted functional cells (Fig.29) by nested functions. For example see the ABL diagram in Fig.29: abutment expression P @ Q will be replaced by nested function references P ( Q ( <operands> ) ). The make clause
will be converted into the ordinary functional expression, right of the ".=" connector in:
Fig. d illustrates the general scheme of layer to nested function conversion. Fig.29 b shows ABL diagram and make clause of a mixed layer / slice example. By conversion into a slice expression we obtain:
Slice expressions are based on the orthogonal flow convention shown in Fig.29 c: the "vertical" data flow through a sequence of layers is called main flow, the "horizontal" flow (e. g. ripple flow or control code distribution) is called serial flow. In slice expressions main flow is represented by parentheses, and serial flow is indicated by colons, like in (18). Multiple operands and multiple destinations are catenated by dots to fit to the slice expression, like in (18). The ABL diagram in Fig.29 e is expressed by the following slice expression:
With respect to implementation slice expressions
just a subset of the abutment expression implementation. In abutment
out, and bi are applicable to all
4 sides. In slice expressions "cells" have the following restrictions:
side may use out only, the back side in only,
by convention main flow always goes from back to front. Serial flow may
go left or right or both (see
Fig.29 c), so that at
and right all attributes are allowed: in,
RTcode is the executable form of KARL descriptions. RTcode is generated by the KARL compiler and is executed by KARL simulators (and other tools). RTcode has a bidirectional list structure which supports a wide variety of CAD algorithms. During the time of the CVT project RTcode has become an important interchange format used by more than a dozen different users. Fig.33 shows, how 7 non-KARL tools from different partners within the CVT project are integrated by means of a central RTcode interface such, that RTcode is a kind of design data base of a major part of the CVT software system. So RTcode is the backbone of an early CAD framework for VLSI design.
We distinguish simulation, test pattern
Most directly related to CHDLs are simulators - important CAD tools,
efficient than other kinds of simulators, are subject of section 5.1.
related to simulation is the area of testing. Section 5.2deals with
methods having been implemented for test pattern development and for
deriving functional test patterns from KARL descriptions, functional
from layout or from personality matrixes for verification purposes.
integrating simulation and test pattern development is an approach of
for testability. Section 5.3 deals with using KARL and ABLED and their
topology features for structured VLSI design within the framework of
CVT software package, as well as with high level synthesis and related
methods and their support by CHDL use. Section 5.4 points out some
experiences in commercial and academic chip designs and other practical
applications. More literature on all this is referenced in  Fig.32
and Fig.33 help to achieve a partial survey on
For KARL-1 only a single simulator implementation effort has been reported . Three simulator implementations have been reported for KARL-2   . From KARL-2 simulation experiences two example collections have been assembled . Three different simulators have also been implemented for KARL-3 . One of them, called SMART, is an event-driven simulator . Another of them is a fault simulator  (also see next section). For these KARL-3 simulators a physical model extension has been implemented , which organizes the cooperation of a tester (Tektronix DAS 9100 digital analyzer) running concurrently with the simulator. All these simulators accept code generated from a non-procedural hardware description language. However, also for procedural extensions of KARL-3, the languages CVS_BK and KARL-4 a simulator has been implemented .
This section deals with KARL-based software for generation and evaluation of test patterns as well as for design verification and its support by extraction of KARL descriptions from layout.
KARL use in Testing and Verification. Also verification and test pattern generation and validation may benefit from CHDL use. Two KARL-based systems have been implemented, the KARATE system   and the CVT test development environment   including a KARL-based fault simulator (a version of the CVT KARL-3 simulator) and an automatic fault extractor . Also an experimental KARL-based verifier has been implemented . For verification support the REX system has been implemented at Kaiserslautern for extracting KARL descriptions from layout .
KARATE (KARL Automatic Test Extractor) is an automatic test pattern generator for KARL3 Hardware Descriptions which was developed in 1988 ,. Unlike most test pattern generators which are based on the D-Algorithm    KARATE also supports test pattern generation for sequential register transfer level descriptions and may be therefore used for test pattern generation at the early phases of a design process. A build in testability analysis guides the designer in finding an easy testable architecture.
Two innovative features of KARATE elaborate it from a simple test pattern generator to a flexible test pattern environment. These are:
Explicit fault modeling means that KARATE's ATPG algorithm is independent of a specific fault model. Component test patterns specify tests for the unconnected hardware primitive. Different component test patterns libraries are provided for distinct fault models. Propagation properties of language primitives are specified in terms of functional patterns using symbolic functions.
The ATPG algorithm within KARATE consecutively
applies component test patterns to each primitive of a netlist using
test patterns of the other components to propagate values to the
ports of the netlist. This process is done by a least cost depth first
search algorithm with efficient heuristics to prune the search space
algorithm works hierarchically by generating functional patterns for
master of each component instance in a hierarchical design, hereby
test pattern generation time by exploiting the design hierarchy.
Functional Test Patterns. Conventional systems for automatic test pattern generation work on flat gate level Hardware Descriptions and are restricted to the “stuck-at” fault model. KARATE generates test pattern generation at RT-, logic and switch level which do not rely on a specific fault model . The hierachical test pattern generation process of KARATE allows support of DFT techniques like BIST or scan-path techniques. KARATE generates test pattern in various formats. Tester specific formats like EDIF200, SENTRY, Tektronix DAS 9100 and simulator activation languages SCIL and SCIL-3 . The KARATE system has a comfortable user interface for testability analysis, pattern generation and editors to create functional test patterns and component test patterns and for library management. KARATE is implemented in VAX/VMS-PASCAL and runs under VAX-VMS. Test pattern generation for RT level descriptions of medium complexity run within a few CPU seconds on a VAX 11-750.
CVT test development environment. Fig.32
gives an overview  of the CVT test environment which was developed
in cooperation with CSELT and Olivetti. This environment as well as its
main program are called TIGER (Test pattern Interactive Generator
at RT level) . The TIGER program is organized as a shell
around OFSKA and the KARL-3 system. But, in fact, TIGER is a test
generator using information provided by a testability analyzer OTAKA (Olivetti
based on KARL) , a fault simulator OFSKA (Olivetti
KARL)  (an interactive tool to evaluate fault coverage
of given test patterns, allowing fault models of the type stuck-at,
truth table change, function change), and FERT (Fault model Extractor
at RT level) , a fault extractor. A fault generator OFGKA (Olivetti
for nets described in KARL) supports OFSKA. FERT computes
models with injected faults and extracts these faults from layout
parasitics and a physical fault set. FERT accepts a SPICE-NDL-like
format and generates RTcode format  as input for TIGER. Like
TIGER is also independent of an underlying fault model. The system
more interaction by the user than KARATE but provides more support to
layout specific fault models. Fig.33 shows, how
above test pattern development system has been integrated into the CVT
CAD software environment. Note the central role of RTcode, the
form compiled by KARL compilers.
Verification and Register Transfer Extraction. The correctness of a design compared to its specification is generally validated by comparing the simulation runs of the register transfer specification and logic level simulation. The quality of this comparison is heavily dependent on the chosen set of stimuli patterns used for simulation. The Register Transfer Extractor REX and VERENA provide verification of a layout against its register transfer specification. REX reconstructs an RT-level description out of a previously extracted circuit netlist by graph matching. The algorithm finds an optimal matching of isomorphic subgraphs to a library of RT-level circuit netlists. VERENA  is then used to determine the functional equivalence of the extracted register transfer netlist and the specification. REX has been developed at University of Kaiserslautern. VERENA was developed at University of Passau.
A substantial amount of synergism may be
from integrating a CHDL into the design process . Several programs
have been implemented for deriving layout or minimizing logic from KARL
descriptions, deriving module generators form the KARL language, or,
KARL descriptions from high level specifications.
KARL-3 has been used in designing several
circuits at Kaiserslautern, which have been manufactured on multi
chips assembled by the multi university E.I.S. project. KARL has also
used in completion of some industrial IC designs   . For
KARL is used or has been used, respectively, at Kaiserslautern and
(e. g. ). One of the first uses of  in teaching has been by C.
Ramamoorthy at UC Berkeley. More references to KARL applications are
An ABL and KARL User Group ABAKUS has been organized by Karin Lemmert and Andrea Wodtko, which provided licenses, distributed manuals and other application support material (e. g. , ) and even an ABAKUS Newsletter, and organized workshops. The number of licensee institutions finally reached 93. The 1st ABAKUS workshop  in Passau (Germany, organized 1986 by Werner Grass, University of Passau) attracted 35 participants from 8 countries and the 2nd one  at Igls (Innsbruck, Austria, organized 1988 by Bernhard Quatember, University of Innsbruck) attracted 44 from 6 different countries. Exploitation of KARL-based developments has also been a subgoal of the CVT and CVS exploitation efforts . But commercially the final result is: VHDL is the winner.
Before VHDL had been widely spread, KARL has
well accepted and widely used, mainly in industrial and academic
but also for commercial applications. This is indicated by 93 licensees
(holding site licenses), the number of simulators having been
(see section 5.1), the number of RTcode users (more than a dozen), a
number of CAD tools related to KARL or somehow connected to KARL
(we do not know the exact number), the number of KARL dialects 
    and evaluations (   and others). This
would not have been possible without the massive funding received from
the Commission of the European Communities within CVT and CVS project
of the ESPRIT programme). At that time for VHDL only a slow Simulator
been available . The conclusion is, that in the eighties, Europe
been far ahead of the rest of the world (not only due to KARL, but also
other efforts (reported in this volume), like by the CONLAN group, the
CHDL-based hardware verification scene, and others. But finally all
efforts failed. What has been the reason for this? The European disease
(lack of competitiveness, hesitating in launching innovative products)?
The European IH (Invented Here: cannot be interesting -
spread view in European industry) effect (the inverse of the American
Here: cannot be interesting - view widely
spread among highest ranking US universities) effect)? "Because VHDL has
become a standard" (although KARL is a completely different thing)? Is
standard really better than no standard at all? However, in 1989 there was only a preliminary draft paper published
dealing with partial implementation. The standardization had only been
proposed by a heavily DoD-supported aggressive VHDL lobby.(P. S. on
2002: see fig. 34).
The KARL user group ABAKUS (see section 6) collected KARL-related literature (reports and publications), as well as literature with KARL-related references. This list  (available for free, contact the e-mail address: email@example.com), which has been regularly updated until about 1986 or 1987, includes 299 entries. Because of space limitations the following section shows only a part of such references.
KARL Parsers and Simulators.
Synthesis from KARL descriptions.
Verification and Extraction
ABL and KARL user group