A Smart Memory Array Processor for Two Layer Path Finding

Abstract

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.