Introduction
In the late 1970s and early 1980s, artificial intelligence research faced a significant hurdle known as the "search explosion." Representing common-sense knowledge in traditional serial databases required complex heuristics to avoid exhaustive searches. The NETL system proposed a paradigm shift: representing knowledge as a physical network of nodes and links that pass "markers" (single-bit signals) in parallel. However, scaling this to a million nodes presented a massive engineering challenge: interconnection. A full crossbar switch for such a system would require approximately four trillion connection points. This paper presents a design for a million-element NETL machine that achieves high connectivity using a novel, probabilistic interconnection scheme called a hashnet.
The Hashnet Architecture
The core innovation of the proposed machine is the Hashnet, a multi-level, time-shared switching network. Rather than providing a rigid, guaranteed connection for every possible pair of nodes, the Hashnet relies on probabilistic routing.
The architecture employs several key strategies:
- Probabilistic Routing: Internal connections are wired in a pseudo-random pattern. While this does not guarantee a path for every request, it ensures that the probability of a "blocking" event (a failure to connect) is extremely low.
- Time-Sharing: The physical hardware contains roughly 1,000 switching units, which are time-shared 1,024 ways. This allows the machine to simulate approximately one million "virtual" elements.
- Selector Cells: The design utilizes custom 15-way selector cells arranged in four layers. If a path is blocked, the system can simply attempt a different virtual link.
Implementation and Marker Passing
Unlike traditional CPUs that manipulate multi-bit data words, the NETL machine moves single bits, or "markers," across the network. This allows for massive parallelism in operations like set intersections and property inheritance. The design leverages 64K RAM chips not just for data storage, but as the state-holders for the time-shared processing elements. This approach aligns the cost of a high-speed AI machine with that of a standard serial computer's memory.
Results and Performance
The proposed design demonstrates that a million-element system can be constructed using approximately 7,000 integrated circuits, the majority of which are standard 64K RAM chips.
Key performance metrics include:
- Scale: 1,000,000 virtual elements.
- Speed: A basic marker propagation time of 5 milliseconds. Complex queries can be resolved in 0.1 to 0.3 seconds, independent of the total knowledge base size.
- Efficiency: The hardware cost is comparable to storing the same data in a conventional serial database, while providing the advantages of parallel search.
Limitations and Future Work
While the design is promising, several challenges remain. At the time of the proposal, 64K RAM chips were a scarce resource. Additionally, the "random" wiring between layers presents significant board-level layout challenges. Fahlman also notes that while a million elements provide significant capacity, it remains an open question whether this is sufficient for human-like common-sense understanding. Finally, the reliance on an external serial processor for orchestration could become a bottleneck for highly complex deductions.
Summary updated