TweetFollow Us on Twitter

Paralation
Volume Number:8
Issue Number:7
Column Tag:Lisp Listener

The Paralation Model

A simple model comprised of only one data structure and three operators

By Paul Snively, Sunnyvale, California

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

We’re rapidly approaching perhaps the most interesting time in all of the existence of personal computing. The winds of change are upon us, and this much is clear: we programmers are going to have to adopt new programming paradigms if we expect to survive into the future.

In terms of the hardware that we use, old classifications and distinctions are being either blurred or obliterated on a daily basis. The line between high-end PC and low-end workstation is becoming artificial, a matter of marketspeak only, as time marches on. The machine that this magazine is devoted to has always had the capability that is probably 2nd most-often used to designate a workstation as opposed to a PC-networking capability. The most-often used designator, “performance,” is something that can be achieved principally through changing processors. Nearly everyone in the industry has heard about the architectures vying for attention-Motorola’s 88000 family, MIPS, Sun’s SPARC, and IBM’s RS/6000, to name only the ones that come immediately to mind. In addition, Apple has been investigating RISC for some time.

It only stands to reason that another revolution will ensue as the average power of even the most affordable machines goes from the order of the single-digit MIPS (with the “high end” Macintosh IIfx being around 8.5, if memory serves me correctly) to more on the order of the low-three-digit MIPS, say 120 on the “low” end of the spectrum. If the new revolution doesn’t begin-if all we do when we go from 8.5 MIPS to 120 MIPS is recalculate our spreadsheets faster-we’ll have only ourselves to blame. Regardless, something that should be fairly apparent in all of this is that the chips are approaching their limits. I’m not referring to limits of the state of the art; those change daily. Rather, I’m referring to the pace at which the capabilities of our silicon foundries are approaching the limits of the laws of physics. We can only go so far with smaller/faster/cheaper until Einstein, Bohr, and others step into muddy the waters. Mechanical engineering gives way to quantum mechanics, as it were.

This may sound pretty dismal, but there is an obvious solution to the problem: start building machines with more than one processor. If one blazing processor is good, wouldn’t more be better? The answer, of course, is “yes, depending upon the nature of the problem being solved,” and that opens a can of worms all its own. If you have a parallel architecture, the way that you must go about creating software for it changes accordingly, and most of us are not accustomed to programming for parallelism. God knows I’m not. And it’s not as though there were a consistent mental model to apply to the notion of parallel programming, either. For one thing, most of the effort that I’m familiar with regarding parallel programming has been done in order to adapt an already largely outmoded programming methodology-“structured programming,” the holy grail of the ’70s-to parallelism. Research to integrate what I’ll call the holy grail of the ’80s-“object-oriented programming,” which seems better suited to programming in the large than structured programming alone-with parallel programming still seems to be largely open, with few real-world implementations available.

Parallelism has its own language, of course, with terms like SIMD, MIMD, Shared Memory, coarse- and fine-grained, “massively,” data flow, and the like, and has systems with names like Transputer, Sequent, Butterfly, Hypercube, Cray, and Connection Machine. In terms of generally-applicable software to allow the implementation of parallel systems, the ones that I’ve heard the most about are Linda (as a model and environment) and Occam (as a language). Unfortunately for me, I could never wrap my brain around either of them, although I’d like to give Linda another shot some day.

In the meantime, there is another model that I think deserves a lot of attention, because it provides you explicit control over the costs of both computation (work done by the processors) and communication (how much wire and how many intermediate stops must a signal take to get from one processor to another). It’s architecture independent-it doesn’t care whether it’s on a MIMD, SIMD, Shared Memory, etc. machine. Most importantly to me, it’s simple. The whole model is comprised of one, count ’em, one data structure and three, count ’em, three operators. The model is also base-language independent: there are at least two implementations in Lisp, and an experimental implementation in C.

The model is called the Paralation Model, and was developed by Gary Sabot, a senior research scientist at Thinking Machines, Inc., creators of the Connection Machine, a massively-parallel computer capable of supporting up to 65,536 processors. It’s described in the book entitled The Paralation Model, published by The MIT Press, ISBN 0-262-19277-2.

The principal data structure of the Paralation Model is the field. A field is simply a collection of data that can be referred to by an ordinal index. Related fields comprise a paralation, which is short for “parallel relation.” A paralation always includes an index field. A paralation consists of sites, which are similar to the elements of an array; the nth site of a paralation contains the nth field elements of the fields of the paralation. The index field at that site has the value n. When you create a paralation, you create its index field. Additional fields can then be added to the paralation, and each of them contains a pointer to the index field.

Figure 1

Elements of fields in a given paralation that have a particular index are guaranteed to be near each other-that is, the 173rd elements of two fields in the same paralation are near, the 2nd elements are near, etc. This means that intra-site communication is guaranteed to be cheap. Inter-site communication, on the other hand, can be arbitrarily cheap or costly. By default, paralations are “shapeless;” there’s no information regarding the nearness of sites in a paralation to the sites in any other paralation. You can, however, specify the shape of paralations in order to ensure the least costly inter-site communication possible, which may have a dramatic effect on system performance.

When you create a paralation, you automagically create its index field, and in fact, that is what is returned:

A word about the examples is in order here: first, I’m a Lisp hacker, so the examples will all be in Paralation Lisp. A secondary reason for this is that, as of the writing of the edition of The Paralation Model that I own a copy of, the Paralation C compiler had not been completed, and all of the examples in the book are in Paralation Lisp. Perhaps the most important motivation of all, however, is that the book includes a complete “Tiny Paralation Lisp” simulator that will work in any [Steele84] Common Lisp implementation. In case you’re wondering how the simulator can be “complete” and “tiny” at the same time, the answer is that it completely implements the model (remember, it’s only one data structure and three operators), but it doesn’t go miles out of its way to do type checking, error handling, or generate efficient code on a serial machine. Neither does it support shaped paralations, which isn’t really a loss on a serial machine. There is a much better simulator for Common Lisp that you can order from The MIT Press. An order form is included with the book.

Common Lisp aficionados will realize that the #F notation used to represent fields in Paralation Lisp resembles the #A syntax that Common Lisp uses to denote an array. Also like an array, a paralation is made to be a certain length, and all fields in the paralation are of the same length. As the Common Lisp programmer would expect upon seeing the #F representation, fields can be given to the reader as literals, but each field read causes a new paralation to be constructed, so:

because the two objects are not the same object; they are two paralations that happen to consist of fields of the same length containing the same values. This is the only gripe that I have about Paralation Lisp: you cannot tell simply from looking at its printed representation what paralation a field belongs to.

That pretty much covers paralations and their fields, so let’s move on to the Paralation Model operators. They are elementwise evaluation, move, and match.

Elementwise evaluation is exactly what it sounds like: given a field, some evaluation is performed on each of the elements of the field. The result is a new field in the same paralation. The evaluations are done in parallel-correct paralation programs cannot rely on any order of initiation or completion of the evaluation among any of the elements of the field. The only synchronization guarantee that elementwise evaluation makes is that the operator will not terminate until the evaluations of all of the elements have terminated.

Here’s a completely trivial example of elementwise evaluation:

This example obviously isn’t terribly useful; its sole function is to create a new paralation with ten sites, assign the resulting index field to the global variable *foo*, and then to add a new field to the paralation whose elements are the integers one through ten rather than zero through nine by adding one to each index field element in parallel (if you were to run this on an implementation with at least ten processors, this would happen very quickly indeed, ignoring communication costs for now).

There are a few subtleties to the semantics of elwise. One is that elwise can operate on more than one field at a time, which is why the first parameter to elwise is a list. Another is that references to the field name within the body refer to an individual element rather than to the entire field. Still another subtlety is that elwise can support temporary binding in similar fashion to Common Lisp’s let. It’s fairly common to temporarily create a paralation and then want to apply elwise to the resulting index field without having to store it in some variable. An example of rewriting the above code would look something like this:

There aren’t any a priori restrictions on what can be done within the body of an elwise, although there are limitations as to what can be done correctly in the context of elwise’s parallel operation. For example, side effects in the body are perfectly fine:

results in a paralation with an index field suffering from an off-by-one bug (moral: there’s nothing to prevent you from hoisting yourself by your own petard). Note that the fields returned by the last two examples are not the same: the first is a new field added to the paralation; the second is the (incorrectly-formed) index field of the paralation.

One of the remaining Paralation Model operators is the move operator. You can think of it as a parallel assignment. The idea is to move values from one field to another in parallel. Of course, this implies that some way to specify which elements in the source field go into which elements in the destination field exists. This mechanism is called a mapping, and mappings are created by the third and final Paralation Model operator, match.

Match is fairly straightforward: it takes two fields and returns a mapping from one to the other. Any elements not present in both fields are represented as NIL in the mapping. The other elements are handled as follows: the elements in one field are labeled with the index of their first occurrence in the field, and the elements in the other field that match are given that same label. For example:

A picture being worth a thousand words, although I hate drawing:

Figure 2

(At least this is one possible representation of a mapping, and in fact it’s the one used by the Tiny Paralation Lisp system.)

If you’re looking closely at this, remembering that the principle purpose of match is to provide a mechanism for the move operator to use to get the elements of one field to another, you’ll perhaps notice that there are opportunities for a couple of things. One is that one or more elements in the “to” field might not get filled at all. In the figure above, this is represented by a field element with no arrowhead pointing to it, although you should keep in mind that duplicate elements in the “to” field also have no arrows pointing to them-they simply take on the first occurrence of the value in the field. Another situation that can occur is that there might be more than one value to be placed in the same element in the “to” field. This condition is represented by a field element having more than one arrowhead pointing to it. The example above suffers from both of these problems.

The move operator allows you to resolve both of these problems by specifying default values for the cases where no value to be moved in exists, and a combiner function to handle the cases where there’s more than one value to be moved in. Oftentimes you might wish to take a field and combine all of its elements-e.g. you may want a sum of a field of numbers. It’s trivial to write a library function, vref, in terms of the Paralation Model primitives that allows this conglomeration of elements in a field:

The function may not be too easy to understand at first. It checks to see if the length of the field is positive. If so, it uses the move operator (“<-” in Paralation Lisp) with a mapping of all of the elements of the field to the same place, passing in the combiner function. The result is a field of one element, so Common Lisp’s elt is used with a zero parameter to extract the result.

The secret is in the match form. It creates a “from” field consisting of zeros using elwise. These zeros will all map to the same place if the “to” field is simply the field #F(0), and the easiest way to get that is by making a paralation of length one.

A good example of the applicability of these data structures and operators to programming tasks that are normally done sequentially is the Sieve of Eratosthenes, the de facto standard algorithm for finding prime numbers. You can find the serial version of the algorithm in nearly any entry-level computer science text. Most of us are so accustomed to thinking of the Sieve in serial terms that we probably don’t even realize that the algorithm can be expressed in a parallel fashion, and remarkably simply in the Paralation Model:

(1)

(defun find-primes (n)
   (let* ((sieve (make-paralation n))
          (candidate-p (elwise (sieve) (if (> sieve 1) t nil)))
          (prime-p (elwise (sieve) nil)))
     (do ((next-prime 2 (position t candidate-p)))
         ((null next-prime)
          (<- sieve :by (choose prime-p)))
       (setf (elt prime-p next-prime) t)
       (elwise (sieve candidate-p)
         (when (and candidate-p (zerop (mod sieve next-prime)))
           (setf candidate-p nil))))))

The function find-primes takes one parameter, which is the maximum number of primes to find. First it creates the Sieve by making a paralation of size n. Next it creates a field that consists of booleans indicating whether the integer at that index is potentially prime or not (at this point, “potentially prime” is defined as being an integer greater than one). Finally a field of all NILs is created, meaning that initially no values are known to be prime.

Figure 3

A do loop is then entered. This loop binds next-prime to the appropriate value (beginning with 2 and continuing through all elements of candidate-p that are T). The loop is defined to terminate when next-prime is null, and the result is the evaluation of (<- sieve :by (choose prime-p)). Choose is another library function that is easily defined in terms of the primitives:

(2)

(defun choose (field)
  (let ((count 0)
        (from-field (elwise (field) nil)))
    (dotimes (i (length field))
      (when (elt field i)
        (setf (elt from-field i) count)
        (incf count)))
    (match (make-paralation count) from-field)))

Choose is pretty straightforward; it binds count to zero and from-field to a field of NILs, then loops for the length of the incoming field, checking the ith element of the incoming field and, if it is non-NIL, setting the ith element of from-field to the count of non-NIL elements. It then returns a mapping of from-field to a field of a length sufficient to hold only the non-NIL elements.

The value of the do loop in find-primes, then, will be the result of moving sieve (the index field) by the mapping returned by (choose prime-p). The body of the loop is concerned with seeing that prime-p is a field of NILs and Ts, with the indices of the Ts being prime numbers. It is always the case that next-prime is in fact the index of a prime number, so find-primes sets the appropriate element of prime-p to T. It then elwises across sieve and candidate-p, checking first to see if the current element is even a candidate and, if so, whether it’s evenly divisible by next-prime. If it is, then the element is removed as a candidate. Then the loop goes again. The interactions among the fields, especially prime-p and candidate-p, are fairly subtle; don’t feel discouraged if it’s not clear even after several readings why this function works. Hint: you can think of there being two loops (do and elwise), with prime-p being modified by the do loop and candidate-p being modified by the inner elwise.

The point of the algorithm is that finding prime numbers basically consists of checking several numbers against one number to see if they divide evenly or not, and elwise fits the bill very nicely. The loop then climbs, so that the next parallel modulo comparison can occur, and so on.

This is all subtle enough that some more pictures are called for, so let’s meander through an invocation of (find-primes 5). To see the paralation initially created by the let* form, please see Figure 3 above. Keeping in mind that elwise operates in parallel, here’s what happens as we evaluate our example.

The do binds next-prime to 2, and evaluates (setf (elt prime-p next-prime) t), giving:

Figure 4

Now we get to the real meat: the

(3)

(elwise (sieve candidate-p)
  (when (and candidate-p (zerop (mod sieve next-prime)))
    (setf candidate-p nil)))

form. Keeping in mind that references to a field name within an elwise actually refer to the elment, we see that this parallel evaluation will do nothing for element zero, since candidate-p is NIL, so the state doesn’t change; see Figure 4 above. Likewise for element one; candidate-p is also NIL. Things change, however, when we get to element two; candidate-p is T, so (zerop (mod sieve next-prime)) is evaluated. Two modulo two is, of course, zero, so the result of the zerop is T, which causes the (setf candidate-p nil) to be evaluated (see Figure 5). This may seem puzzling at first-after all, two is a trivially prime number, and should therefore seem to remain a candidate-but if you refer to Figure 4 above again, you’ll see that this has already been accounted for in the prime-p field.

Figure 5

Element three is next, and candidate-p is T, so we evaluate (zerop (mod sieve next-prime)) again. This time, three modulo two is one, not zero, so the zerop returns NIL, and the T value of candidate-p is left alone.

Finally we reach element four, and candidate-p is T for it as well, so we evaluate (zerop (mod sieve next-prime)) yet again. Unfortunately for candidate-p, four modulo two is zero, so the zerop returns T, and candidate-p goes NIL:

Figure 6

For the N = 5 case, that’s the end of the elwise. On parallel hardware, each element would presumably have been dealt with at the same time, meaning that the elements of candidate-p would get set very quickly. So finally we go through the do loop again. The binding of next-prime becomes (position t candidate-p), and if you refer to Figure 6 above, you’ll see that at this point, the position of the next T in candidate-p is element three. The (setf (elt prime-p next-prime) t) gets evaluated again, which gives us:

Figure 7

The elwise form is evaluated all over again, this time with next-prime bound to three. Everything gets left alone until element three is examined, at which point candidate-p is T and (zerop (mod sieve next-prime)) is also T, so candidate-p goes NIL again:

Figure 8

Element four is examined, but candidate-p was set NIL by the elwise that was done when next-prime was bound to two, so no change is made, and the elwise ends. The next time through the do loop, however, (position t candidate-p) is NIL, which is the terminating condition for the loop. The result form, (<- sieve :by (choose prime-p)), should be fairly self-explanatory, but in case it’s not, here we go.

I defined choose a few pages back. First it binds count to zero. Next, it adds a new field, from-field, to whatever paralation the parameter is in:

Figure 9

Next is a dotimes loop for the length of the parameter. It searches for non-NIL elements and, when it finds them, it stores the value of count into that element of from-field and increments count. In our case, the result of this is:

Figure 10

Finally, choose returns (match (make-paralation count) from-field). At this point, count is bound to 2, so the result of that is a new paralation with an index field of #F(0 1). The result of the match, then, is the mapping:

Figure 11

As you might expect, the <- operator applied to the sieve field with this mapping results in a field of #F(2 3), which is in fact a field containing all of the prime numbers from zero to four.

I believe that that pretty much covers what I wanted to say about the Paralation Model. It’s small, it’s clean, and it’s powerful. I hope that you’ve enjoyed your glance at it and that it’s given you food for thought as to the future of computing using architectures other than the traditional Von Neumann approach. The book goes into much more detail, of course, and comes highly recommended for those readers who might be curious about an elegant model for parallel computation. A special word of thanks is due here to Gary Sabot, creator of the Paralation Model, who kindly reviewed this article and convinced me that the figures were a necessary evil.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Latest Forum Discussions

See All

Six fantastic ways to spend National Vid...
As if anyone needed an excuse to play games today, I am about to give you one: it is National Video Games Day. A day for us to play games, like we no doubt do every day. Let’s not look a gift horse in the mouth. Instead, feast your eyes on this... | Read more »
Old School RuneScape players turn out in...
The sheer leap in technological advancements in our lifetime has been mind-blowing. We went from Commodore 64s to VR glasses in what feels like a heartbeat, but more importantly, the internet. It can be a dark mess, but it also brought hundreds of... | Read more »
Today's Best Mobile Game Discounts...
Every day, we pick out a curated list of the best mobile discounts on the App Store and post them here. This list won't be comprehensive, but it every game on it is recommended. Feel free to check out the coverage we did on them in the links below... | Read more »
Nintendo and The Pokémon Company's...
Unless you have been living under a rock, you know that Nintendo has been locked in an epic battle with Pocketpair, creator of the obvious Pokémon rip-off Palworld. Nintendo often resorts to legal retaliation at the drop of a hat, but it seems this... | Read more »
Apple exclusive mobile games don’t make...
If you are a gamer on phones, no doubt you have been as distressed as I am on one huge sticking point: exclusivity. For years, Xbox and PlayStation have done battle, and before this was the Sega Genesis and the Nintendo NES. On console, it makes... | Read more »
Regionally exclusive events make no sens...
Last week, over on our sister site AppSpy, I babbled excitedly about the Pokémon GO Safari Days event. You can get nine Eevees with an explorer hat per day. Or, can you? Specifically, you, reader. Do you have the time or funds to possibly fly for... | Read more »
As Jon Bellamy defends his choice to can...
Back in March, Jagex announced the appointment of a new CEO, Jon Bellamy. Mr Bellamy then decided to almost immediately paint a huge target on his back by cancelling the Runescapes Pride event. This led to widespread condemnation about his perceived... | Read more »
Marvel Contest of Champions adds two mor...
When I saw the latest two Marvel Contest of Champions characters, I scoffed. Mr Knight and Silver Samurai, thought I, they are running out of good choices. Then I realised no, I was being far too cynical. This is one of the things that games do best... | Read more »
Grass is green, and water is wet: Pokémo...
It must be a day that ends in Y, because Pokémon Trading Card Game Pocket has kicked off its Zoroark Drop Event. Here you can get a promo version of another card, and look forward to the next Wonder Pick Event and the next Mass Outbreak that will be... | Read more »
Enter the Gungeon review
It took me a minute to get around to reviewing this game for a couple of very good reasons. The first is that Enter the Gungeon's style of roguelike bullet-hell action is teetering on the edge of being straight-up malicious, which made getting... | Read more »

Price Scanner via MacPrices.net

Take $150 off every Apple 11-inch M3 iPad Air
Amazon is offering a $150 discount on 11-inch M3 WiFi iPad Airs right now. Shipping is free: – 11″ 128GB M3 WiFi iPad Air: $449, $150 off – 11″ 256GB M3 WiFi iPad Air: $549, $150 off – 11″ 512GB M3... Read more
Apple iPad minis back on sale for $100 off MS...
Amazon is offering $100 discounts (up to 20% off) on Apple’s newest 2024 WiFi iPad minis, each with free shipping. These are the lowest prices available for new minis among the Apple retailers we... Read more
Apple’s 16-inch M4 Max MacBook Pros are on sa...
Amazon has 16-inch M4 Max MacBook Pros (Silver and Black colors) on sale for up to $410 off Apple’s MSRP right now. Shipping is free. Be sure to select Amazon as the seller, rather than a third-party... Read more
Red Pocket Mobile is offering a $150 rebate o...
Red Pocket Mobile has new Apple iPhone 17’s on sale for $150 off MSRP when you switch and open up a new line of service. Red Pocket Mobile is a nationwide MVNO using all the major wireless carrier... Read more
Switch to Verizon, and get any iPhone 16 for...
With yesterday’s introduction of the new iPhone 17 models, Verizon responded by running “on us” promos across much of the iPhone 16 lineup: iPhone 16 and 16 Plus show as $0/mo for 36 months with bill... Read more
Here is a summary of the new features in Appl...
Apple’s September 2025 event introduced major updates across its most popular product lines, focusing on health, performance, and design breakthroughs. The AirPods Pro 3 now feature best-in-class... Read more
Apple’s Smartphone Lineup Could Use A Touch o...
COMMENTARY – Whatever happened to the old adage, “less is more”? Apple’s smartphone lineup. — which is due for its annual refresh either this month or next (possibly at an Apple Event on September 9... Read more
Take $50 off every 11th-generation A16 WiFi i...
Amazon has Apple’s 11th-generation A16 WiFi iPads in stock on sale for $50 off MSRP right now. Shipping is free: – 11″ 11th-generation 128GB WiFi iPads: $299 $50 off MSRP – 11″ 11th-generation 256GB... Read more
Sunday Sale: 14-inch M4 MacBook Pros for up t...
Don’t pay full price! Amazon has Apple’s 14-inch M4 MacBook Pros (Silver and Black colors) on sale for up to $220 off MSRP right now. Shipping is free. Be sure to select Amazon as the seller, rather... Read more
Mac mini with M4 Pro CPU back on sale for $12...
B&H Photo has Apple’s Mac mini with the M4 Pro CPU back on sale for $1259, $140 off MSRP. B&H offers free 1-2 day shipping to most US addresses: – Mac mini M4 Pro CPU (24GB/512GB): $1259, $... Read more

Jobs Board

All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.