Sunday, September 2, 2007

Fine-Grain Reactive Parallelism Is Faster than Thread-Based Parallelism

Most programmers are familiar with the concept of polling. Essentially, a program repeats a loop over and over until a condition is met that triggers a reaction. The problem is that looping unnecessarily wastes CPU cycles, especially in a multithreaded system. In a reactive system, by contrast, there is no polling, which means that there is no need to use loops to test conditions. A pure reactive system is based on change. It is the ultimate event-based paradigm because nothing happens unless something changes. Rather than use polling, the process that changes a variable knows to notify each and every part of the program that might be affected by the change.

In COSA, reactivity is implemented with the use of sensors (comparison operators) and effectors. Effectors know which sensors are likely to be affected by a change to their assigned variables. The result is that event/data dependencies are automatically enforced by the system, thus leaving nothing to chance. The beauty of this is that modifications to a legacy system cannot introduce unknown side effects or bad assumptions that may lead to failures down the road.

Fine-grain parallelism is much more desirable, performance wise, than coarse-grained parallelism because it makes it possible to parallelize many things that are not parallelizable using light weight threads. For example, any initialization procedure whereby many variables in a table are assigned their initial values can be completely done in parallel in a fine-grain parallel system. These are things that multicore CPU designers need to consider. Do they really want the speed, reliability and scalability advantages of fine-grain reactive parallelism or do they just want to retain compatibility with existing development tools even though they are hard to use in a parallel environment? The choice should be obvious.


snakenerd said...

In any case, I think nobody uses polling to synchronize threads. Everybody is aware of the existence of condition variables and mutex locks, which spend no CPU clocks except for the locking mechanism and context switching. Not to defend the usage of threads or algorithms hehe :)

-- Fred

Louis Savain said...

True, but polling (if ...then) may be used internally within an inner loop and that wastes cycles. By the way, timing is so constrained and deterministic in a COSA environment, there is really no need for mutex locks. Of course, there is no context switching either. The end result is fast parallelism. The only disadvantage so far is that current CPUs do not support it. But that will change soon enough.

snakenerd said...

In any case, a system designed to achieve massive parallelism is to be much better than using threads and locks. It complicates the code way too much. You gotta be an expert to use them right hehe.

And condition variables are much like your sensor mechanism: threads are notified that some condition variable has changed and wake up to do something about it. It is efficient but still very complicated to keep track. Even more being textual instead of visual.

Potatoman said...

You would have to be a muppet to using polling with threads. You are setting up a straw man here.

Louis Savain said...

You would have to be a muppet to using polling with threads. You are setting up a straw man here.

No. As I said, polling is not limited to inter-thread communication. Let's say you have a thread that is sent a message regularly, or a fucntion that is called periodically to do something. The reaction may include testing the condition of one more variables in order to make a decision. That, too, is a form of polling.

The beauty of a purely reactive system is that state changes need only be tested once, i.e., when the change actually happens.

David Hopwood said...

Polling is often used in cases where it has no significant effect on performance. Of course, the infrastructure should, and almost always does, support mechanisms for reacting to changes without polling, and probably those mechanisms should be the default. But asserting that polling should never be used for performance reasons is just premature optimization.

"The beauty of a purely reactive system is that state changes need only be tested once, i.e., when the change actually happens."

In general, it is once for each component that is monitoring each change.