A Caltech Library Service

A Smart Memory Array Processor for Two Layer Path Finding

Carroll, Christopher R. (1981) A Smart Memory Array Processor for Two Layer Path Finding. In: Proceedings of the Second Caltech Conference on Very Large Scale Integration. California Institute of Technology , Pasadena, CA, pp. 165-195.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper describes three examples of hardware implementations of path finding schemes based on the Lee-Moore maze solving algorithm. one is purely a demonstration circuit to show the technique. The other two are complete LSI implementations which should be usable in building large and useful path finding machines. One of these two LSI circuits, known as the MAZER, is designed to find shortest paths from one point to another on a plane, where there is only one layer of allowable routes to take. As its name suggests, this chip solves ordinary mazes, or on a more practical level, it can route wires on a one sided printed circuit board. The other LSI circuit, known as the PATHFINDER, is designed to handle the two sided printed circuit board case. It finds a least costly path from one point to another where there are two parallel planes on which routes are allowed. Crossing of the path from one plane to another can be either unrestrcited, as in free via printed circuit boards, or permitted only in certain places, as in fixed via boards. The phrase "least costly" above can, for now, be read as "shortest", although in a later section a more general definition will be revealed. The remainder of this document is divided into three parts. The first section outlines the original Lee-Moore algorithm for path finding on which the circuits described later are based. The second section details the one layer hardware, including both the demonstration circuit and the MAZER chip. Finally, the third section describes the PATHFINDER chip and the techniques used to conquer the problems encountered in two layer path finding. Documentation on the integrated circuits includes those results of testing and characterization which were available at the time of this writing.

Item Type:Book Section
Additional Information:The research described In this paper was sponsored by the Defense Advanced Research Projects Agency, ARPA Order number 3771 , and monitored by the Office of Naval Research under contract number N00014-79-C-0597.
Funding AgencyGrant Number
Defense Advanced Research Projects AgencyARPA Order 3771
Office of Naval ResearchN00014-79-C-0597
Record Number:CaltechCONF:20120507-155151454
Persistent URL:
Related URLs:
URLURL TypeDescription
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:216
Deposited By: Kristin Buxton
Deposited On:08 Aug 2012 16:51
Last Modified:03 Oct 2019 22:50

Repository Staff Only: item control page