0
$\begingroup$

This question is for resource or explanation generalizing or simplifying the ideas of parallel computers, cellular automata, and multi-agent architectures. I am interested in the requirements for simulating a parallel architecture on a standard computer. Specifically, what the components are and the basic algorithm is for doing so. But it seems like there is no standard model of parallelism, and it seems related to cellular automata and multi-agent architectures.

First, from Wikipedia:

Parallel computing is closely related to concurrent computing—they are frequently used together, and often conflated, though the two are distinct: it is possible to have parallelism without concurrency (such as bit-level parallelism), and concurrency without parallelism (such as multitasking by time-sharing on a single-core CPU).

I am not sure if I am considering concurrency vs. parallelism, or if I need bit-level, data-level, or task-level parallelism. I am also confused by all the many parallel architecture types, so not sure what to pick. Which is why this question is about the different parallel architecture types.


Some notes:

In terms of data:

  • SISD: Single Instruction Single Data (standard sequential computer)
  • SIMD: Single Instruction Multiple Data (gpu, same instruction but each processor has its own data)
  • MISD: Multiple Instruction Single Data (don't know why you would need this, not really interested)
  • MIMD: Multiple Instruction Multiple Data (each processor executes its own program)

In terms of memory:

  • UMA: Uniform Memory Access (processors share memory)
  • NUMA: Non-Uniform Memory Access (each processor has its own memory).

In terms of parallelism:

  • ILP: Instruction-Level Parallelism (multiple instructions from single instruction stream evaluated concurrently)
  • TLP: Thread-Level Parallelism (or Task-Level Parallelism) (not sure the difference)
  • DLP: Data-Level Parallelism (single instruction on different data)

https://computing.llnl.gov/tutorials/parallel_comp/parallelClassifications.pdf


My conception/working definition of parallelism for this context is a machine with many processors all working on the same underlying set of data (the same underlying model, i.e. a shared memory), similar to how one might think of the brain doing, where each neuron is a processor, or how a cellular automaton works, where each cell is a processor. What I am not sure about (and what this question is partly asking about) is how these processors are related to each other (i.e. how they communicate with each other).

Essentially, I would like for all processors to perform a "memory read" at the same time (used to perform their next operation), and then afterward a "memory write" at the same time (the result of the operation), so that during the memory read, they all read from the same memory state before anyone has modified the memory for that time step. In addition, I don't want the parallelism to necessarily be "scaling up", where every processor is doing the exact same thing. I would like for each processor to be doing its own thing, whether or not that means doing the same thing as another processor.

The question is, how to model such a system. If that is too broad of a question, then a resource/reference request for a description on how to model it. Not sure if it is as extreme as a multi-agent architecture.


To summarize, it seems there are 3 related things that all have roughly the same structure:

  • Parallel Computers.
  • Multi-Agent Architectures.
  • Cellular Automata.

They all have:

  • Processors $P$
  • Memories $M$
  • Data $D$
  • Instructions $I$
  • Signal/event/message passing $S$

I am wondering if there is one general model of all of these, and what it is. Or if not an explanation, a resource explaining a simplified version.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.