. ‘ x; “Ca .152. . , Aug-5min“) .”

. ‘ . . . 3. .. r. ‘ 2 s u
. .. M. ‘

. x :07.

 

3.1.3:...
9...; .1.an r

 

211$.»
Iii-S
l .

ll :41.
5.5.0.) .3};

5...»:

5.2.5... :3...
.311 .x

I

 

 

 

, izﬁaili.-.»
.4. if . 5i;
. I Y:l'15\71|

.5»). vi?!

 

 

 

GSAN TA

IIUIJIIUIUHIHIIIHHWIINIIIUlllllIHIHIIIHIHHHI

31293 00591 3045

 

 

 

 

 

LIBRARY
Michigan State
University

 

 

 

This is to certify that the

thesis entitled

Modeling Artificial Neural Networks
Using VHDL

presented by

Keshavachandra, C.K.

has been accepted towards fulfillment
of the requirements for

 

 

Master's degree: in Electrical
Engineering

mat/7 zW

Major professor

 

Date ”Vt/f. 9; /990

O-7639 MS U is an Afﬁrmative Action/Equal Opportunity Institution

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.

ﬁ

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

MSU Is An Affirmative Action/Equal Opportunity Institution

MODELING ARTIFICIAL NEURAL NETWORKS
USING
VHDL

By

Keshavachandra, C.K.

A THESIS

Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of

MASTER OF SCIENCE

Department of Electrical Engineering

1990

ABSTRACT

MODELING ARTIFICIAL NEURAL NETWORKS
USING
VHDL

By

Keshavachandra, C.K.

This thesis describes an Artiﬁcial Neural Network (ANN) ceprocessor modeled
behaviorally using VHSIC Hardware Description Language (VHDL).

There has been renewed interest in the area of ANN of late. Everyday new ANN models
for new domains are being suggested. There is however a dearth of equal progress in this ﬁeld as
far as hardware implementation is concerned. This is partially due to limitations posed by the
current technology and it’s orientation towards traditional VonNeuman architectures. It is a logical
step to adopt VHDL as the design test bench for behavioral modeling of Artiﬁcial Neural Networks
considering the fact that VHDL is gaining ground as the standard design test bench for hardware
design. It is fast becoming the industry standard for hardware design, simulation and exchange.

One such system modeled in VHDL is described in this report. Even though the system is
aimed at solving dynamic programming problems, it is designed such that any similar ANN can be
modeled using it The design structure facilitates easy modiﬁcation in order to incorporate new

features, such as learning, and different models for a neuron. This coprocessor can be used to test

any ANN model and the corresponding energy function.

TABLE OF CONTENTS

LIST OF FIGURES

LIST OF TABLES

I.

INTRODUCI'ION

1.1 Introduction

1.2 Objective

VHDL

2.1 Introduction
2.2 Factors Inﬂuencing the Development of VHDL
2.3 The Language
2.3.1 Design Entities
2.3.2 Interface Description
2.3.3 Body Description.
2.4 Impact of VHDL

2.5 Suitability of VHDL for ANN Implementations

DYNAMIC PROGRAMMING

3.1 Introduction
3.2 Stagecoach Problem

3.3 Solution to the Stagecoach Problem

ARTIFICIAL NEURAL NETWORKS

4.1 Introduction
4.2 Hopﬁeld - Tank Networks

4.3 Traveling Salesman Problem

iii

vi

10

12
12

13

16
17

20

4.4 An ANN for Solving Dynamic Programming Problems

4.5 An ANN Model for the Stagecoach Problem

NEURAL COPROCESSOR: A BEHAVIORAL MODEL

5.1 Introduction
5.2 Design Methodology
5.3 Design
5.3.1 Network
5.3.2 Neurons
5.3.3 Memory
5.3.4 Convergence Sensor
5.3.5 Register Set
5.3.5 Auxiliary Components

5.4 Simulating the Stagecoach Problem

POST-SIMULATION ANALYSIS

6.1 Introduction
6.2 Results and an Analysis
6.3 Possible Reasons for the Observed Behavior

6.4 An Extended Problem

CONCLUSION

7.1 Conclusion

7.2 Future Research
APPENDIX 1
APPENDIX 11

BIBLIOGRAPHY

iv

23
26

28
29
3o
31
32
34
35
35
36
39

42

42

45

48
48
so
56
63

LIST OF FIGURES

Figure 2.1. Interface description of an entity.

Figure 2.2. Different architectural bodies for the same entity ﬁrll adder.

Figure 3.1. The road system for the stagecoach problem.

Figure 4.1. Hopﬁeld - Tank network.

Figure 4.2. Transfer function of a neuron.

Figure 4.3. An example of a 10 - city travelling salesman problem.

Figure 4.4. A 3x6 dynamic programming problem.

Figure 4.5. An ANN model for the stagecoach problem.

Figure 5.1. The ANN coprocessor.

Figure 5 .2. Top level schematic diagram of the system.

Figure 5 .3. Composition of the network for a case of 5 stages with 3 states per stage.
Figure 5 .4. VHDL code implementing the network.

Figure 5.5. Schematic of a neuron and the corresponding VHDL code.

Figure 5.6. VHDL code implementing the memory.

Figure 5.7. VHDL code to implement the convergence sensor.

Figure 5.8. VHDL code for the Neural_Package.

Figure 5 .8. VHDL code implementing the neural coprocessor.

Figure 5.9 VHDL code implementing the test bench.

Figure 5.10. The interconnection weight — matrix for solving the stagecoach problem.
Figure 5.11. The ANN for the stagecoach problem.

Figure 6.1. The ANN for the extended stagecoach problem.

Figure 6.2 The modiﬁed package declaration for solving the extended stageoach problem.

Figure 6.3. The modiﬁed test bench for solving the extended stagecoach problem.

Figure 6.4. The interconnection weight - matrix for solving the extended stagecoach problem.

13
17
18
20
23
27
29
30
31
32
33
34
35
36
37
39
40
41
45
46
46
46

LIST OF TABLES

Table 3.1. The cost for the standard policy on the stagecoach run from state i to state j. 14
Table 6.1. Simulation results for the stagecoach problem. 43

Table 6.2. Simulation results for the extended stagecoach problem. 47

vi

Cﬁapter 1

Introduction

1.1 Introduction

The past few years have witnessed an increased interest in the area of Artiﬁcial Neural
Networks (ANN) [1]. Research in this ﬁeld, although started in early 60s, could not proceed at the
desired pace due to the limitations posed by available technology. The phenomenal advances in the
ﬁelds of computer engineering and IC engineering have given a fresh impetus to this ﬁeld. These
technological leaps have also Opened up a myriad applications for Artiﬁcial Neural Nets [2, 3].

In spite of these factors, research in this area is still impeded by the fact that there is no
standard hardware testbench to test new designs. Simulation and veriﬁcation of most of the
networks suggested are done on traditional computers in software. Designing and fabricating
hardware that can be used for research is still prohibitively expensive. This problem, when
considered with an academic setup in perspective, appears to be one of the bottlenecks in ANN
research.

Another notable development of the past few years is the emergence of Design Automation
(DA) tools, and Hardware Description Languages [4]. VHSIC Hardware Description Language
(VHDL) is fast becoming an industry standard for hardware design and exchange [5]. The merits

of using such a language for hardware design and veriﬁcation are explained in Chapter 2. Apart
l

2

from the immediate advantage of using an emerging standard for hardware design, VHDL provides
an economical alternative for hardware design and veriﬁcation. A premise of this work is that ANN
research, impeded by the huge cost required for physical implementation, will ﬁnd VHDL ideal for
modeling and veriﬁcation. Using this approach the actual implementation of these networks can be

separated from much of the research effort.

1.2 Objective

This thesis is an effort in demonstrating VHDL as a viable design test bench for ANN
research. A conscious decision was taken to develop a general purpose ANN coprocessor in VHDL,
even though the primary objective was to model a neural network in VHDL capable of solving
dynamic programming problems. The system is designed as a “coprocessor” similar to a math
coprocessor in the sense that it receives data from the CPU and retums the solution or sends a signal
that it could not converge to a solution within the predeﬁned accuracy. This system can be used to
test any similar network without major changes by describing the size of the network (in terms of
the number of stages and the number of states in each stage) and providing the initial conditions (the
weights on the links in the network). The design is also kept ﬂexible enough for incorporation of
additional features such as learning. One can use subcomponents of the present system in an
alternative design without much eﬂort. Essentially, this is a skeletal system that can be enhanced

and used for simulation and veriﬁcation of many types of Artiﬁcial Neural Networks.

C ﬁapter 2

’VHQDL

2.1 Introduction

Early in the Department of Defence (DoD) Very High Speed Integrated Circuits (VHSIC)
program, a need was felt for a standard medium of expression to communicate the massive amounts
of design data associated with device designs of the desired scale and complexity. VHSIC Hardware
Description Language (VHDL) is the outcome of efforts in this direction [6]. It is fast becoming
industry standard for hardware design and exchange [5].

In the present day hardware design environment, where DA tools are used virtually in all
phases of design cycle, hardware description languages are crucial to the design and test of
hardware. They allow incremental development of designs, store design data, and communicate
those data between various design activities. VHDL marks the ﬁrst coordinated eﬁort to develop a

common hardware description language, that is being recognized as an industry standard [7].

2.2 Factors Inﬂuencing the Development of VHDL

Improving the documentation of electronic systems: Government electronic systems

require stringent documentation because they have long life cycles and are deployed around the

world. Maintaining and upgrading electronic systems while they are an active part of the inventory

4

requires detailed, up-to—date, and accurate documentation. Hence there was a need for a precise
hardware description language.

Since VHDL can serve as a design automation tool interface, it can document the electronic
system during (instead of after) the design process. Therefore, VHDL more accurately reﬂects a
system’s true properties and characteristics.

Decreasing system design time and cost: There is a need for a signiﬁcant number of custom
ICs to meet performance, reliability, and classiﬁcation requirements that off-the—shelf ICs won’t
satisfy. Already in the $2 to $5 million range, development costs of advanced ICs must be reduced
to economically meet future IC demands[6]. VHDL can reduce IC development time and expense
by promoting repeated use of previous design investments, and by providing a vehicle for more
efﬁcient management of the design process among individual designers or organizations.

When considering the development of large electronic systems, the paradigm of design as
an iterative process building new designs upon past designs is quite powerful. Similarities between
this process and human learning provide a conceptual basis for knowledge-based design tools that
improve with use. In addition, some business analysts forecast that a “redesign era” will emerge to
fuel the next major semiconductor market, and that equipment manufacturers will upgrade their
products to take advantage of VLSI technology[6].

By allowing for parameterized generic design components, VHDL simpliﬁes the reuse of
designs. Once a generic component has been designed, it can be reused by instantiating its
parameters with values meeting givenapplication requirements - a feature signiﬁcantly reducing
resources expended in complex electronic system development.

By providing many features to assist in design management and documentation by
conﬁguration control, VHDL helps to establish more structured policies and procedures for
deve10ping electronic systems. Similar to the speciﬁcation and body concept in Ada, VHDL allows
designers to deﬁne speciﬁcations representing design component interfaces separately from several
associated bodies representing alternative component implementations. Use of the interface and

associated bodies enables VHDL to support conﬁguration management of top-down and bottom-up

5

design methodologies. In addition, VHDL supports packages, this allows managers to establish
common naming conventions, data types and convenient functions among designers by

encapsulating descriptions with VHDL packages.

2.3 The Language

VHDL provides a standard textual means of description for hardware components at
abstraction levels ranging ﬁom the logic gate level to the digital system level. It provides precise
syntax and semantics for these hardware components, enabling design transfer both within and
among organizations. The language is designed to be efﬁciently simulated and natural for hardware
designers. In addition, it allows designers to represent information outside the primary range of
language coverage.

Some of the building blocks and abstractions of the language are explained below. This

section has been written with extensive reference to the paper by JD. Nash and LP. Saunders [7].

2.3.1 Design Entities: A design entity models hardware of any complexity. For example, it may
model a logic gate, a ﬂip-ﬂop, a RAM or a computer system. A design entity is composed of an
interface and one or more alternative bodies. The interface contains a set of deﬁnitions common to
alternative bodies. The hardware entity’s external view and specify communication channels
between the design entity and the outside world are captured in such deﬁnitions. The entity’s
operating characteristics and conditions may also be described as part of its interface’s deﬁnition.
Each alternative body describes an altemative view of the hardware entity. For example, one body
may describe a hardware entity’s behavior while another body may describe its structure,
decomposing the entity in terms of its subcomponent interconnections; a third body may model the
entity’s Operations in terms of register-transfer microoperatons. There are no restrictions on the
number of ways designers can view hardware entities. Altemative structural implementations of the
same hardware entity can be modeled so as to enable evaluation of cost and speed factors. Similarly,

both functional and physical structures of a hardware entity can be modeled. Each alternative body

 

6

is associated with the same interface and can make use of all deﬁnitions supplied in the interface.

2.3.2 Interface Description: A design entity’s interface contains information common to its
alternative bodies. A subset of this information (namely, the speciﬁcation of ports and generics) is
externally visible. When a design entity is used as a subcomponent in a higher level design entity,
its interface must conform to that of the subcomponent. Extemally visible interface information is
used for such consistency checks.

Ports deﬁne communication channels between design entities and the outside world. A port
deﬁnition involves description of its mode and type. The port’s mode speciﬁes the direction of
infomration ﬂow through the port. A port can be of mode in, out, irrout or buffer. A port type
Speciﬁes the set of values a port may assume. Port values may be represented by voltage levels, truth
values, binary digits, or multiple logic values. Each of these sets is a type, and each may be an
abstraction of the same underlying electrical phenomenon.

A design entity interface may also deﬁne generics. Such a design entity deﬁnes a class of
components. When used, a generic design entity is particularized to select one component in the
class. To particularize a generic design entity, desired values are supplied for corresponding
generics. Generics increase a design entity’s reusability. For example, technology dependencies
such as noise margins or power consumption may be captured in generics. When design entities are
used, a particular technology may be speciﬁed by supplying the necessary generic values. An

example is given in Figure 2.1.

2.2.3 Body Descriptions: VHDL provides two body description types: architectural bodies and
conﬁguration bodies. Architectural bodies describe how the input and output ports of a design entity
relate, either by expressing the involved input/output data transformation or by connecting those
ports to subcomponents. Such predominantly local information pertains to one design hierarchy
level. On the other hand, a conﬁguration body contains global information such as which design

entities model subcomponents used in an architectural body or how global signals are distributed.

 

entlty Ful|_Adder ls

generlc ( Time_Delay : TIME );

port ( X,Y,Cin :IN Bit; Cout,Sum: OUT Bit);
end Fu|I_Adder;

 

 

 

Figure 2.1. Interface description of an entity.

There are three styles of description within an architectural body: structural, dataﬂow, and
behavioral. Structural descriptions capture the schematic view of hardware and consist primarily of
interconnected components. Dataﬂow descriptions, a little more abstract, specify data transforms
being performed in terms of concurrently executing RTL statements. Behavioral descriptions, the
most abstract, specify data transforms in terms of algorithms for computing output responses to
input changes.

A given architectural body may make use of any combination of these styles of
descriptions, for they are all deﬁned under a common set of semantics. Together, these features
support most hardware design styles. An example is given in Figure 2.2.

Component instances in structural descriptions are placeholders for behavioral information
speciﬁed as separately described design entities. In the absence of contrary information, we assume
a separate design entity to have the same characteristics as the component being instantiated (the
same name, for example, plus ports and generics with the same names, types, and compatible
modes). Thus, if a design is being created bottom-up and the user wants to declare a Component
whose instances exhibit a given behavior, he need only copy the name, port declarations, and
generic declarations of an existing design entity exhibiting the required behavior. Similarly, if a
design is being created top-down and the user wants to deﬁne a design entity that implements the
behavior required for a given component, he need only copy the name, port declarations, and

generic declarations from that component’s declaration to create the design entity’s interface

 

 

 

description.
ﬂBehavioral model of a Full Adder \ -- Structural model of a Full Adder \
architecture behavior of Full_Adder is architecture structure of Full_Adder is
begin
Process(A, B, Cin) Component Half_Adder
begin port (I1,l2:in Bit;S,C:out Bit);
Sum <- ( A xor B xor Cin ) after Trme_Delay; and component;
Cout<-(AandB)or(BandCin)or
( Gin and A) after Time_Delay; Component Or_Gate
and process; port (I1,l2:in Bit;O:out Bit);
and behavior; and component;

Signal 61 ,C1 ,CZ:Bit;

begin
X1 : Hall_Adder port map (X,Y,S1,C1);
X2: Hali_Adder port map (81 ,Cin,Sum,CZ);
X3: Or_Gate port map (C1,CZ,Cout);

end My_Full_Adder;

k J\ j

 

 

 

 

 

 

 

Figure 2.2. Diﬂ’erent architectural bodies for the same entity Full Adder.

Conﬁguration speciﬁcations provide the ability to override default association rules so that
an architectural body’s component instances may be bound to similar but not identical design
entities. The names and port types may be different, in which case the conﬁguration speciﬁcation
must identify appropriate type conversion functions. Moreover, additional signals may be
connected to formal design entity ports that do not correspond to ports of the component.

Although conﬁguration speciﬁcations may appear in either architectural or conﬁguration
bodies, they become most useful in the latter. A conﬁguration body of a given design entity relates
to an architectural body of the same entity; it’s conﬁguration speciﬁcations relate to it’s component

instances.

2.4 Impact of VHDL

The steadily increasing level of integration has motivated a growing emphasis on design

automation and semicustom/custom ICs. The dependency of continued growth of the

 

 

9

semiconductor industry and the nature of the IC market on the maturation rate of design automation
and semicustom/custom technology, which in turn depend mainly on standardization and legal
copyright protection, indicate that not everything can be or should be standardized. However, the
lack of appropriate standards to guide and focus the growth of a technology can foster costly and
burdensome diversity. Hence, there is a need for design, test, and manufacturing standards to
establish interoperability and required interfaces. VHDL aims at ﬁlling this void.

As the electronic design process becomes increasingly dependent on automation tools, IC
designing ﬁrms will develop proprietary tools to maintain a competitive edge. Many companies
won’t depend completely on closed and inﬂexible vendor design automation systems. On the other
hand, most companies cannot attract the expertise or aﬂord the sizable resources required to
develop their own custom design automation systems.

While existing CAB environments provide excellent capabilities in specialized areas, in
general they do not contribute to custom design automation system integration. By making these
CAE environments provide interfaces with a standard such as VHDL, design exchange and CAE
environment interoperability can be realized.

As the sophistication of the DA Tools being used is increasing, and as VHDL is fast
becoming an industry standard for hardware design and exchange, many CAD vendors are coming
out with compilers which translate the structural design in VHDL to an intermediate format, such
as CIF or EDIF, with which an IC can be fabricated. Although the current versions can accomplish
this only when the design is atleast at the Register Transfer Level (RTL), there are signs of VHDL
growing into a full ﬂedged Silicon Compiler - any hardware designer’s dream.

As IC complexity increases, circuits become more specialized and their broad applicability
decreases. It is estimated that about half the total IC market would be custom and semicustom ICs,
by 1991 [6]. In this scenario, VHDL can play a major role in providing a clearly deﬁned interface
to customers of varying experience and sophistication to shorten development cycles, reduce costs,
and avoid expensive legal proceedings resulting ﬁom design speciﬁcation misunderstandings

between vendor and customer. It can provide an elegant user documentation method for the difﬁcult

10

task of documenting custom/ semicustom designs. Another interesting offshoot is the phenomenon
of design second sourcing.

Historically, design has been an art rather than a science. Starting with sometimes vague
and incomplete speciﬁcations, designers go through an iterative series of transformations until
systems can be built within given technologies - or until it is clear that intended functional behavior,
performance goals, or design constraints are not feasible. There is a need for a top—down design
approach, with all the speciﬁcations available at the outset and then trying to implement it
physically. It translates to having a behavioral description of a system at the beginning and then
implementing it structurally, in the VHDL design paradigm. Thus, VHDL can play in important role
in advancing electronic system design the above stages to form a science of design by providing a
economical vehicle to do the same.

VHDL has a crucial role to play in an academic environment in terms of educational value,
propagating a science of design, and as an economical hardware design test bench. VHDL serves
as a vehicle for investigating new approaches to design techniques, models, and automation in areas
such as test, synthesis, and simulation. Knowledge about hardware properties and characteristics
applicable to design is the very essence of language constructs comprising VHDL. A system can be
ﬁrst modeled behaviorally, verifying the correctness of the design, then modeled structurally testing
the feasibility of hardware realization by incorporating the current technology constraints into the

design.

2.5 Suitability of VHDL for ANN Implementations

In order to test various theories and hypotheses propounded in the ﬁeld of Artiﬁcial Neural
Networks, a “true” neural network is needed rather than a software simulation. ICs must be
fabricated with “neurons” and interconnections built-in. (In the cases of programmable
interconnections, the size of the network is dictated by the connectivity). Some of the major
impediments to this are: 1) It is still with an empirical knowledge that a neuron has to be modeled;

2) Costs involved are enormous which is especially critical, considering that major portion of

 

11

current research is being done in Universities; and 3) These ICs cannot be used to model different
networks of realistic size, since a generic network would require complete connectivity with ways
of programming the inter-neuron links.

VHDL merits a closer examination as an alternative for ANN implementations just by the
fact that it is an economical and viable alternative. There is no incremental cost involved in
modeling different networks; it can be made as close to hardware implementation as desired as
against software approach. Limitations imposed by the existing technology can be circumvented by
using VHDL. One need not get lost in problems such as connectivity, die-size, etc. Research effort
will be directed at solving the real problem on hand. These limitations can be looked into when the
system is designed, tested and is ready to be used.

When VHDL is used as the implementation tool for ANN implementations, the research
will have a cumulative effect as the design can be exchanged with out any problem. Earlier designs
can be modiﬁed to suit the current needs, a bigger system can be built upon those developed earlier.
This provides a language to the research community in which theories can be propounded, tested.
challenged and veriﬁed.

With the idea of VHDL growing into a silicon compiler gaining currency, the ANN
community would be one of the prime beneﬁciaries by using VHDL for their designs. It does not
appear too far-fetched to imagine having a ANN chip fabricated directly after it is modeled and

tested in VHDL.

 

Chapter 3

@ynamic Trogramming

3.1 Introduction

Dynamic programming is a useful mathematical technique for making a sequence of
interrelated decisions. It provides a systematic procedure for determining the combination of
decisions that maximizes overall effectiveness.

Dynamic programming is a general type of approach to problem solving; the particular
equations used must be developed to ﬁt each individual situation. There does not exist a standard
mathematical forrnulaﬁon of “the” dynamic programming problem.Therefore, a certain degree of
ingenuity and insight into the general structure of dynamic programming problems is required to
recognize when problem can be solved by dynamic programming procedures and how it can be

done.

3.2 Stagecoach Problem

This chapter is with extensive reference to the book by Hillier and Lieberman [8]
The stagecoach problem is an example especially constructed to illustrate the features and
to introduce the terminology of dynamic programming. It concerns a mythical salesman who had

to travel west by stagecoach about 125 years ago when there was a serious danger of attack by

12

13

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10

 

 

 

 

 

 

 

 

 

 

 

 

 

\
\ /

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 3.1. The road system for the stagecoach problem.

marauders. Although his starting point and destination were ﬁxed, he had considerable choice as to
which state (or territories that subsequently became states) to travel through en route. The possible
routes are shown in Figure 3.1, where each state is represented by a numbered block. Thus four
stagecoach runs(stages) were required to travel from his point of embarkation in state 1 to his
destination in state 10.

This salesman was a prudent man who was quite concemed about his safety. After some
thought, he came up with a rather clever way of determining the safest route. Life insurance policies
were offered to stagecoach passengers. Because the cost of the policy for taking any given
stagecoach run was based on a careful evaluation of the safety of that run, the safest route should
be the one with the cheapest total life insurance policy. The cost for the standard policy on the
stagecoach run from state i to state j, which will be denoted by egj, is as shown in Table 3.1.The

objective now is to ﬁnd the route that minimizes the total cost of the policy.

3.3 Solution to the Stagecoach Problem

First note that the shortsighted approach of selecting the cheapest mn oﬂered by each suc-

cessive stage may not yield an overall optimal decision. Following this strategy would give the

14

Table 3.1. The cost for the standard policy on the stagecoach run from state i to state j.

 

 

 

 

 

 

5 6 7 _8_.9_

27 4 1 4
+234 6 5__ 8-
1l2|4|3| 3324 663 I
—— 94

4415 733

 

 

 

 

 

 

 

 

 

 

 

route 1 - 2 - 6 - 9 - 10 at a total cost of 13. However, sacriﬁcing a little on one stage may permit
greater savings thereafter. For example, 1 - 4 - 6 is cheaper overall than 1 - 2 - 6. One possible ap-
proach to solving this problem is to use trial and error. However, the number of possible routes is
large and having to calculate the total cost for each route is not an appealing task.

Dynamic programming provides a solution with much less effort than exhaustive enumer-
ation. The computational savings are enormous for larger versions of this problem. Dynamic
programming starts with a small portion of the original problem and ﬁnds the optimal solution for
this smaller problem. It then gradually enlarges the problem, ﬁnding the current optimal solution
from the preceding one, until the original problem is solved in its entirety. For the stagecoach
problem, we start with the smaller problem where the salesman has nearly completed his journey
and has only one more stage (stagecoach run) to go. The obvious optimal solution for this smaller
problem is to go from his current state (whatever it is) to his ultimate destination (state 10). At each
subsequent iteration, the problem is enlarged by increasing by one the number of stages left to go
to complete the journey. For this enlarged problem, the optimal solution for where to go next from
each possible state can be found relatively easily from the results obtained at the preceding iteration.

Let the decision variables xn where n = 1.2.3.4 be the immediate destination on stage n (the
nth stagecoach run to be taken). Thus the route selected is l - x1 - x2 - X3 - x4 where x4 = 10. Let
fn(s,x,,) be the total cost of the best overall policy for the remaining stages, given that the salesman
is in state s ready to start stage n and selects 1:1‘ as the immediate destination. Given s and n, let x;

denote the value of xn that minimims fn(s,xn), and let fn.(s) be the corresponding minimum value.

 

15

Thus
rn’(s) = min fn(s,xn) = rn(s,xn’),
= C3sxn + fn+1 . (x11).
where the value of csxn is given by the preceding tables for cij by setting i = s (the current state) and
j = xn (the immediate destination). Because the ultimate destination (state 10) is reached at the end
of stage 4, f5*(10) = 0. The objective is to ﬁnd f1‘(1) and the corresponding route. Dynamic
programming ﬁnds it by successively ﬁnding f4‘(s), f3*(s), f2'(s) for each of the possible states 8

and then using f2*(s) to solve for f1‘(s).

By solving the stagecoach problem using the above algorithm, the optimal routes are found to be
1 - 3 - 5 - 8 - 10
1 - 4 - 5 - 8 - 10
1-4-6-9-10

They all yield a total cost of f1‘(l) = 11.

Cﬁapter 4

ﬂirtiﬁcid Mound Ne tworﬁs

4.1 Introduction

Conventional digital computers are extremely good at executing sequences of instructions
that have been precisely formulated for them, with the “stored program” representing the processing
steps that need to be done. The human brain, on the other hand, performs well at such tasks as
vision, speech, information retrieval, and complex spatial and temporal pattern recognition in the
presence of noisy and distorted data - tasks that are very diﬂicult for sequential digital computers to
do. The brain accomplishes this, even though its “processing elements” (neurons) are signiﬁcantly
slower than the processing elements of contemporary supercomputers. In fact neurons, which are
electrochemical devices, can reSpond in milliseconds, whereas current, off-the-shelf electronic
technology can switch states in nanoseconds.

Current estimates place the number of neurons in the human brain at 10“[9]. They are
organized in a complex, unknown interconnection structure, and an individual neuron may be
connected to several thousand other neurons. There has been considerable research going on for
quite some time to understand how such a network (biological neural network) is capable of storing
data like images, smell, sensations and thoughts, allowing us to represent, retrieve and manipulate

these data. There has been a concerted effort to duplicate such a network at different abstraction

16

17

levels, creating what has come to be known as an Artiﬁcial Neural Network (ANN).

4.2 Hopﬁeld - Tank Networks

Many logical problems arising ﬁom real world situations can be formulated as optimization
problems. It can be described as a qualitative search for the best solution. In their landmark paper,
J .J .Hopﬁeld and D. W. Tank proposed a network topology, that has come to be known as Hopﬁeld-
Tank network. The Hopﬁeld - Tank network consists highly-interconnected nonlinear analog
neurons that can be used for solving Optimization problems[1]. These networks can rapidly provide
a collectively-computed solution (a digital output) to a problem on the basis Of analog input
information. The problems tO be solved must be formulated in terms Of desired Optima, Often subject
tO constraints.

The general structure Of the analog computational networks which can solve Optimization
problems, as suggested by Hopﬁeld and Tank is shown in Figure 4.1. These networks have the three
major forms Of parallel organization found in neural systems: parallel input channels, parallel
output channels, and a large interconnectivity between the neural processing elements. The

processing elements (neurons) are modeled as ampliﬁers in conjunction with feedback circuits

Inputs

.7 \3.
* 1

ECU? 'jj‘lmje

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J —
. I . R .
v Ampliﬁer A1333? . ineI'z-jiroe'twork

Figure 4.1. Hopﬁeld - Tank Network.

 

 

18

 

V = 801)

 

 

 

 

0 0
u

Figure 4.2. Transfer function of a neuron.

comprised Of wires, resistors and capacitors organized so as to model the most basic computational
features of neurons, namely axons, dendrites, and synapses connecting the different neurons.

The ampliﬁers have sigmoid monotonic input-output relations, as shown in Figure 4.2. The
function V]- = gj(uj) which characterizes this input-output relation describes the output voltage Of
ampliﬁer V,- due to an input voltage uj. The time constants Of the ampliﬁers are assumed negligible.
However, like the input impedance caused by the cell membrane in a biological neuron, each
ampliﬁer j has an input resistor p ,- leading tO a reference ground and an input capacitor C}. These
components partially deﬁne the time constants of the neuronsand provide for integrau've analog
summation Of the synaptic input currents from other neurons in the network. In order to facilitate
both excitatory and inhibitory synaptic connections between neurons while using conventional
electrical components, each ampliﬁer is given two outputs, a normal (+) output and inverted (-)
output. The minimum and maximum Outputs Of the normal ampliﬁer are taken as O and 1, while the
inverted output has corresponding values Of O and -l.

A synapse between two neurons is deﬁned by a conductance Ti}- which connects one of the
two outputs Of ampliﬁer j to the input Of ampliﬁer i. This connection is made with a resistor Of value
R5 = l/IT,-ll. If the synapse is excitatory (Til > 0), this resistor is connected to the normal (+) output

Of ampliﬁer j. For an inhibitory synapse (Til- < 0), it is connected to the inverted (-) output of

 

19

ampliﬁer j. The matrix T3,- deﬁnes the connectivity among the neurons. The net input current to any
neuron i (and hence the input voltage u,-) is the sum Of the currents ﬂowing through the set Of
resistors connecting its input to the outputs Of the Other neurons. Thus the normal and inverted
output for each neuron allow for the construction Of both excitatory and inhibitory connections
using normal (positive valued) resistors; biological neurons do not require a normal and inverted
output since exicitatory and inhibitory synapses are deﬁned by use Of diﬁerent receptor/ton channel
combinations.

As indicated in Figure 4.1, these circuits include an externally supplied input current 1,- for
each neuron. These inputs can be used to set the general level Of excitability Of the network through
constant biases, which effectively shift the input-output relation along the u,- axis, or to provide
direct parallel input to drive speciﬁc neurons.

Although this “neural” computational circuit is described here in terms Of ampliﬁers,
resistors, capacitors, etc., it has been shown that networks Of neurons whose output consists Of
action potentials and with connections modeled after biological excitatory and inhibitory synapses

could compute in a similar fashion to this conventional electronic hardware [1].
The equation Of motion describing the time evolution Of this circuit is
ngui/dt) = Eﬁjl/j-uglRi-r-Ii.
I/R;=I/p,~+2T,-j,
and Vi = 81M).
where g,- is commonly a monotonically increasing sigmoid function.

The main task in solving a problem using an ANN is ﬁnding an energy function

corresponding to the problem at hand, whose minima correspond to the solution tO the problem. The

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

20
Eitu bun
. .E J
.O I? m
" II no
.. ’5
Hc ' "
A or
City Map An Optimal Path

 

 

 

Figure 4.3. An example of a 10 - city TSP.
minima of the energy function can be found by using the above network.

4.3 Traveling Salesman Problem

In order to explain the ideas developed in the previous section, the Traveling Salesman
Problem (TSP) is discussed below, explaining how it can be solved using a network similar to the
one described in the previous section[l].

The TSP is a classic example of a difﬁcult Optimization problem. A set of n cities A, B, C,
have (pairwise) distances Of separation dAB, dAc. ..... , dBc, The problem is to ﬁnd a closed
tour which visits each city once, returns to the starting city, and has a short (or minimum) total path
length. A tour deﬁnes some sequence B, F, E, G, , W in which the cities are visited, and the total
path length d Of this tour is

d=dBF+dFE+dEG+ ..... +dw3.

The actual best solution to a TSP problem is computationally very hard - the problem is np-

 

21

complete, and the time required to solve this problem on any given computer grows exponentially
with number Of cities. An example of a lO-city TSP is given in Figure 4.3.

The solution to the n-city TSP problem consists of an ordered list of 11 cities, Tb “map” this
problem onto the computatiOnal network, a representation scheme which allows the digital output
states of the neurons Operating in the high - gain limit to be decoded into this list, is needed. Hopﬁeld
and Tank have chosen a representation scheme in which the ﬁnal location of any individual city is
speciﬁed by the output states of a set of n neurons. For example, for a lO-city problem, if city A is
in position 6 of the tour which is the solution to the problem, then this is represented by the sixth
neuron out of a set often having an output with all other outputs at 0.

This representation scheme is natural, since any individual city can be in any one Of the 11
positions in the tour list. For 11 cities, a total of n independent sets Of n neurons are needed to
represent a complete tour. This is a total of N =n2 neurons. The output state of these 112 neurons
which we will use in the TSP computational network is most conveniently displayed as an n x 11
square array. Thus, for a S-city problem using a total Of 25 neurons, the neuronal state is shown in
Figure 4.3 would represent a tour in which city C is the ﬁrst city to be visited, A the second, E the
third, etc. (The total length of the 5—city path is dCA + d AE + dEB + dBD + dDC). Each such ﬁnal state
of the array of outputs describes a particular tour of the cities. Any city cannot be in more than one
position in a valid tour (solution) and also there can be only one city at any position. In the n x n
“square” representation this means that in an output state describing a valid tour there can be only
one “1” output in each row and each column, all other entries being zero. Likewise, any such array
of output values, called a permutation matrix can be decoded to obtain a tour (solution).

To enable the N neurons in the TSP network to compute a solution to the problem, the
network must be described by an energy function in which the lowest energy state (the most stable
state of the network) corresponds to the best path. This can be separated into two requirements.
First, the energy function must favor strongly stable states Of the form of a permutation matrix,
rather than more general states. Second, of the n! such solutions, all of which. correspond to valid

tours, it must favor those representing short paths. An appropriate form for this function can be

22

found by considering the high gain limit, in which all ﬁnal normal (+) outputs will be 0 or 1. The
space over which the energy function is minimized in this limit is the 2Ncomers of the N-

dimensional hypercube deﬁned by V,- = 0 or 1. A suitable energy function would be
E = A/ 2 2X Z 2 VXIVXJ+

ijuu‘

3/2 2 2 2,16:sz

iXX-t
C/2(>:>:VX,.-n)2+
X i

D/2 2 2 2 dXYVXi(VY,i+I + VYJ-I )

X Y ex 1'
where A, B, C and D are positive.

The ﬁrst triple sum is zero if and only if each city row X contains no more than one "’,‘1 the
rest of the entries being zero. The second triple sum is zero if and only if each “position in tour”
column contains no more than one “1” the rest of the entries being zero. The third term is zero if
and only if there are n entries of “l” in the entire matrix. Thus, this energy function evaluated on
the domain of the comers of the hypercube has minima with 13:0 for all state matrices with one “1”
in each row and column. All other states have higher energy. Hence, including these terms in an
energy function describing a TSP network strongly favors stable states which are at least valid tours
in the TSP problem and, and fulﬁlls the ﬁrst requirement for E. The last term in the above equation
fulﬁlls the second requirement, that E favor valid tours representing short paths. This term contains
information about the length Of the path corresponding to a given tour.

From the above energy ﬁmction, one can deduce the implicitly deﬁned connection matrix,

which is given by:
rxm = - A 5xy(1-51j)
' B 511' (1 ' 5201)
- C
' D dxﬂ 8j,i+1 + 8j,i-1 )

where Oij = 1 ifi =j and is 0 Otherwise.

 

23

This model of TSP has been simulated and veriﬁed to yield “reasonably optimal" soluu'on

to the TSP[1].

4.4 An ANN for Solving Dynamic Programming Problems

As discussed in the previous chapter, traditional dynamic programming is a computational
technique which makes a sequence of decisions to deﬁne an Optimal policy and path based on the
principle of optimality. The conventional algorithm begins by ﬁnding the Optimal path for the last
stage and moves backward stage by stage until the optimal path starting at the source node is found.
An ANN model to solve this is discussed below. This section has been written with extensive

reference to the paper by Chui, Maa and Shanblatt [10].

 

stage 1

stage 2

 

stage 3

 

Destination

 

 

 

Figure 4.4. A 3x6 dynamic programming problem.

24

A typical dynamic programming problem is shown in Figure 4.5. A performance measure
is deﬁned as the total length of a valid path from the source node to the destination node. Given the
source and destination nodes, the number of stages m, the number of states in each stage n, and the
metric data d3; (1+1)j' where x is the index of stages, and i and j are the indices of states in each stage,
the problem is to ﬁnd an Optimal path from source to destination. This Optimal path is measured with
respect to a performance criterion. The conventional approach uses the principle of optimality. It
requires intensive calculations and a huge amount Of memory to determine the Optimal solution. In
many dynamic programming applications where a real-time solution is required, the rapid
calculation of near-optimal solutions is more attractive than a slowly computed globally optimal
solution. For example, robot trajectory planning problems, aircraft altitude control problems, and
Optimal control problems that must respond quickly to radically changing environmental conditions
are of this type. Following is a dynamic programming ANN that can provide a near-optimal solution
in an elapsed time of only a few characteristic time constants of the circuit

Consider again the 3x6 dynamic programming problem shown in Figure 4.4. The goal of
the DPP is to ﬁnd a valid path which starts from the source node, visits one and only one state node
in each stage, reaches thedestination node, and has a minimum total lengthamong all possible paths.
To ensure that the ANN dynamic programming algorithm is able to Obtain at least a near-Optimal
solution, the network must be deﬁned ‘by an energy function in which the Optimal solution
corresponds to the lowest energy state of the network. Looking at the characteristics of the optimal
path carefully, two constraints become evident. First, the Optimal path must visit one and only one
state in each stage (structure constraint). Second, the optimal solution must have the minimum total
cost based on the given performance measure (cost constraint). Thus, the energy function has two
requirements. The structural constraint implies that the energy function must converge to stable
states where one and only one state in each stage is active. The cost constraint dictates that the
energy function must converge to stable states representing an optimal path.

Each state node is considered as an individual neuron. Tb develop an appropriate energy

function for the dynamic programming network, take V1,- as the output Of a neuron of the itlr state

 

25

in the xth stage, where n is the number of stages and a and b are positive numbers. The following
formal constraints are thus deﬁned.
1. To ensure that one and only one neuron is active in any stage and the number of

active processing elements is equal to the number of stages,

E1=a/2(EEZinvxj+(2£vxi-n)2).

ijaer‘

2. To ensure that the total length of a valid path is minimum.

E2 = b/4 ( Z 2. z.(dxi(x+1)j in V(x+1)j + d(x-1)j xi in V(x-1)j ) )0

x r 1
E1 comes from the structure constraint and Fa comes from the cost constraint. For a valid
path, E1 will vanish. For a minimum length path, F4 has the minimum value. Therefore, to retain

the characteristic of a gradient system, the energy function for the dynamic programming network

can be written as

E=a/2(ZZZVﬁij+(Ez.in-n)2)+

ijati

b/4 ( Z Z 2 (dxi (x+1)j in V(x+1)j + d(x-I)jxiin V(x-1)j ) ) +
I

I i

We
2 2 am...) l 8,-"(0 at.
x i 0.5 .
V,-

= 13* r. 2 2 (1/in) g,"(C) d5.
1 i 0-5

The quadratic terms in the above equations deﬁne the connection weight matrix T and the

linear term deﬁnes the bias current vector I of the dynamic programming network.

26
Thus, the weight of the connection linking the ith neuron of stage x with the jth neuron of
stage y is
TM:- a * 5,, «1-80)- a-b/2 * dx,yj*(8(x+,,y+8(x_1)y)
where
a * Sxy * ( 1-51-1- ) is the inhibitory connection within each stage.
a is the global inhibition,

b/2 * dxiyj * ( 50+ 1)), + 60-1)? ) is the strength of the metric distance,

l‘ifi=j(x=y).
8‘7 ( or axy ) = { 0 otherwise,

and the input bias current of ith neuron Of stage x is

Ixi = a II.

It is apparent that Txiyj is equal to Tij; for all x,y,i and j. Moreover, E is positive-deﬁnite.
Thus the dynamic programming ANN is a gradient system and the equilibria are bounded in the V
space. VVrth the high-gain limit, the stable states will be close to the minimum states of 13* since the

integral term can be neglected.

4.5 An ANN Model for the Stagecoach Problem

Using the above algorithm, an ANN model for the stagecoach problem is constructed as
shown in Figure 4.5.Values chosen for different parameters are as follows:
a = 5

b=5.

 

27

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10

 

 

 

 

 

 

 

 

 

 

 

 

 

-10.0

 

9

 

 

 

 

 

 

 

 

 

All 0 have weight -5 .0

 

Figure 4.5. An ANN model for the stagecoach problem.

 

 

Cﬁapter 5

Mound Coprocessor:

ﬂl Beﬁamonu Maid

5.1 Introduction

The suitability and advantages Of using VHDL for ANN modeling and simulation have
been discussed in the preceding chapters. We shall see one such system modeled using VHDL.

The immediate objective of this thesis is to model an ANN for solving dynamic
programming problems. The stagecoach problem explained in Chapter 3 is used as a test example
for running the simulation. The ANN model to solve such problems proposed by Chiu, Ma and
Shanblatt[10] has been used for implementing this network.

The larger Objective of this research effort, however, is to demonstrate the suitability and
various advantages one accrues by using VHDL as the vehicle for modeling ANN s. These
advantages include ﬂexibility in design, modularity, and ease of information exchange, and testing
of designs. Hence, the network has been modeled as a general-purpose ANN coprocessor, much like
a math coprocessor. This system can be conﬁgured to model any network with very little extra eﬂ’ort
(none in many cases). Hence, this network is not limited to solving this particular example or this

speciﬁc kind of problem. It can be used as a testbench to simulate and verify different ANN models

28

29

for various domains without signiﬁcant modiﬁcation.

5.2 Design Methodology

In conﬁrmation with the objective of deve10ping a general-purpose ANN coprocessor, the
design has been made as ﬂexible and as general as possible. At the highest level of the hierarchy,
the whole system can be viewed as a coprocessor which has an input port to get initial conditions
for the ANN, a mechanism to enter the interconnection weight-matrix, and an output port to return
the output values of the neurons. This is shown in Figure 5.1.

This coprocessor is built using various components as explained in the next section. The
design methodology adopted across the system is to make different components independent of the
application. The whole network as applied can be described in a package right at the beginning. In
order to do this, one has to assign values for certain variables such as the number of stages in the
network, number of states in each stage, and connectivity between different neurons in the network.
Fmany, an appropriate test bench can be created to test the system.

This structured design scheme facilitates easy modiﬁcation as necessary. New features like

learning, or changing the neuron model, for example, can be accomplished without much eﬂort.

 

 

Initial Cznditions Variable
values

Weight Matrix ANN }
Coprocessor 1

 

 

 

 

 

 

Figure 5.1. The ANN coprocessor.

30

5.3 Design

The top level design of the neural coprocessor is shown in Figure 5.2. The system is
comprised of an ANN at the core, a memory to hold the interconnection weight - matrix, a set of

registers to hold the value of the neurons, and a convergence sensor.

Previous

 

 

Values

 

 

 

 

Neuron Value

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Registers
Artiﬁcial Neural
Network Control

. Line ;

- - 5 Convergence 5 Variable Values
lnrtral Values > ‘ Current Sensor >

: 1 Values i

' 3 Output
Input Weights
Weights

3\ Memory

 

 

 

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Figure 5 .2. Top level schematic diagram of the system.

31

5.3.1 Network: A schematic Of the composition of the network is shown in Figure 5 .3. The network
is built using neurons, where every neuron in the network is connected to all the neurons in the
previous, current and the next stage. The very ﬁrst stage is connected to the very last stage in the
network, making it a ring structure.

As stated earlier, the design is such that the network can be of any size and can be described
by declaring some parameters such as number of stages and number of states per stage. This
description is to be given in the VHDL package declaration called Neural_Package.

Every neuron in the network has available to it the weights and the corresponding stimuli
for it’s links with neurons in the preceding stage and neurons in the same stage (including itself).
Complete connectivity (where every neuron is connected to every other neuron in the network) is
not implemented as it would put unnecessary load on the system. Most of the present day models
are not completely connected. Nevertheless, the system design can be modiﬁed to make the network

completely connected if desired . The VHDL code to accomplish this is listed in Figure 5 .4.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Neurons

 

 

 

 

Figure 5.3. Composition of the network for a case of 5 stages with 3 states per stage.

 

32

 

K

- A network of Neural Elements
use work.Neural_Package.all;
entity network ls

port (
Network_Stlmulus : ln Stlmulus_Matrlx;
Network_Welghts : ln Welghts_Matrlx;
Network_Output : out Neural_Array);
end network;

archltecture network_structure of network Is

component Neural_Node

port (
Stlmulus : ln Unlt_Array;
Welghts : In Unlt_Array;
Output : out Real := 0.0);

end component;

— lnstantlatlon of all Neural_Nodes to the Neural_Element deslgn
unlt

for all : Neural_Node use entity work.Neural_element(behavlor);

begln

element _generate:
for I In 1 to N_Unlts generate
Nodes : Neural_node
port map (Network_Stlmulusa),
Network_Welghts(l), Network_Output(l) );
end generate; '

end network_structure; ,

 

 

 

Figure 5 .4. VHDL code implementing the network.

5.3.2 Neurons: Each neuron in the network is essentially a summation unit. It calculates the inner
product Of the weight and stimulus vectors and provides an output value based on this inner product.

The size of these vectors depends on the size of the network. The parameters are read in from the

 

package declaration Neural_Package. The function CalculateSum is described in the package body

of N eural_Package.

In the present implementation, the sigmoid input - output relation of a neuron as described
in Chapter 4 has been approximated by a step function. This is due to the non-availability of certain
mathematical functions in VI-IDL (such as tanh'1 which is the usual approximation for the sigmoid

function). Approximating the sigmoid with “stair-case” function or a ramp function is is also

33

possible. A schematic of a neuron and the corresponding VHDL code is shown in Figure 5.5.

 

/

 

 

 

 

Neuron
Inputs -> Ii and W;
Neural Function
Output 0
-> 1 if 2 Ii Wi+ bias > threshold
0 Otherwise
after delta delay

 

\

\

 

 

m

- Model of a Neuron Element

use work.Neural_Package.aII;

entlty Neural_element Is

Port (
Stlmulus : In Unlt_Array;
Weights : In Unlt_Array;
Output : out Real);

end Neural_Element;

archltecture behavior of neural_element
Is
begln
NeuralProcess:
process(StImqus'Transactlon)
variable Sum : Real;

begln

Sum := CalculateSum(StImulus,
Welghts) + 10;
It Sum > (0.0) then
Output <= 0.0 after 4 ns;
else
Output <= 0.5 after 4 ns;
and It;
and process;

 

 

 

Figure 5 .5 . Schematic of a neuron and the conesponding VHDL code.

34

5.3.3 Memory: The memory component holds the weights to be used in the network. Weights can
be read from this memory only once at the beginning, or iteratively, if a leaming algorithm is
incorporated. Initially, it was desired to read in interconnection weight - matrix values into the
memory from a ﬁle, making it possible to run different networks without having to rebqu the
network (as long as their dimension is same). This could not be accomplished as the ﬁle I/O
functions available with VHDL are not capable of handling such data transfers in the latest version.
Hence, the current implementation has the interconnection weight-matrix built into the memory
(essentially a ROM). If a different system is to be simulated, the corresponding weight matrix is to
be entered into the architecture of the memory and the system has to be rebuilt.

The VHDL code to model this memory is shown in Figure 5 .6.

 

x

- ThIs module Is meant to be used as a memory to hold the welghts. A centrallzed
memory Is vIsuaIIzed as the change required for a different network would be mIn-
lmal this way.

use work.Neural_Package.all;
entlty memory Is
port (
memory_output : out Welghts_MatrIx);
end memory;

architecture memory_arch or memory Is

begln
memory_output <= (
(0.0, 0.0, 0.0, .1 00.0, 400.0, -1 00.0), (0.0, 0.0, 0.0, 0.0, 100.0, 0.0), (0.0, 0.0. 0.0, -1 00.0, -100.0, -
100.0),
(0.0, «6.0, 0.0.0.0, 60,-5.0), (0.0, -1 0.0, 0.0, «5.0.0.0, -5.0), (0.0, ~75, 0.0,-5.0,-5.0, 0.0),
(-1 7.5, -7.5, -10.0, 0.0, -5.0,-5.0), (-10.0, -5.0, o2.5,-5.0,0.0, -5.0),( -1 5.0, -10.0, -12.5,-5.0,-5.0, 0.0),
(4.5, -1 5.0, -7.5,0.0, o5.0,-5.0),(-10.0, -7.5, -7.5,-5.0, 0.0, 6.0), (0.0, 0.0, 0.0,-100.0,-100.0, 0.0),
(0.0, 0.0, 0.0.0.0, -100.0,0.0),(-7.5, -10.0, 0.0, 0.0, 100.0, 0.0), (0.0, 0.0, 0.0, 0.0,-100.0, 0.0));

end memory_arch;

 

 

 

Figure 5 .6. VHDL code implementing the memory.

 

 

35

5.3.4 Convergence Sensor: The convergence sensor is designed to detect convergence of the
network to a set of values. It compares the present neuron-outputs with the previous set of output
values and sends out a signal if they are identical. This component is more Of a hardware abstraction
and has not been used in actual implementation as the VHDL simulator itself senses convergence

if it is run in the interactive mode, and as the neuron model adopted is a step function.

K

- Thls unlt Is used to sense the convergence of the network
to a solution

The schematic and the equivalent VHDL code is shown in Figure 5 .7.

 

use work.Neural_Package.all;
entity conv_sensor Is
port (
Old_Outputs : In Neural_Array;
New_Outputs : In Neural_Array;
Sensor_Out : out Integer);
end conv_sensor;

architecture sensor_behavlor of conv_sensor ls

signal dIfference : Real := 0.0;
begln
loop _process:
process
begln
Sensor_Out <= 1 after 0 ns;
Ioop1:for I In 1 to N_Unlts loop

dlfference <= abs (OId_Outputs(I) - New_Outputs(I));
If dlfference > Tolerence then
Sensor_Out <= 0;
end If;
endlooploopt;
end process;
end sensor_behavlor;

 

 

 

Figure 5 .7. VHDL code to implement the convergence sensor.

5.3.5 Register Set: The Register set is an abstraction with no exact equivalent in the VHDL model.

 

36

5.3.6 Auxiliary Components: Some auxiliary components required to implement this system in
VHDL, namely a package deﬁnitions called Neural_Package, a neural processor, where different
components are integrated into one entity, and a test bench to test the system are shown in Figures

5.8. 5.9 and 5.10.

 

K

package Neural_Package Is
constant N_Stages : natural := 5;
constant N_States : natural := 6;
constant States _per_Stage : natural := 3;
constant N_Unlts : natural := 15;
type Neural_Array Is array (Natural range 1 to N_Unlts ) of Real;
type Unlt_Array Is array (Natural range 1 to N_States ) of Real;
type Welghts_MatrIx Is array (Natural range 1 to N_Unlts) of Unlt_Array;
type Stlmulus_Matrlx Is array (Natural range 1 to N_Unlts) of Unlt_Array;

functlon CalculateSum (
Stlmulus : Unlt_Array;
Welghts : Unlt_Array)
return Real;

end Neural_Package;

package body Neural_Package Is

functlon CalculateSum (
Stlmulus : Unlt_Array;
Welghts : Unlt_Array)
return Real;
ls
varlable Sum : Real := 0.0;
begln
for I In 1 to N_States loop
Sum := Sum + Stlmulus(l) ‘ Welghts(l);
endloop;
return Sum;
end CalculateSum;

end Neural_Package;

 

 

 

Figure 5 .8. VHDL code for the Neural_Package.

37

 

 

- Thls Is the top level assembly of all the sub-components. Dliterent slgnals
are generated and fed to dlfterent parts.

use work.Neural_Package.all;

entlty ann_processor ls
port (
Stlmulus : In Neural_Array;
Output : out Neural_Array);
end ann_processor;

archltecture processor_structure of ann_processor Is

component memory
PO" (

memory_output :Welghts_Matrlx);
end component;

component network

port (
Network_Stlmulus : In Stlmulus_Matrlx;
Network_Welghts : In Welghts_Matrlx;
Network_Output : out Neural_Array);

end component;

slgnal Matrlx_WeIghts : Welghts_MatrIx :=

((0.0, 0.0, 0.0. 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0). (0.0, 0.0, 0.0, 0.0, 0.0, 0.0).
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0.0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0. 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0. 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0). (0.0, 0.0, 0.0, 0.0, 0.0, 0.0) );

slgnal Matrlx_Stlmulus : Stlmulus_Matrlx :=

((0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0. 0.0), (0.0. 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0. 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0).
(0.0, 0.0, 0.0, 0.0, 0.0. 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0. 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0). (0.0, 0.0, 0.0, 0.0, 0.0, 0.0) );

for all : network use entlty work.network(network_structure);
for all : memory use entlty work.memory(memory_arch);

 

Figure 5 .8. VHDL code implementing the neural coprocessor( Cont’d. on next page ).

 

38

 

begln

procees(Stlmulue'Traneactlon)
varlable tmp1 : Integer := 1;
varlable tmp2 : Integer := 1;
begln
element_loop1 :
for II In 1 to N_Unlts loop
element_loop2 :

for k In 1 to States _per_Stage loop
tmp1 := (II mod States _per_Stage);
II tmp1 = 0 then
tmp1 := N_Stages -1;
end It;
tmp2 := «mm -1) ‘ States _per_Stage )+ k;
Matrlx_Stlmulus(ll)(k) <= Stlmulus(tmp2);
end loop element_loop2;

element_loop3 :
for I In 1 to (N_States - States _per_Stage ) loop
tmp1 := (II mod States _per_Stage);
It tmp1 = N_Stages then
tmp1 := N_Stagee - 1;
endlh

tmp2 := ((tmp1) ' States _per_Stage ) + l ;
Matrlx_Stlmulue(ll)(l + Stetes_per_Stage) <= Stlmulus(tmp2);

end loop element_loop3;
end loop element_loop1;
end process;
read_memory : memory port map ( Matrlx_WeIghts);
- teed the Neural Network with these Welghts and the Stlmulus and obtaln the Output

run_network : network port map ( Matrlx_Stlmulus, Matrlx_WeIghts, Output);

end processor_structure;

 

 

Figure 5 .8. VHDL code implementing the neural OOprocessor ( Cont’ d. from previous page ).

 

39

 

 

- Thle Ie the tee! bench for teetlng the whole eyetem. Whole eyetem le Integrated In ann_prooeeeor.

uee work.Neural_peckege.all;
entlty teet_bench Ie
end teet_bench;

archltecture teet_bench_erch OI teet_bench Ie

component ann_proceeeor
PM“
Stlmulue : In Neural_Array;
Output : out Neural_Array);
end component;

elgnel kln :Neural_Arrey := (0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0);
elgnel kOut : Neural_Array;

for all : ann_proceeeor uee entlty work.enn_proceeeor(proceeeor_etructure);
begln
teeter :enn_proceeeor port map ( kln , kOut );

Proceee(kOut)
begln

kln <= kOut after 10 ne;
end proceee;
end teet_bench_erch;

 

Figure 5.9. VHDL code implementing the test bench.

5.4 Simulating the Stagecoach Problem

 

As has explained earlier, the neural coprocessor is a general one and has to be customized

to run a particular example. Following are the steps to be taken to mn the network to solve the

stagecoach problem that was discussed in Chapter 3.

1. Since there are 5 stages (counting the point of origin and the destination) and there are

3 states in each stage, the following parameters have to be set in the package declaration

N eural_Package.

constant N_Stages : natural := 5;
constant States _per_Stage : natural := 3;
constant N_States : natural := 6;
constant N_Units : natural := 15;

40

Note that N_States speciﬁes the number of links into a neuron ( including the one to itself)
in the network. States _per_Stage is the number of states in each stage.

2. Since the network modeled in VHDL is a symmetric rectangular network, some neurons
may have to be “deactivated” to represent an assymmetric network. The network used to solve
dynamic programnring problems is not rectangular. Therefore, some of the neurons in the network
described in the package declaration have to be isolated from the network. This can be achieved by
making the weights in the interconnection weight matrix corresponding to the inputs Of these
neurons totally inhibitory. Weights conesponding to their output is set to 0. The modiﬁed network
is shown in Figure 5.11.

3. The interconnection weight - matrix, after incorporating the above changes would be as
shown in Figure 5 . 10. This is to be incorporated in the memory ’s architectural description.

This matrix is structured in the form of an array of arrays, where each array represents the
weights for different links for every neuron in the network. The ﬁrst array corresponds to the ﬁrst
neuron ( tOp left) and the last one corresponds to the last neuron ( bottom right). A weight of -100

is found to be inhibitory enough to isolate unwanted neurons from the network.

 

(
(0.0. 0.0, 0.0, -1oo.o, 400.0, 400.0), (0.0, 0.0, 0.0, 0.0, 100.0, 0.0), (0.0. 0.0. 0.0, -1oo.o, -1oo.o, 400.0).
(0.0. -5.0. 0.0, 0.0, so -5.0), (0.0. -1o.o, 0.0, so 0.0. -5.0), (0.0, -7.5, 0.0, -5.0, so 0.0).

(-1 7.5, -7.5. 40.0, 0.0, -5.0, -5.0), (-10.0, -5.0, -2.5, -5.0, 0.0, -5.0),( -15.0, -10.0, -12.5, -5.0, -5.0, 0.0),

(-2.5, -15.0, -7.5, 0.0, -5.0,-5.0),(-10.0, -7.5, -7.5,-5.0, 0.0, -5.0), (0.0, 0.0, 0.0,-100.0,-100.0, 0.0),

 

 

 

Figure 5.10. The interconnection weight - matrix for solving the stagecoach problem.

41

.8283 noaooomﬁm 05 B.— ZZ< 2F .2 .m BEE

 

 

3

 

 

 

 

 

 

 

 

 

”macaw

 

 

 

 

 

 

‘3‘-

”‘4
.00,

e
'0'

 

 

 

)

 

 

 

 

 

 

 

 

 

 

 

 

 

\.

 

 

 

>"e

 

 

 

 

 

 

 

 

666a o ass es: III

Wv‘c.§ >EEDQ é .....................
of: BEOZ All:

 

 

 

 

Chapter 6

Tost-Simﬂation ﬂua[y5i5

6.1 Introduction

The system modeled in VHDL as explained in Chapter 5 was simulated to solve the
stagecoach problem. The initial stimulus values used for these simulations were chosen such that
all possible cases were covered. These simulation runs were monitored for all the transactions for
about lus. The characteristic delay of the whole network was set to about 4 ns and the stimulus
values- output values of the previous iteration, were fed in at the intervals of 10 ns. Outcome of
these simulation runs and an analysis of these results follow.

This system was also used to simulate a diﬂemm problem to verify that the system designed
is not anecdotal to the stagecoach problem. This was accomplished by adding another stage to the

network. The outcome of these simulation runs are analyzed in Section 6.4.

6.2 Results and Analysis

The simulation results for the stagecoach problem are tabulated in Tableﬁ. l. The complete

simulation results can be seen in Appendix C.

Some general Observations on the simulation nm data in Table 6.1 follow. All the vectors

shown indicate the values for all the neurons in the complete network discussed in Chapter 5.

42

Table 6.1. Simulation results for the stagecoach problem.

43

 

 

1g Initial Stimulus Final Outcome # of cycles
a (0.1,0.0,1,0.0,0,1,1.0.0.0.1,0) (0.1.0.0.0,1.o,1.0.0.1.0,0.1.0) 6
b (0.1.0,0.0.1.1,0,0.1,0,0,0.1,0) (0.1.0,0,0.1.o.r.0,0,1.0.o.1.0) 5
c (0.1.0,1,0,0,1.0,0,0.0,1,o,1,0) (0.1.0.0.0.1,0.1.0,0.1,0.0.1,0) 7
d (0,1.0,1,0.0,1,0,1,0.1.0.0.1.0) (0,1.0,0,0,1,o,1.0.0.1.o.0.1.0) 7
e (0.1.0.0,0,1,0,1,0,0,1.0,o,1,0) (0.1.0,0.0.1,0,r.o.o.1.o,o,1,0) 1
f (0.1.0.0.1.0.1,o.o.1,o,o,o.1,0) (0,1.0,0,0.1.o.1,0,0.1,o,o.1,0) 4
g (o. o. o, o, o, o, o. o. o, o. o, o. o. 0, 0) D°°f¥§gg°f§3m° -

 

 

 

 

 

 

1. Runs a and b have an intial stimulus that is a valid solution to the problem, though not
optimal. Both converge to one of the optimal solution in less than 6 cycles.

2. Run c has an input stimulus which has one of the deactivated neurons active. But still the
network converges to an optimal solution in 7 cycles.

3. Run d has an invalid neuron state as the input stimulus (two neurons in the same stage
are active). The network converges to an Optimal solution in 7 cycles.

4. Run e has one of the Optimal solution itself as the input stimulus. It remains in the optimal
state.

5. Run f has another optimal state as the input stimulus, and it is observed that the network

converges to a different optimal state.

44

6. Run g has a zero input stimulus for all the neurons, and the network toggles between all
the neurons being at zero and all the neurons being at one. The same case is observed when all the
neurons are initially set to one.

Hence, it can be seen that the network converges to an Optimal solution, even when the
input stimulus is a diﬁerent Optimal state, in all cases except when all the neurons are initially set

to ZCI'O 01' one.

6.3 Possible Reasons for the Observed Behavior

Some Of the assumptions and approximations made in the present implementation that
might be responsible for the Observed behavior of the network are listed below:

1. The algorithm proposed by Chiu, Ma and Shanblatt claims that Optimization done
pairwise will lead to a global optimization[lO], i.e., every stage in the network need be connected
to only the preceding and succeeding stages, and total connectivity is unnecessary. But this does not
guarantee that this algorithm will lead to all the Optimal solutions. It may lead to only one of the
Optimal solutions which happens to be pairwise optimal too. This could be the reason for the
network converging to the same optimal solution in all the cases (even when the input stimulus is a
diﬂ’erent optimal state).

2. The neuron input-output relation was modeled by a step function in place of a sigmoid
function (due to the unavailability of trigonometric functions in VHDL, at this time). This could be
the reason for the network being not able to move towards a solution when all the neurons are set
to zeros or ones as much of the information gathered in the previous cycle is lost. It behaves like a
memoryless system. Future work is intended to approximate the sigmoid function by a ramp

function, a staircase — like function, etc.

6.4 An Extended Problem

In order to verify that the network designed is not anecdotal to the particular stagecoach

problem and to highlight the ease with which it can be modiﬁed to ﬁt a different problem, an

 

Norm o/ links
0 Links within a Stage

W Dummy links

_>

45
schematic of the extended system is shown in Figure 6.1. The simulation results are tabulated in

 

extended stagecoach problem was developed and was solved using the network modeled in VHDL.
It was seen that the network converges to the optimal solution in less than 4 - 5 cycles as expected.A
Table 6.2. The changes in the VHDL code to effect the desired changes are listed in Figures 6.2, 6.3

and 6.4.

      

   

 

 

 

 

 

 

 

 

 

      
         

 

 

 

 

 

 

 

w x./..w4..?.£:§. nﬁhﬂﬁﬁmwzéuzwrﬁ kw
ruf- IQWMwiu‘oesvrt‘OVK s r5‘4Joehvjil‘.Olil u I,
I n w eel“§o",q‘- . .'-V‘ 0/0.”e"‘§“'~".9%n%00'/

- . . . . .................................. /
.0. .0. .m \I O. 7 )1, O ......................... " I
o .. . .u.u ..... . . n.. .vvn.-o.$w.6 - o
I u ”m m em WWW; l awe” . ..

o v. a. o e
/. u a
o v .

. .. . .
u .. .. . u

g
n V u“ 1V 1‘ (I o
o res 5f o totem]! I! o
u 000000 x\”“n'00"‘/\ﬂl“ 0'V5010'0J0'dt'i‘ryu 0'09’.

.2 . . I i. . . . 7
.. . . mum“ .

. . an” . I
. . u u
I u . ..
. ...
// .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

... ......
. u "z
z 2
K ........
n u
3.. / m.
n. m m 7'0
u u
....... ./
n m :

 

 

 

 

""""

 

O

       

\ are...

0000‘ S'qAV“lﬁ" ’ '0‘- '0
A”: . J 1 \

 

 

33,---.-.-./

 

-J.

 

 

 

   

in?” ”ii. .
.. u mm .. u . 3.
. . mm w Egg. 2 1 . .
/n n u T.
are. , . ....
I Ill. .wgﬂﬁgggg "(were I on.
// 3.89%.»... .43.”..gnees“ 3... J63}? .
I ........ I 000000000 I 000000

 

 

Figure 6.1. The ANN for the extended stagecoach problem.

 

 

46

 

package Neural_Package is

constant N_Stages : natural := ;
constant N_States : natural z: ;
constant States _per_Stage : natural := 3;
constant N_Unlts : natural := 18;

 

 

Figure 6.2. The modiﬁed package declaration for solving the extended stagecoach problem.

X

 

elgnal kln :Neurel_Arrey := (0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0.0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0
I

elgnel IrOut : Neural_Array;

for all : ann_proceeeor uee entlty womenn_proceeeor(proceeeor_etructure);

 

 

 

Figure 6.3. The modiﬁed test bench for solving the extended stagecoach problem.

(0.0, 0.0. 0.0, -100.0, -100.0, -100.0), (0.0, 0.0, 0.0, 0.0. 100.0, 0.0), (0.0, 0.0, 0.0. -100.0, -100.0, -100.0),

 

(0.0, ~5.0, 0.0, 0.0. 35.0. -5.0). (0.0. 40.0, 0.0, -5.0, 0.0, -5.0), (0.0, -7.5, 0.0. -5.0, -5.0, 0.0),

(47.5, ~75. -10.0, 0.0, -5.0, -5.0), (-10.0, -5.0, -2.5, -5.0, 0.0, -S.0),( -15.0. -10.0, -1 2.5, -5.0, -5.0, 0.0),
(~2.5, 45.0, -7.5, 0.0. -5.0, -5.0), (40.0, -7.5, -7.5, -5.0, 0.0, -5.0),( 42.5, -1 2.5, -2.5, -5.0, -5.0, 0.0),
(47.5, «7.5, -10.0, 0.0, -5.0. -5.0), (42.5. 45.0, -10.0, -5.0, 0.0, -5.0),(0.0, 0.0, 0.0. -100.0, -1 00.0, 0.0),

(0.0, 0.0, 0.0, 0.0, 400.0, 0.0),(-7.5, -10.0, 0.0, 0.0, 100.0, 0.0), (0.0, 0.0, 0.0, 0.0,-100.0, 0.0)

 

 

 

Figure 6.4. The interconnection weight - matrix for solving the extended stagecoach problem.

47

Table 6.2. Simulation results for the extended stagecoach problem.

 

 

 

11; Initial Stimulus Final Outcome # of cycles
a (o,1.0.0.0,1,0,0.1,0.1,0.r.0,0.0.1.0) (0,1,0,0,0,1,0,1,0,0,o,1.1,0,o,0,1,0) 6
b (0,1.0,1.0,0,0.o.1.0,0.1, r,0,0,0,1,0) (0.1.0.0,0,1,0,1,0,0,0,1,1,o,o.o,1.o) 4
c (0.1.0.0.0,1,0,0,1,0,0,1.0,0,1,0,1,0) (0.1.0.0,0,1,0,1,0,0,0,1,1,0,0,0,1,0) 4
d (0.1,0,0,0.1.o.0,1,1,0,1,1,0,0,0,1,0) (0.1.0.0,0.1,0,1,0.0,0,1,1,0,0,0,1,0) 4
e (0.1.0.0.0,1,0,1,0,0,0,1.1.0.0,0,1.0) (0,1.0.0.0.1,0,1,0,0,0,1,1,o,0,0,1,o) 1
f (0,1,0,0,0,1,o,o,1,0,0, 1.1,0,0,o,1,0) (0.1.0.0,0,1,0,1,0,0,0,1,1,0,0,0,1,0) 4
g (0,0,0,0,0,0,0,0,0,0,0.0,0.0.0.000) D°°f¥ggg°fgg°rge -

 

 

 

 

 

Cﬁapter 7

Condusion

7.1 Conclusion

The primary objective of this research effort was to prove the suitability of VHDL for ANN
modeling and simulation. This has been achieved by modeling a general purpose ANN coprocessor
in VHDL. This system was tested by simulating a dynamic programming problem. namely the
stagecoach problem. This system was simulated with different initial conditions. The system
modeled behaved according to expectations and the results are encouraging.

This research effort’s contribution has been in establishing the suitability of VHDL for
ANN modeling. The general purpose ANN coprocessor developed can be used to model different

systems with little extra effort.

7.2 Future Research

As has been explained earlier, the objective of this thesis effort was to prove the suitability
of VHDL for ANN modeling, with dynamic programming as a sample domain. Hence, although the
system developed is general in nature and ﬂexible enough to model any problem, the particular

example solved is a simple case with very few features. The future research should be directed to

48

49

enhancing the capabilities of the network by incorporating new features such as learning, different
models for the neuron, and complete connectivity between different neurons in the network. A
much larger problem, with a larger solution space is yet to be modeled. These form a framework

and a direction for future research efforts in this area.

APPENDIX I

VHDL CODE LISTING

VHDL CODE LISTING

- Package declaratlon : Neural Package

package Neural_Package ls
constant N_Stages : natural := 5;
constant N_States : natural := 6;
constant States _per_Stage : natural := 3;
constant N_Unlts : natural := 15;
type Neural_Array ls array (Natural range 1 to N_Unlts ) of Real;
type Unlt_Array Is array (Natural range 1 to N_States ) of Real;
type Welghts_Matrlx ls array (Natural range 1 to N_Unlts) of Unlt_Array;
type Stlmulus_Matrlx ls array (Natural range 1 to N_Unlts) of Unlt_Array;

tunctlon CalculateSum (
Stlmulus : Unlt_Array;
Welghts : Unlt_Array)
return Real;

end Neural_Package;

package body Neural_Package ls

functlon CalculateSum (
Stlmulus : Unlt_Array;
Welghts : Unlt_Array)
return Real
ls -
varlable Sum : Real := 0.0;
begln
for I In 1 to N_States loop

Sum := Sum + Stlmulus(l) * Welghts(l);
endloop;
return Sum;
end CalculateSum;

end Neural_Package;

50

 

 

51

- Model of a Neuron Element

use work.Neural_Package.aII;
entlty Neural_element Is
port (
Stlmulus : In Unlt_Array;
Welghts : In Unlt_Array;
Output : out Real := 0);
end Neural_Element;

archltecture behavlor of neural_element Is
begln
NeuralProcess:
process(StImulus'TransactIon)
varlable Sum : Real;

begln

Sum := CalculateSum(Stlmulus, Welghts) + 10.0;
If Sum > (0.0) then
Output <= 1.0 after 4 ns;
else
Output <= 0.0 after 4 ns;
end If;
end process;
end behavlor;

- Thls module Is meant to be used as a memory to hold the Input values
'- ( Welghts ). A centraIIzed memory Is vIsuaIIsed as the change requlred
— for a dIfferent network would be mlnlmal this way.

use work.Neural_Package.all;
entlty memory Is
port (
memory_output : out Welghts_Matrlx);
end memory;

52

archltecture memory_arch of memory Is
begln

memory_output <= (
(0.0, 0.0, 0.0, 400.0, -1 00.0, 400.0), (0.0, 0.0, 0.0, 0.0, 100.0. 0.0). (0.0, 0.0. 0.0, -1 00.0, -1 00.0, -1 00.0),
(0.0, -5.0, 0.0.0.0, -s.0,-s.o1, (0.0. -10.0, 0.0. -5.0,0.o. -s.0), (0.0, -7.5, o.o.-5.0.-s.o, 0.0),
(4 7.5. -7.5, 40.0, 0.0. -s.o,-5.o1, (40.0, -5.0, -2.5,-5.0,0.0. -5.0).( -1s.o, -10.0, -12.5,-5.0.-s.0, 0.0),
(-2.5, -1 5.0, -7.5,0.0, -5.0,-5.0).(-10.0, -7.s, -7.5,-5.0. 0.0, -s.0), (0.0. 0.0. o.0,-100.o.-100.0. 0.0),
(0.0. 0.0. 0.0, 0.0, -100.o,0.0).(-7.5. -1o.0. 0.0, 0.0, 100.0, 0.0), (0.0, 0.0, 0.0, 0.0,-100.0, 0.0));
end memory_arch;

- A network of Neural Elements

use work.Neural_Package.alI;
entlty network Is
poﬂI
Network_Stlmulus : In Stlmulus_Matrlx;
Network_WeIghts : In Welghts_MatrIx;
Network_Output : out Neural_Array);
end network;

archltecture network_structure of network Is

component Neural_Node
poﬂI
Stlmulus : In Unlt_Array;
Welghts : In Unlt_Array;
Output : out Real := 0.0);
end component;

— lnstantlatlon of all Neural_Nodes to the Neural_Element deslgn unlt
for all : Neural_Node use entlty work.Neural_eIement(behavIor);
begln
element _generate:
for I In 1 to N_Unlts generate
Nodes : Neural_node
port map ( Network_Stlmulus(l), Network_WeIghts(I),

Network_Output(I) );
end generate;

end network_structure;

53

- Thls Is the top level assembly of all the sub-components. leferent slgnals are
generated and fed to dlfferent parts. In essence, It Is the Test-bench for the whole
system

use work.Neural_Packageall;
entlty ann_processor Is
port (
Stlmulus : In Neural_Array;
Output : out Neural_Array);
end ann_processor;

archltecture processor_structure of ann_processor Is

component memory
PO" (
memory_output : out Welghts_Matrlx);
end component;

 

component network
POFN
Network_Stlmulus : In Stlmulus_Matrlx;
Network_WeIghts : In Welghts_Matrlx;
Network_Output : out Neural_Array);
end component;

slgnal Matrlx_WeIghts : Welghts_Matrlx :=(
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0));

slgnal Matrlx_Stlmulus : Stlmulus_MatrIx :=(
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0),
(0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (0.0, 0.0, 0.0, 0.0, 0.0, 0.0));

for all : network use entlty work.network(network_structure);
for all : memory use entlty work.memory(memory_arch);

 

54
begln

process(StlmuIus’Transactlon)
varlable tmp1 : Integer := 1;
varlable tmp2 : Integer := 1;
varlable tmp3 : Integer := 1;
begln
tm p3 := (N_States - States _per_Stage );
element_loop1 :
for II In 1 to N_Unlts loop

element_loop2 :
for k In 1 to States _per_Stage loop
tmp1 := (II / States _per_Stage);
If tmp1 = 0 then
tmp1 := N_Stages -1;
end If;
tmp2 := «mm -1) "' States _per_Stage ) + k;
Matrlx_Stlmulus(ll)(k) <= Stlmulus(tmp2);
end loop element_loopz;

 

element_loop3 :
for I In 1 to tmp3 loop
tmp1 := (II I States __per_Stage);
If tmp1 = N_Stages then
tmp1 := N_Stages -1;

end If;

tmp2 := ((tmp1) * States _per_‘_Stage ) + I;

Matrlx_Stlmulus(lI)(l + States _per_Stage) <= Stlmulus(tmp2);
end loop element_loop3;

end loop element_loop1;
end process;

- read the welght values to be used In the network from the memory

memory_read : memory port map (Matrlx_WeIghts);

- feed the Neural Network wlth these Welghts and the Stlmulus and get the Output

run_network : network port map ( Matrlx_Stlmulus, Matrlx_WeIghts, Output);

end processor_structure;

55

- Thls Is the test bench for testlng the whole system. Whole system Is Integrated In
ann_processor.

use work.Neural_package.all;
entlty test_bench Is
end test_bench;

archltecture test_bench_arch of test_bench Is

component ann_processor
Port (
Stlmulus : In Neural_Array;
Output : out Neural_Array);
end component;

slgnal kln : Neural_Array := (0.0, 1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0,
1.0, 0.0);
slgnal kOut : Neural_Array;

 

for all : ann_processor use entlty work.ann_processor(processor_structure);
begln
tester : ann_processor port map ( kln , kOut );

Process(kOut)
begln

kln <= kOut after 10 ns;
end process;
end test_bench_arch;

APPENDIX II

SIMULATION RESULTS
FOR
THE STAGECOACH PROBLEM

56

 

 

8+m8°8¢.8o+m88oo. ~8+m888d8+m08°8.§+m588o. ~8+m8°8o.8°+m888.8o+m888. _8+§8.§+m§. ~8+mo88°.§+m§§.§+m888.§+§88. ~8+m88§dﬂv
8+m8o8o.8°+m880o. ~8+mo08868+m58o868+mo8§.§+m§8o.8°+m888.§+m888. ~8+m888 68+mo88o. ~8+m°88°.§+m8°§.§+m888.§+m888. ~8+mb8§dﬂn
8+m8o§.8c+m88°°. ~8+m888d8+mo80868+mo8898¢+m8§98¢+m§509§+m888. _8+mco8868+mo880. ~8+mo88o.8¢+m8080.8o+m88oo.§+moo88. ~8+m08o8dﬁu
8+m§8o.8¢+m888. ~8+ﬂ88868+mo8o8d8+m§89 ~8+m8o89 8o+m888. _8+m888. _8+moo88.§+m°88o. _8+mo88°.8°+m8o80.8o+m888.§+m888. ~8+m$8o8§2
8+m8°898o+m88oq ~8+m6o88d8+mo§8da5+mo8§. ~8+m8o89 ~8+m888. ~8+m888. ~8+m888. ~8+m0889 ~8+mo8898o+m8°89 ~8+m888. ~8+moo88. ~8+mo808§3
8.7588.o8+m08°8. ~8+mo8§.8o+m§.8o+m888.§+§88. ~8+mo§8.§+88§.§+mo880.8¢+m§. ~8+m888doo+m88868+m58o8d8+m§89 ~8+m8°§§v
§§88.§+m6808.§+m§8980+m8°8o.§+m888.8¢+§68.50958d8+88§.§+mo8§.8¢¢m8§o.8°+m888.§§.§+§.§+m§8o.§+m8§.8

.

G GEOu—Av—VBOu—An _ VSOMAN $50!“ = VSOMS SHDOMABSOMA SSOMADBOMGVSOMAOBOﬁavVSOu—AGSOMANVSOMA $505376

_
82542208 2

8d d4 dd dd dd d4 d4 dd dd dd .04 dd dd d4 ddv ”ms—26m 3v

 

 

_57

 

 

+ .
8+m88o; 8+8... 8+8... 8+8; 8+888d 8+m888d 8+m88o; 8+m888d 8+m88; 8+m88d 8+m8d 8+8... 8+8; 8+§M
8+mo88o; 8.3886 8+mo88d 8+8d $888.0 8+m888d cam—88; 8E8... 8+m88; 8+m8d 8+m8d 8+8d 8+8; 8+§nh
8.50880; 8+8d 8+m—88d 8+8d 8+m888d 8+m888d 8.588; 8+m8d 8+m88; 8+m88od 8+m8d 8+8d 8+8; 8+§W
8.588; 8+8d 8+8d 8+8; 09.888; 8+m888; 8.5888; 8.5886 8+m88; 8+m88d 8+m88d 218886 8+8; 8+§w
8+m888; 8+m888d 8.588... 8+m88d 8+mo88o; 8+8... 8+8; 8.59886 8+8; 8.58886 8+m8886 8+m88od 8+m88o; 8+MV¥W
8+m888d 8.58886 8+m88d 8+m88d 8+m8d 8+8... 8+8d 8+8d 8+8d 8.58886 8.5886 8+m888d 8+m88d 8+§hv
G 350% Av; VSOM An GSOM an SBOM 2850M 8550M Any—DOM Any—DOM EBOM GVSOM Amy—DOM Avvsou Any—bog ASP—JON SEOu: 82v.

_
v.22 .2205! u NEE.

6d d; dd dd dd d; dd dd d; d; dd dd dd d; ddv $2255 3v

 

 

58

 

8+8d
8+mo88o; 8+8d 8+8... 8+8; 89.886 8+m888d 8+m888; 8.5888... 8.58; 8+8... 8+m88d 8+8... 8+8; 8+888.o _ wv

8.888.... 8.888.... 888.8... 8.88.8. 8888.. 88888.. 88888.. 8.4888... 8888.... 8.888.... 8888...... 8888.... 88.88.. 8%....
8.888.... 8888.... 888.8... 888.8... 88.88... 88888... 88888.. 88888... 85.88.. 8888.... 8888.... 8.888.... 8.8888. 8%“.
8.888.... 8888.... 85888... 888.8... .8888... 88888... 88888... 88888... 88888.. 8.888.... 8888.... 8888.... 8.88.8. 8%“.
8888.... 888.8... 888.8... 8.88.8. 8.888.. 88888.. 86888... 8.4888... 8.8888. 8888.... 8.888.... 8888.... 8888.... 8% H.
8.888.... 8888.... 888.8... 8.888.. 88.88.. 88888.. 88888... 88888... 88888.. 88.88.... 8888.... 8.888.... 888.8. 8%...
8.6888. 86888... 88888.... 88888... 8.888.... 8.888.... 8.88.8... 8888.. 85888.. 88888... 88888.. 88888... 88888.... 8+W§m
88888... 88888... 88.88.... 8888...... 88.88.... 8888.... 888.8... 8888.... 8.888.. 8.888.. 88888.. 88888... 8888.... S+§u
.358. 3.58. a :58. a :58. .558. 8:58. 858. S58. E58. 6.58. 858. 8.58. .053 .658. 2.58. _ 82..

.
mum—24.2.2208 mg

 

 

8d d; dd d; dd dd dd dd d; dd dd d; dd d; ddv ”magnum A3

59

 

 

8+m88o.8o+m888. ~8+m888d8+m688d8+m889 ;8+m88.80+m888.8o+m888. ;8+8.8+888. ;8+m8.8¢+m88.§+m88.8¢+888. ~8+888§ov
8+m88o.8o+m888. ~8+m888d8+88d8+m889 255—88. 80+m888. ;8+m888. ;8+mo88.8+m8. ~8+mo8.8o+m88.8o+m88o.8o+m88. ;8+m88.oﬂv
8+m88o.8+m888. ;8+m888d8+md88d8 +mo88o.8+m88o.8o+m888.8¢+m888. _8+m888.8+m—o8. ;8+mc88.80+m88.8o+m888.§+888. ~8+N88§Nn
8+m8o8.8+m888. ; 8.5888.8+m588.8+mo88.8+m88.8+m88.8+m88.8+m88d8+88. ~8+mo8o.8+m88o.80+m888.§+m888. ~8+8o8dﬁn
8+m88.8o+m888. ~8+moo88.8+m88.8+mo88. _8+m88. 594—889 ;8+m888.8+m88d8+888. ;8+mo88o.8+m88o.8+m88.8o+m88. —8+mc88d.w—
8+m88.8+m888;8+m888d8+88.8+m8. sew—88o. 80+m88o. ;8+m888d8+m.888.8+888o. _8+mc88o.8¢+m88. ;8+m888.8¢+888. ~8+88o8d3~

8+m888.8+mo88. _8+m8o.8o+m88.8o+m888.8+m888.8+888.8+mo88.8+m88c.8+m888. ~8+m888.8+m8. _8+888.8+mo88. ;8+m88.9v

8888.8+88.8+m88o.8+m88.8¢+m888.8+m888d8+888d8+8.8+m8.80+m—8.8o+m888.8288.8+88.8+mo88.80+m8o8§o

_
G CSOKAEVSOMG CSOMAN CECE BROOKS _VSOMAEBOV:850MSEAS—“850%OSOMAVVSOMAeSOMAQSOMA $505876

_
8212205 .34;

8d d; dd dd d; dd d; dd d; dd dd d; dd d; ddv ”magnum AB

 

 

6O

 

8+8...

8+m888; 80888... 8+m88..... 8+m88; 8+m88..... 8+8... 8+8; 8+8... 8+888; 8+m888... 8+8... 8+m888... 8+8; 8.58... _ v
8+8...

8+m888... 8+m888... 8.588.... 8+m88..... 8.588.... 8+8... 8+8... 8+8... 8888... 8+m888... 8.5888... 8+m88... 8+m88... 8+m88... _ ..
.

$550M .v...—.00M .n 550.. .N 550.— 9350.. 6050! .050“ .ogou €50“ 6.50M .850.— .v.50¥ .050.— .6SOM 3.50.. _ .mZ.
.

”85; 8.» . BE...

8... d; d... d... d; d... d... d; d... d; d... d... d... d; dd. 6258.5 .0.

61

 

8+8...

8+m88; 8+8... 8+8... 8+8; 8+8... 8+m888... 8+m888; 8+m88... 8.588; 8.58... 8+m8... 8+8... 8+8; 8+8... _ «N
8+8...

8+m—88; 8+8... 8+8... 8+8... 8+8; 8+m888... 8888...... 8+m88o; 8N8; 8+m8... 8+m8; 8+8... 8+8; 8+8... 2
8+8...

8+m88; 8+8... 8+8... 8+8... 8+8; 8+m888... 8+m888; 8+m88; 8+m88; 8+m88... 8.8.88...— 8+88..; 8+8; 8+8... _ #—
8+m88...

8.5888; 8+m888... 8N8... 8.588.... 8+m88; 8+8... 8+8... 8+8; 8+8... 8+m888... 8+m888... 8+m888... 8+m88; 8+m88... _ v
8+8...

8.5888... 8+m888... 8+m88... 8+m88d 8+m..88..... 8+8... 8+8... 8+8... 8+8... 8+m888... 8+m888... 8M8... 8+m88... 8+8... _ ..
_
.n 580.. 93.50.. .n 350.. .N 050.. 2.....00H 8550.. 3.80.. 3.50.. 650.. G.SOH .n..—.DOM 9950.— .n..—.DOM .380“. .5500: 82.

.
”85,. 85 m S

...d d; d... dd d... d; dd d... d; d... d; dd dd d; dd. ”magnum Q.

 

 

62

 

 

.w
x.

*

+8 8 a a a .

8+8; 8+m888... 8+m888... 8+m88... 8+m88..... 8+m8... 8+m8... 8+8... 8+8... 8+8... 8+8... 8+m888... 8+m8; 83...”.890 . 8....

8+m8; 8+8... 8+8... 8+8; 8+8; 8+m8; 8+m8; 8+m888; 8+m8; 8+m8... 8+.m8; 8+8... 8+8; 8+“..88.... 3..
+ o o a :8.

8+m8; 8+8... 8+8... 8+8... 8+8... 8+m888... 8+m8... 8+m88... 8N8... 8+8... 8+m8... 8+8... 8+8; 8+§d . X...
+ a a a a .5.

8+m8; 8+8... 8+8... 8+8; 8+8; 8+m888; 8+m8; 8.5888; 8&8; 8+m8... 8+m—8; 8+8... 8+8; 8+“Mh8... . 00..
$5 8 a a...

8+m8; 8+8... 8+8... 8+8... 8+8... 8+m888... 8+m8... 8+m8... 8N8... 8+m8... 8+m8... 8+8... 8+8; 8+?d _ 3...
+8 .5 a a o .

8+m88; 8+8... 8+8... 8+8; 8+8; 8+m888; 8+m8; 858; 8+m8; 8+m8... 8+m8; 8+8... 8+8; 8+?d _ and
+ o 8 a a a .

8+m8; 8+8... 8+8... 8+8... 8+8... 8+m888... 8.58... 8+m8... 8+m8... 8+m8... 8N8... 8+8... 8+8; 8+hh8... _ a...
+8 8 no...

8+m88; 8+m8; 8+m8; 8+m88; 8+m88; 8+8; 8+8; 8+8; 8+8; 8+m888; 8+m8; 8N8... 8&8; 8+”...88; .v.
+8 5 o a o a .

8+m88... 8+m8... 8+m88... 88.8... 8+m8... 8+8... 8+8... 8+8... 8+8... 8+m8... 8+m8... 8+m8... 8+m8... 8+”.8... _ .H.

3580.. $350.. .n $50M .N 550.. 2050.. ...;....DOM .050! .8SOI 650... 6.50.— 9.50.. .850.— .n....DOM .650M 280.— _ 62..

_

 

 

8(2 8208 m 8

.o... d... dd dd dd d... d... d... dd dd dd d... d... d... dd. 8228.8 0.

BIBLIOGRAPHY

BIBLIOGRAPHY

[1] JJ. Hopfield and D.W. Tank, “Neural Computation of Decisions in Optimization Problems,”
Biological Cybernetics, Vol. 52 , 1985, pp. 141 - 152.

[2] C. Mead, Analog VLSI and Neural Networks, Addison-Wesley, 1989.

[3] H.P. Graf, “VLSI Implementation of a Neural Network Memory with Several Hundred
Neurons,” Proc. of AIP Conf. on Neural Networks for Computing, No.151, 1986, pp. 182-187.

[4] A. S. Gilman, “VHDL - The Designer Environment,” IEEE Design & Test of Computers, April
1986, m). 42 - 47.

[5] V.D. Agrawal, “The Linguistics of Design and Test," IEEE Design & Test of Computers, April
1986, page 8.

[6] A. Dewey and A. Gadient, “VHDL Motivation,”IEEE Design & Test of Computers, April 1986,
pp. 12 - 16.

[7] JD. Nash and LP. Saunders, “VHDL Critique,” IEEE Design & Test of Computers, April 1986,
pp. 54 - 65.

[8] Hillier and Lieberman, Introduction to Omrations Research (Eourth Edition), Holden - Day Inc.,
Oakland, CA., pp. 332 - 336.

[9] 8D. Shriver, “Artiﬁcial Neural Systems,”, Computer, March 1988, pp. 8 - 9.

[10] C. Chiu, C.Y. Ma and M.A.. Shanblatt, “An Artiﬁcial Neural Network Algorithm for Dynamic
Programming,” to appear, International Journal of Neural Systems.

[11] VHDL Language Reference Manual, Version 7.2, Technical Report IR - MD - 045 - 3,

Intermetrics, Bethesda, MD., 1 Jan, 1987.

[12] R. Lipsett, C. Schaefer and C. Ussery, WM, Kluwer
Academic Publishers, 1989.

[13] DR. Coelho, MW, Kluwer Academic Publishers, 1989.

63

 

64

[14] 8.8. Leung and M.A. Shanblatt, ASIC System Design with VHDL: A Paradigm, Kluwer
Academic Publishers, 1989.

  

gnRIES
5}]
H

”9]“9]°9]9]9]T9”]9]]9li]

 

 

45