Shannon I. Steinfadt

Associative Computing (ASC) Reference Page

About the Model

ASC is a generalized version of the associative computing style that has been in use since the 1970’s with the introduction of associative SIMD computers such as the STARAN [Potter94].  Associative computing includes the use of data parallel programming, which is sequential in nature.  Unlike MIMD programming, ASC programmers are not responsible for task allocation, load balancing, synchronization points, etc.

The reference to the word “associative” is related to the ability to locate data in memory by content rather than by location.  As shown in the figure, the ASC model consists of an array of cells and a single instruction stream.  The cells are composed of a processing element (PE) and a local memory.  Each PE is capable of performing local arithmetic, logical operations and the usual functions of a sequential processor other than issuing instructions.  Every PE listens to the instruction stream (IS), which broadcasts data and instructions.

The ASC model uses associative searching to locate data cells by content rather than memory address.  Unlike an associative memory, the data remains in place in the responder cells and are processed in parallel. 

Cells may be active, inactive, or idle.  The IS can broadcast to all of its cells and only the active PEs execute an associative search.  Based on the results of its search, cells are again partitioned into active cells (responders) or inactive cells (non-responders). Idle cells are currently inactive with no essential program data, but they can be reassigned as an active cell. 

Since only active cells execute the instructions broadcast from the IS, inactive cells listen but do not execute the broadcast instructions.

ASC has several global operations.  The IS may broadcast data to all of its active cells, invert the responders and the non-responders, as well its ability to select a single cell from the set of responder cells.  An IS may compute the global AND, OR, MAX or MIN of data in all active cells.  These reduction operations take constant time relative to the bit length of a memory word [Falkoff62][Jin01].  This MAX feature is useful since the maximum D value must be found for the start of the traceback in the local alignment algorithm.

There are no restrictions on the type of cell network used with the ASC model in general. The programmer does not need to worry about the actual network hardware or the routing scheme, but only that ASC is capable of generalized routing with some latency.  SIMD computers are particularly efficient in data movement. 

A great overview with an example algorithm is the IEEE Computer paper, the first reference below.  ASC's home on the web is located at http://www.cs.kent.edu/~parallel/.  Software links can be found under the "Software" link.

[Potter94] J. Potter, J. Baker, A. Bansal, S. Scott, C. Leangsuksun, and C. Asthagiri. “ASC: An Associative Computing Paradigm.”  IEEE Computer, 27(11): pp. 19-25.  November, 1994.
[Falkoff62] A. D Falkoff.  "Algorithms for Parallel-Search Memories", Journal of the ACM, 9(4), 488-511, October 1962.
[Jin01] M. Jin, J. Baker, K. Batcher. "Timings for Associative Operations on the MASC Model." in Proc. of the 15th IPDPS, MPP Workshop, April 2001.

Using and Running ASC

The ASC compiler and emulator are available for download.  Also, listed below is a local copy of the nice reference handout from Obie Slotterbeck on how to run the compiler and emulator.

ASC language primer: Table of Contents (pdf)

ASC language primer (pdf)

Windows EXE files:

ASC Compiler ASC Emulator Running in Windows (pdf)  Running in Windows (doc)

C Code for Compilation on Windows, Unix / Linux, Mac, etc.:

ASC Compiler ASC Emulator Test Suite Tar

 

ASC Syntax Highlighting for Xcode 3.0 on Apple MacOS 10.5.4 (Leopard):

These files need to be copied into the /Developer/Library/Xcode/Specifications directory and Xcode has to be restarted to get the benefits of syntax highlighting and auto-completion.

These files USED to reside as the *.pbsfilespec and the *.pblangspec that were stored in the /Library/Application\ Support/Apple/Developer\ Tools/Specifications/ in earlier versions of Xcode.

Modified from language specifications posted by Andreas Färber listed online as "Xcode 3 C# syntax coloring." I'm having a bit of trouble modifying the files to not be case sensitive and to highlight any capitalization combination. I'm currently looking in /Developer/Library/Private Frameworks/XcodeEdit.framework/Versions/A/Resources/ for examples to help with this..

 

Edit Remote Files in Xcode

** Note for Mac users - you can use MacFuse from Google to FTP and treat  the remote server as another volume (i.e. can be accessed like a local disk) and edit files in Xcode!  A nice description of usasge in this manner can be found here.  The VERY helpful GUI is MacFusion available at http://macfusionapp.org/.

XCode 3 Search and Replace Regular Expressions Syntax

The regular expression syntax is not uniform in Xcode. All of the documentation listed indicates that it based on the ICU library. It appears that Xcode's find and replace "Regular Expression" grammar has some Perl-like structure to it. Some notes to help for search and replace are listed below and another good resource is the Noodlings online thread. Any good search hints and tips are welcomed at ssteinfa ".at." kent.edu.

^ beginning of line

$ end of line

[12][[:alpha:]] – find 1 or 2 followed by a letter

[12][[:alpha:]]+ – find 1 or 2 followed by one or more letters

[01[:alpha:]%]

Other qualifiers:

To find ANY string that doesn't’t contain a, b or c: [^abc]

To find the beginning of a comment (\***) and to match complete it on the line (/***):

SEARCH field: ^\/\*\*\*.*  OR ^\/\*\*\**

REPLACE field: \0***/

The first wild card expression is matched with the \0. Following expressions are followed by \n where n >= 0.

©2006-2008 Shannon I. Steinfadt