Important Parts—Midterms

Flynn's taxonomy is crucial lec 2 - Flynn's taxonomy

This classification system categorizes computer architectures by their concurrent instruction and data streams into four distinct models:

SISD (Single Instruction, Single Data): Sequential processing where one instruction handles one data stream, typical of classic single-core computers.
SIMD (Single Instruction, Multiple Data): Parallel processing where one instruction simultaneously hits multiple data streams, used in GPUs. It relies on a front-end host computer controlling an array of processing elements.
~~MISD (Multiple Instructions, Single Data): A largely theoretical or highly specialized model where different instructions operate on a single data stream, often used for fault tolerance.~~
MIMD (Multiple Instructions, Multiple Data): Independent parallel processing where multiple processors execute different instructions on different data sets, standard in modern multi-core CPUs and supercomputers.

Term	Definition
Bus	A shared communication pathway used to transfer data between processors, memory, and other components.
Synchronous	Operating on a predictable, predetermined time schedule.
Asynchronous	Operating based on the immediate readiness of devices and availability of data, rather than a fixed clock.
Contention	A conflict that occurs when multiple processors attempt to access the single shared bus at the same time.
Arbitration	The logical system used to resolve bus contention by deciding which processor gets priority access.

Feature	Bus-Based Networks	Switch-Based Networks
Basic Structure	The simplest way to connect multiprocessor systems, utilizing either a single shared bus or multiple parallel buses.	Utilizes Switching Elements (SE) configured in crossbar, single-stage, or multistage networks.
Concurrency	In a single bus system, only one processor can access the bus, and only one memory access can take place at any given time.	Crossbar networks provide simultaneous connections among all inputs and outputs.
Contention & Routing	Requires bus arbitration logic and handshaking to resolve bus contention when multiple processors compete for access.	Routing can be achieved via direct switch settings or self-routing based on the destination address (in MINs).
Network Blockage	Both single and multiple bus systems are blocking networks.	Crossbars are non-blocking networks, whereas Multistage Interconnection Networks (MINs) can experience blockage (or be rearrangeable).
Delay Complexity	O(N) for a single bus and O(mN) for multiple buses.	O(1) for crossbars and O(logN) for MINs.
Cost Complexity	O(1) for a single bus and O(m) for multiple buses.	O(N^2) for crossbars and O(NlogN) for MINs.

In terms of speed, a scalable system is capable of increasing its speed in proportion to the increase in number of processors.
In terms of efficiency, a parallel system is scalable if its efficiency is kept fixed as the number of processors is increased.

Cache-Memory Coherence (Updating Global Memory)

this handle the choice regarding a process affect on the global memory

Write-Through: Every time a processor updates its cache, the global memory is updated at the exact same time.
Write-Back: The cache is updated immediately, but the global memory is only updated much later when that specific block of data needs to be removed (replaced) from the cache to make room for something new.

The Write-Once protocol combines both:

The very first write to a block uses Write-Through (updating main memory and invalidating other caches).
All subsequent writes to that same block use Write-Back (updating locally in the cache without touching memory or flooding the bus).
It strictly uses Write-Invalidate cache-cache coherence.

Cache-Cache Coherence (Handling Other Processors' Caches)

this handle the choice regarding a process affect on another process cache

Write-Invalidate: Processors can read from their local caches safely until one processor writes new data. When a write occurs, the system marks all copies of that data in other processors' caches as invalid, forcing them to fetch the new version if they need it again.
Write-Update: When a processor writes new data, it immediately broadcasts that update to all other copies in all other caches to maintain consistency.

Real shared memory systems combine these approaches to maintain overall coherence, resulting in four possible combinations (e.g., Write-Invalidate with Write-Through, or Write-Update with Write-Back)