Connex Project History

The Connex Project

(This document mirrors the page maintained by G. Stefan)

The Connex Project started with the Connex Memory.

Connex Memory: is the hardware support for efficient string store, search, insert, read and delete.

The concept of Connex Memory (CM) is a sequel of the [lispMachine.html Lisp Machine] project (see the story in [Stefan '02]). The concept is first presented in [Stefan '85/91], but unpublished until 1991 because "the cabinet 2" has forbidden the use of the sintagm "artificial intelligence".

The main feature of CM consists in searching strings in "constant" time ("constant" instead constant because of a very small weighted log which is inevitably there due to of physical reasons). For example, if the string "george" is to be searched in a very big string, then the following sequence of commands identifies all the occurences of "george" and accesses the first:

find g;
cfind e;
cfind o;
cfind r;
cfind g;
cfind e;

John Sununu, explaining to Bill Frezza the reasons to invest in Connex Technology (now BrightScale Inc.), uttered the best explanation for this feature of the Connex Memory:

Using the Connex Memory, we search "the needle in a hay stack" using time proportional to the size of "the needle" rather than time proportional to the size of "the stack".

The main development stages of the concept of CM

1. The initial definition

CM is a sort of associative memory containing a string of variables whose value can be accessed to be read or modified using the following set of simple one cycle operations:

• reset s : all the variables after the first marked variable take the value s
• find s : all the variables that follow a variable having the value s switch to the marked state and the rest switch to the nonmarked state
• cfind s : all the variables that follow a marked variable having the value s switch to the marked state and the rest switch to the nonmarked state
• insert s : the value s is inserted before the first marked variable
• readup | down | -  : the output has the value of the first marked variable and the marker moves one position to right (up) or to left (down) or remains unchanged (-)
• delete : the value stored in the first marked position is deleted, the position remains marked (in the current cycle the output has the value of the deleted variable) and the symbols from the right are moved one position left.

For an extended description see [Stefan '98a].

2. Exotic applications

A lot of exotic applications were investigated prior to 2001:

• Artificial Life (see [Stefan '95])
  
• Algorithmic Complexity (see [Stefan '96])
  
• Molecular Computing (see [Stefan '97], [Stefan '97a], [Stefan '98b])
  
• Theory of Computation (see [Stefan '98], [Stefan '98a])
  

The main colaborators: Mihaela Malita and Robert Benea

3. From CM to Connex Engine

In 2001 spring semester, during a sabatical half-year, the concept of CM is applied to bio-informatics and expanded in a colaborative work with Dominique Thiebaut. CM becomes Connex Engine (CE) expanding the physical resources from one-word cell to many-word cells.

The application domain investigated with CE is bioinformatics (see [Stefan '01] and Dominique's research web page).

The main outcome of this stage is the patent application issued in August 2001.

4. The Connex Architecture

In 2001 Fall semester the concept of Connex Architecture (CA) was developed with Dan Tomescu. The CE becomes now a general purpose computational architecture.

The first application investigated by Dan Tomescu using CA: in memory data bases.
The second application investigated was a SoC for still camera. Basic algorithms on CA where developed in colaboration with Mihaela Malita and Dominique Thiebaut.

The prototype version of ConnexArray^TM - an array of 4096 processing elements - was designed and produced at TSMC. Main collaborators: Bogdan Mitu (testing), Victor Radu-Radulescu (physical design).

5. Connex Technology

Starting from 2003 inside Connex Technology, Inc. (co-founded with Paul Conley, John Sununu, Dominique Thiebaut, Dan Tomescu) CA is developed as Connex Technology optimizing CA for a specific application domain: image processing. The main colaborators in this stage are: Bogdan Mitu, Dan Tomescu.

The company has built a [ca4096.ppt PCI board] deploying 4 of its ConnexArray^TM test chips, each of which contains 4,096 PEs. The board was used by Government Agencies for string searches of very large databases, utilizing the Connex machine capability to search for a string in a time proportional to the length of the string, rather than the size of the database, as is the case with conventional search engines.

Connex Technology is implemented as the core of [CA1024.pdf CA1024] chip produced by Connex Technology, Inc. (see [Stefan '06] for architectural description and for the basic performances). The new features added in this stage are:

• Connex Programming Lannguage (CPL)
• "microprogram-like" execution at the Processing Element (PE) level
• hardware support for multiplication
• hardware support for scalar vector multiplication
• Input-Output System

The first public presentation of Connex Technology occurs in Microprocessor Report.

---

References

Patents:

Gheorghe Stefan, Dominique Thiebaut: Memory Engine for the Inspection and Manipulation of Data (United States Patent 6,760,821, February 20, 2003; Filed: August 10, 2001)
Gheorghe Stefan, Dominique Thiebaut, Dan Tomescu: Associative memory device (United States Patent 7,069,386, June 27, 2006; Filed: May 10, 2004)
Dan Tomescu, Gheorghe Stefan: Data processing system having a Cartesian Controller (United States Patent 7,107,478, September 12, 2006; Filed: December 4, 2003)

Papers

[Stefan '85/91] Gh. Stefan, V. Bistriceanu, A. Paun, "Catre un mod natural de implementare a LISP-ului" (Toward a Natural Way to Implement LISP), in Sisteme cu inteligenta artificiala (Systems for Artificial Intelligence), Ed. Academiei Romane, Bucuresti, 1991 (paper at Al doilea simpozion national de inteligenta artificiala (The Second National Symposium on Artificial Intelligence), Sept. 1985). p. 218 - 224.
[Stefan '86] Gh. Stefan, "Memorie conexa" (The Connex Memory) in CNETAC 1986 Vol. 2, IPB, Bucuresti, 1986, p. 79 - 81.
[Stefan '91] Gh. Stefan, F. Draghici, "Memory Management Unit - a New Principle for LRU Implementation" in Proceedings of 6th Mediterranean Electrotechnical Conference, Ljubljana, Yugoslavia, May 1991. p. 989 - 992.
[Stefan '91a] Gh. Stefan, F. Draghici, "Memory Management Unit with a Performant LRU Circuit" in Buletinul IPB, Tom LIII, Nr. 1-2, 1991. p. 89 -96.
[Stefan '95] Gh. Stefan, Mihaela Malita, "The Eco-Chip: A Physical Support for Artificial Life Systems", in Artificial Life. Grammatical Models, ed. by Gh. Paun, Black Sea University Press, Bucharest, 1995. p. 260 - 275.
[Hascsi '95a] Z. Hascsi, Gh. Stefan, "The Connex Content Addressable Memory (C2AM)" in Proceedings ot the Twenty-first European Solid-State Circuits Conference, Lille - France, 19 - 21 Sept. 1995, p.422-425.
[Stefan '96] Gh. Stefan, Mihaela Malita, "Chaitin's Toylisp on a Connex Memory Machine", in Journal of Universal Computer Science, Vol. 2, No. 5, May 28, 1996, p.410 - 426. (Special Issue: C. Calude (ed.): The Finite the Unbounded and the Infinite, Proceedings of the Summer School "Chaitin,s Complexity and Applications", 27 June - 6 July, 1995.)
[Hascsi '96a] Z. Hascsi, B. Mitu, M. Petre, G. Stefan, "High-Level Synthesis of an Enchanced Connex memory", in Proceedings of the International Semiconductor Conference, Sinaia, October 1996, p. 163-166.
[Stefan '97] Gh. Stefan, Mihaela Malita, "DNA Computing with the Connex Memory", in RECOMB 97 First International Conference on Computational Molecular Biology, January 20 - 23, Santa Fe, New Mexico, 1997. p. 97-98.
[Stefan '97a] Gh. Stefan, Mihaela Malita, "The Splicing Mechanism and the Connex Memory", Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, Indianapolis, April 13 -16, 1997. p. 225-229.
[Stefan '98] Gh. Stefan, Robert Benea, "Connex Memories & Rewriting Systems", in MELECON '98 9th Mediterranean Electrotechnical Conference, May 18-20, 1998, Tel-Aviv, Israel. p 1299-1303.
[Stefan '98a] Gh. Stefan, "The Connex Memory: A Physical Support for Tree / List Processing", in The Roumanian Journal of Information Science and Technology, Vol.1, Number 1, 1998, p. 85 - 104.
[Stefan '98b] Gh. Stefan, "Silicon or Molecules? What's the Best for Splicing", in Gh.Paun (ed.) Computing with Bio-Molecules. Theory and Experiments, in Springer, 1998. p. 158-181
[Stefan '01] Gh. Stefan, Dominique Thiebaut, "Hardware-Assisted String-Matching Algorithms", in WABI 2001, 1st Workshop on Algorithms in BioInformatics, BRICS, University of Aarhaus, Danemark, August 28-31, 2001.
[Stefan '02] G. Stefan: "Masina DIALISP - o realizare cu efecte intarziate", in Computers and Computer Networks in Romania 1953-1985, Romanian Academy, 11/22/2001.
[Stefan '06a] G. Stefan: "The CA1024: A Massively Parallel Processor for Cost-Effective HDTV", in SPRING PROCESSOR FORUM: Power-Efficient Design, May 15-17, 2006, Doubletree Hotel, San Jose, CA.
[Stefan '06b] G. Stefan: "The CA1024: A Massively Parallel Processor for Cost-Effective HDTV", in SPRING PROCESSOR FORUM: Power-Efficient Design, June 8-9, 2006, Tokyo
[Malita '06] Mihaela Malita, Gheorghe Stefan, Marius Stoian: "Complex vs. Intensive in Parallel Computation", in International Multi-Conference on Computing in the Global Information Technology - Challenges for the Next Generation of IT&C - ICCGI 2006 Bucharest, Romania, August 1-3, 2006.
[Thiebaut '06] Dominique Thiebaut, Gheorghe Stefan, Mihaela Malita: "DNA search and the Connex technology" in International Multi-Conference on Computing in the Global Information Technology - Challenges for the Next Generation of IT&C - ICCGI 2006 Bucharest, Romania, August 1-3, 2006.
[Stefan '06c] Gheorghe Stefan, Anand Sheel, Bogdan Mitu, Tom Thomson, Dan Tomescu: "The CA1024: A Fully Programable System-On-Chip for Cost-Effective HDTV Media Processing", in Hot Chips: A Symposium on High Performance Chips, Memorial Auditorium, Stanford University, August 20 to 22, 2006.
[Stefan '06d] Gheorghe Stefan: "The CA1024: SoC with Integral Parallel Architecture for HDTV Processing", invited paper at 4th International System-on-Chip (SoC) Conference & Exhibit, Radisson Hotel Newport Beach, CA, November 1 & 2, 2006.