Data structures and VLSI algorithms for bubble chips

This paper demonstrates that data structures such as linear lists, binary trees, and tables, all containing variable-length entities, can be mapped into major/minor loop bubble chips. The use of external indicator loops can facilitate the storage, search, and retrieval of information by providing structural information, traversal guidance, or registers for intermediate results of search. The central objective is compact storage and minimum I/O operations. However, in order to improve overall system performance, logic-in-memory schemes eventually have to be pursued. Algorithms suitable for VLSI implementation are illustrated with a sorter design, which emphasize the virtues of simple and regular cells, simple and regular connections, and amenability to parallel and pipelined operations. Finally, the intrinsic attributes of bubbles are enumerated to indicate opportunities for VLSI bubble memory/logic chips.