Homework 9: Advanced Concepts in Computer Architecture and Parallel Processing

ASU-Tempe Campus

SER 232 – Computer Systems Fundamentals

Summer 2019

Homework 9

1. Why was the RISC architecture concept proposed?

Reduced Instruction Set Computer (RISC) architecture has been proposed to make instructions

sets less complicated and more efficient. Conventional Complex Instruction Set Computer

(CISC) designs had become more complex and most of the specifications seldom were

implemented in practice. RISC set forth to simplify the process of designing a processor in that

more emphasis should be made on fewer and simpler instructions capable of being fast and

efficient. This enabled more rapid execution of instruction, less as well as less complex

hardware. RISC established systems were able to perform more efficiently on a clock cycle

because they were designed to run fast and not rich with instructions. It was also easier to

optimize compiler because every instruction executed a simple task that was very easy. The

proposal was based on the research that revealed that the compilers mainly utilized a minor part

of available CISC instructions meaning that simpler sets of instructions could give better

outcomes (Null and Lobur, 2014). In such a way, RISC was unveiled to give the optimal

performance with minimum redundant complexity in designing the processor.

2. Why is a RISC processor easier to pipeline than a CISC processor?

RISC processor is less difficult to pipeline as its instructions are same in size and time execution

and as such, the interaction between instructions become less linear and more predictable. Based

on this, CISC processors also include variable-length and complex instructions, which are

possibly multiple cycles or micro-operations to finish, posing a problem to overlapping steps on

a pipeline. The simplicity of RISC enables every instruction to later traverse efficient pipeline

phases namely fetch, decode, execute, memory access and write-back without introducing

unpredictable delays. Such regularity guarantees a reduced number of hazards and makes it

easier to control pipelines. Moreover, the RISC instructions can typically operate on simple

operations on registers as opposed to memory, which further minimizes possible bottlenecks in

the pipeline. Consequently, the throughput of instruction is also enhanced and as well as the

efficiency of the pipeline is optimized. The simplicity of the RISC sets of instructions is one key

reason why it is easy to design high performance pipelined processors (Null & Lobur, 2014). In

this way, RISC designs have a higher and more predictable speed of instruction execution

compared to CISC architecture.

3. Describe how register windowing makes procedure calls more efficient.

wasted swapping on and off registers contents to memory. In the case of traditional architectures,

procedure call and is a very expensive overhead. RISC architecture If the register file is

partitioned into overlapping groups or windows where each window relates to the context of a

particular procedure, then register windowing is said to be the default state of the architecture.

Upon invoking a procedure, the processor will just change the current window pointer to a new

collection of registers enabling it to immediately gain access to new registers without any

operation on memory. Shared regions allow the exchange of parameters between procedures to

be done efficiently because the input and output registers can be shared between primarily the

caller and the callee. This design significantly minimizes the memory trafficking and accelerates

the speed at which functions are called which proves to be of great importance to applications

that are performance-intensive (Null & Lobur, 2014). Register windowing is, therefore, helpful

in the RISC systems to improve speed of execution and processor efficiency.

4. Flynn’s taxonomy classifies computer architectures based on two properties. What are they?

The taxonomy created by Flynn categorizes computer architectures based on two major

properties the number of streams of instructions and the number of streams of data that are being

processed simultaneously. This is known as a classification division that the systems are

classified based on four modes of systems and these are SISD, SIMD, MISD, and MIMD. SISD

is symbolic of conventional types of sequential computers, whereas SIMD is used to characterize

other systems such as a vector processor, which executes the same activity on a number of data

items at once. MISD architectures are uncommon and multiple instructions act on the identical

data but MIMD systems allow real parallelism where multiple processors act on dissimilar data

sets. It is a taxonomy that serves to explain the degree of parallelism and parallelism in computer

systems (Null and Lobur, 2014). It continues to form the part of computer architecture, by

providing the design conceptualization and the comparison of parallel processing abilities of

different hardware systems.

5. We propose adding a level to Flynn’s taxonomy. What is the distinguishing characteristic of

computers at this higher level?

A further grade above the taxonomy proposed by Flynn would be systems able to support

massive parallelism and dynamically distribute instruction, like those in current cloud or

quantum computing systems. Such architectures do not just handle several streams of instruction

and data, but they can also adeptly allocate the computing resources among the distributed nodes

or cores. Compared with the classical MIMD systems, the new level would be characterized by

adaptive task scheduling, heterogeneous processors and massively interconnected with the ability

to support thousands or millions of parallel processes. This kind of architecture incorporates

artificial intelligence to maximize resources and provide fault tolerance which makes this kind of

architecture unprecedentedly scalable. The conspicuous difference lies then in independent

parallelism control the capacity of the system that balances workloads dynamically without the

need to declare it by a programmer (Null and Lobur, 2014). With the emergence of the exascale

and distributed AI system computing, including this extension to the Flynn taxonomy is more

appropriate to indicate the architecture of highly adaptive, intelligent, and massively parallel

computing systems.

6. Do all programming problems lend themselves to parallel execution? What is the limiting

factor?

Not every programming task can be executing in parallel since there are those tasks that are

always sequential. Task problems that require the results of posters to be computed cannot

readily be broken down into subtasks that can be done concurrently. It is the most common

dependency where every other data relies on it and is known as data dependency or sequential

dependency. Also, parallel efficiency can be further diminished by synchronization overhead,

communication latencies and load inequity between processors. The Law of Amdahl states that

the maximum acceleration which can be achieved by parallel processing can only be equal to the

part of the program which cannot be done parallel. Despite the high number of processors, the

serial fraction makes the performance improvement of the processors limited. Thus, parallel

execution is only advantageous to programs that have a high level of independent computations

(Null & Lobur, 2014). The parallelization needs to be adjusted effectively, the algorithm needs to

be reorganized, and the hardware needs to support this approach to keep inter-process

communication as low as possible and maximize the concurrent implementation of tasks.

7. Define superpipelining.

A technique to boost traditional processor pipeline throughput involves splitting the processor

pipeline into more stages than found in traditional processor design, and letting multiple

instructions be in different phases of execution simultaneously. The clock cycle may be

shortened by decreasing the time-per-story through the pipeline, and additional instructions may

be moved through in a unit of time. Nevertheless, this design is also likely to augment the

possibility of hazards like data, control, and structural conflicts. To resolve it, high-level hazard

detection and forwarding systems are used. Superpipelined architectures strive to boost the

performance of a computer without increasing the complexity of the instruction set or increasing

processor hardware to an extent that is unreasonable. They are a development of the simplest

pipelining concept, and they enhance the speed of the clock and efficiency of the overall flow of

instructions (Null and Lobur, 2014). Superpipelining therefore enables processors to use finer-

grained parallelism in the execution of instructions, increasing performance by permitting an

increasing number of instructions to be staying in the pipeline.

8. How is a superscalar design different from a superpipelined design?

Although both the superscalar and superpipelined architecture targets to boost the instruction

throughput, they achieve this in entirely different modes. A superpipelined processor breaks up

the execution of instructions into additional steps to allow faster clock rates and increased

overlapping of instructions. Conversely, a superscalar design uses many execution units, and

many instructions can be issued and executed in a given clock cycle. The processors are based on

the superscalar processors which utilize instruction level parallelism, which dynamically

analyzes the dependencies to identify what instructions can be executed simultaneously. This is a

method that augments the throughput without the need of necessarily enriching the pipeline.

Super pipelining is a performance technique that speeds performance by upgrading clock

frequency whereas the overscalar design does so by creating several paralleled fences.

Combining them, they are complementary measures of enhancing the processor speed (Null &

Lobur, 2014). To sum up, super pipelining is aimed at focusing more on depth and speed of

pipelines and superscalar architecture is aimed at focusing on the number of instructions

executed per cycle.

9. In what way does a VLIW design differ from a superpipelined design?

The reason why a Very Long Instruction Word (VLIW) design is different than a superpipelined

design is in the way parallelism is handled. In VLIW architecture, the compiler explicitly assigns

independent instructions which should be run in parallel under one long instruction word. In

every word, there are many operations that are supposed to serve different functional units and

can be performed simultaneously. This replaces the hardware complexity of parallel scheduling

with software complexity. By comparison, a superpipelined architecture uses hardware to exploit

fine-grained time-parallelism through breaking down the pipeline into smaller steps and higher

clock speed. Although both are directed at the improvements in performance, VLIW reduces to

the emphasis on compiler-based parallelism and deterministic execution, the superpipelining is

focused on the throughput of instructions increased by improving their timing by the hardware

(Null & Lobur, 2014). Therefore, the VLIW architectures have simplified control hardware

because this relies heavily upon the high level optimization of the compilers, whereas the

superpipelined processors maintain more hardware complexity to do the dynamic execution

control.

10. What are the similarities and differences between EPIC and VLIW?

The explicit Parallel Instruction computing (EPIC) and the Very Long Instruction Word (VLIW)

architecture arrays both have an aim of exploring the parallelism at the instruction level by

enabling multiple operations to be performed at the same time. They both have long instruction

words which combine a number of independent operations to be done in parallel. They however

vary in the manner they deal with instruction scheduling and parallelism detection. In VLIW,

parallelism of instructions is determined in advance by the compiler, necessitating that perfect

scheduling during compile time is done. Similar to EPIC, hardware features introduced by

hardware in rooted in the concept include speculation, predication, and dynamic grouping of

instructions to facilitate flexibility and runtime efficiency. These extensions will allow VLIW to

overcome the inflexibility and reliance on the ideal compile-time scheduling. EPIC is, therefore,

a development of VLIW, comprising of compiler-aided and hardware-aided parallelism in more

optimized performance and flexibility (Null & Lobur, 2014). Although their main goal is to

maximize throughput, EPIC is more scaled and efficient in the workloads of complex real world.

11. Explain the limitation inherent in a register-register vector processing architecture.

A register-register vector processing architecture hampers the development of higher

performance levels because of its strong dependence on the loading of vectors into registers prior

to the start of computation. This limitation reduces the number of concurrent operations when the

space available in the register is not enough for large data sets. The architecture necessitates

frequent loading and storing between memory and registers, which leads to increased data

transfer overhead and slower execution (Null & Lobur, 2014). As operations are limited to

registers, performance decreases when processing vectors that are larger than the register

capacity. Besides that, the design relies on compiler efficiency to arrange data transfers in an

optimal way, and badly optimized code may result in bottlenecks and lower throughput (Null &

Lobur, 2014).

Another constrained aspect is the complexity of the hardware and its scalability. The large, fast

registers required for handling long vectors take up a considerable amount of space on the chip

and consume a significant amount of power, thus limiting the scalability for high-performance

applications (Null & Lobur, 2014). Also, the design has difficulty dealing with irregular or non-

sequential data, such as sparse matrices or data sets that change dynamically, hence it is

inefficient for general-purpose computing. These issues limit the adoption of the technology to

highly structured, predictable workloads such as scientific computations or signal processing

tasks (Null & Lobur, 2014). Therefore, while the register-register architecture may be an

efficient one for certain operations, its inflexibility and high memory-transfer demands make it

less suitable for broader computational domains.

12. Give two reasons for the efficiency of vector processors.

Vector processors can be extremely efficient by exploiting data-level parallelism, hence one

single instruction can be performed on multiple data elements at the same time. Such a strategy

leads to the minimization of instruction fetches and decodes, thus the control overhead is reduced

and the execution of repetitive computations can be a lot faster (Null & Lobur, 2014). In fact,

vector processors achieve the best hardware utilization by performing whole arrays of data in a

single instruction cycle. It is their pipelined execution that enables even higher performance

since it allows different stages of different operations to be executed on different data elements

thus the functional units which are under different stages of the pipeline are rarely idle (Null &

Lobur, 2014). This architecture is perfectly suitable for scientific and engineering applications in

which the same operations are carried out over large datasets.

Another efficiency benefit stems from memory handling that is optimized. Vector processors

implement stride-based memory access in conjunction with interleaved memory banks, thereby

they can eliminate the delays occuring due to the fetching of non-contiguous data (Null & Lobur,

2014). By using these methods the memory latency is minimized and bandwidth utilization is

maximized and thus memory can be a continuous stream of data to the processor. Hence, vector

processors become very powerful in computationally intensive tasks such as weather modeling,

graphics processing, and matrix manipulation where throughput is of utmost importance (Null &

Lobur, 2014). The performance of the vector processors in predictable, data-parallel applications

is at a higher level due to the combined effect of the expedited execution of the instruction

stream and the efficient memory architecture.

13. Draw pictures of the six principal interconnection network topologies.

Null and Lobur (2014) introduced six different principal topologies for interconnection networks,

which include bus, crossbar, ring, star, mesh, and hypercube. While illustrations show these most

clearly, they can also be grasped conceptually. In the bus topology, all processors are connected

to a single shared line, which is a straightforward method but can get congested if there are many

devices communicating at the same time (Null & Lobur, 2014). On the other hand, the crossbar

topology offers a dedicated path between every processor-memory pair, thus, enabling

simultaneous communication but demanding a lot of hardware connections.

In the ring topology, the nodes are connected in a loop, and the data moves sequentially from one

processor to another thus, the speed is moderate, and the communication is predictable. The star

topology routes all communication through a hub, making control easy but, at the same time,

creating a possible single point of failure (Null & Lobur, 2014). In the case of the mesh topology,

processors are linked in a grid fashion thus, more routes are available, and the system is highly

fault-tolerant whereas, in a hypercube, processors are linked in multi-dimensional cubes thus, it

is highly scalable and the communication paths are short (Null & Lobur, 2014). These

topologies, on one hand, weigh the pros and cons concerning cost, speed, and reliability. The

designers choose the topology that is compatible with the system requirements, taking into

account the number of processors, communication bandwidth, and fault tolerance necessary to

create the efficient parallel processing environments.

14. There are three types of shared memory organizations. What are they?

There exist three fundamental different shared memory organizations that are based on Uniform

Memory Access (UMA), Non-Uniform Memory Access (NUMA), and Cache-Only Memory

Architecture (COMA). In the case of Uniform Memory Access (UMA) systems, memory is

shared among all processors in a uniform manner, i.e., each processor is subjected to the same

memory access latency irrespective of the memory location (Null & Lobur, 2014). Though UMA

systems are easy to program, they do not scale beyond a certain number of processors thus

creating memory bottlenecks. Whereas in NUMA systems, each processor is allocated the

memory that is local to it and is, therefore, given faster access to it while the remote memory is

made available for shared access (Null & Lobur, 2014). NUMA architectures though more

complex, better the overall performance of distributed applications.

In fact, COMA is a NUMA extension that removes the constraint of a fixed home location for

the data and allows blocks to be migrated dynamically to the processors that access them most

frequently (Null & Lobur, 2014). Latency is reduced and data locality is improved thereby. On

the downside, managing dynamic data movement being complicated increases the cost of the

hardware and creates software synchronization challenges (Null & Lobur, 2014). UMA is best

suited for a small-scale multi-processor while NUMA would better serve larger systems and

COMA is an excellent choice for the highly parallel environment that require an adaptive data

distribution. These memory organizations define a series of shared-memory architectures that

differ in the factors of performance, scalability, and design complexity.

15. Describe one of the cache consistency protocols discussed in this chapter.

MESI is a popular example of a cache consistency scheme that stands for Modified, Exclusive,

Shared, and Invalid. The protocol keeps the caches of processors consistent by not allowing any

memory block to be changed without reflecting the change in other caches as well (Null &

Lobur, 2014). A cache line could be in one of the four states: Modified (the data is changed but

has not been written back to main memory), Exclusive (only one cache has the data, and it is a

clean copy), Shared (the data block is present in several caches), and Invalid (the data block is no

longer valid). By using this system, the cache can be managed efficiently, and the number of the

data transfers that are not needed can be limited (Null & Lobur, 2014).

MESI uses bus-snooping to achieve this, where caches keep an eye on the bus to find any

changes that other processors may have done. So that if a cache changes a piece of data, the rest

of the caches get the message that they should invalidate or update their copies in their caches

(Null & Lobur, 2014). In this way, data integrity is guaranteed in all processors, thus, no stale

reads can occur. The complexity of the hardware is increased with the protocol, but the

performance in a multiprocessor system is vastly improved as the caches can maintain coherence

dynamically (Null & Lobur, 2014). MESI is one of the widely used coherence protocols in

multicore processors of the present time because it is able to provide a good balance between

efficiency and consistency.

16. What is SETI and how does it use the distributed computing model?

The Search for Extra-Terrestrial Intelligence (SETI) project is basically a one-in-a-billion search

that utilizes radio telescopes to check the universe for signs of alien life. To manage such a

massive digital task, SETI chose to split the work among a lot of smaller parts of a large network

of computers worldwide through the SETI@home program, which obtains the idle computing

power of millions of volunteer PCs worldwide (Null & Lobur, 2014). Simply put, the SETI

initiative breaks down the huge data trove into even smaller pieces so that the independent

machines can each scan one of the pieces thereby, it is a very effective way of turning the

combined network into a theoretical supercomputer (Null & Lobur, 2014). With such a

distributed device, SETI can perform an exhaustive search for a possible extraterrestrial signal at

a small fraction of the cost of a few very powerful machines.

After the work is completed, the machines transfer their results to a central server for integration

and checking (Null & Lobur, 2014). The method here is a volunteer-based distributed computing

model which can be drastically shortened in time to accomplish large-scale scientific research

and at the same time the cost of the research is decreased. By tapping into the global computing

power, SETI is able to do the analysis of petabytes of data in a fraction of the time that it would

normally take (Null & Lobur, 2014). The primary reason behind the success of SETI@home was

that it led to the creation of similar projects in the fields of health sciences, molecular modeling,

and environmental research, thus, it sent a strong message about the far-reaching distributed

computing possibilities in solving hard problems that are complex and data-intensive.

17. What differentiates dataflow architectures from “traditional” computational architectures?

Dataflow architectures are different from typical von Neumann architectures in that they use data

availability, rather than program order, to control instruction execution. In a dataflow machine,

operations are carried out as soon as their input data are available, thus allowing for massive

parallelism and efficient resource utilization (Null & Lobur, 2014). Dataflow systems do not use

a program counter to fetch and execute instructions sequentially. Instead, they depict

computation as a graph of nodes, with data "tokens" flowing along edges. Hence, dataflow

machines eliminate sequential dependencies, thereby decreasing the waiting time and increasing

the level of concurrency (Null & Lobur, 2014).

Additionally, dataflow architectures do away with the notion of a global memory state. Rather,

they function asynchronously, with local communication between processing nodes (Null &

Lobur, 2014). This provides the possibility of fine-grained parallelism; however, it also

necessitates the presence of specialized hardware for handling data tokens and synchronization.

Traditional architectures, which are generally powerful in areas of general-purpose computation,

whereas dataflow systems are the ones to be used in situations where there are well-defined data

dependencies, like digital signal processing or scientific simulation (Null & Lobur, 2014). The

difference is in the way the control works: von Neumann designs depend on instruction

sequencing, while dataflow designs are data-driven execution.

18. What is reentrant code?

Rentrant code is a program or routine that can be interrupted and re-entered by another process

without affecting the execution of the program and without causing data corruption. It does this

by not using global or static variables and placing all temporary data in local stack frames (Null

& Lobur, 2014). As it does not keep state between calls, a reentrant code can be run by several

threads at the same time, thus it is a very good multitasking environment and operating system

kernels (Null & Lobur, 2014). In this way, the system remains stable even when there is

concurrent access, which is very important for real-time and embedded systems.

Creating reentrant code involves a great deal of focus on thread safety and memory usage.

Functions should not change shared resources if synchronization is not ensured (Null & Lobur,

2014). Libraries and APIs that are designed for concurrent use normally implement reentrancy

principles to be free from race conditions. Reentrant code is a step towards modular and scalable

software design as it guarantees that functions will be executed in any order and will not affect

each other thus they will be predictable (Null & Lobur, 2014). It is the basis for stable concurrent

programming in modern systems.

19. What is the fundamental computing element of a neural network?

The main computing unit in a neural network is an artificial neuron, which is commonly called a

perceptron. In detail, each neuron accepts the input signals, multiplies them with the associated

weights, adds the results, and then, to figure out the output, applies an activation function (Null

& Lobur, 2014). The output thus obtained is communicated to other neurons, which, by the

layers they form, interconnect and process complex data patterns. The power of neural networks

to efficiently represent non-linear functions stems from the combination of the neuron’s simple

mathematical model and massive interconnections (Null & Lobur, 2014). This is the base that

supports the enormous range of today’s applications, e.g., speech recognition and computer

vision.

During training, each neuron modifies its weights based on the error signal it gets, thus enabling

the network to learn from data (Null & Lobur, 2014). Neurons in a layered structure are able to

achieve hierarchical feature extraction, that is, they gradually identify more and more abstract

patterns. Such a distributed computation model, as used in the brain, allows for parallel

processing and fault tolerance (Null & Lobur, 2014). The artificial neuron’s feature of being able

to closely model the complex relationships between inputs and outputs is what makes it the core

unit for any neural architecture, even those of deep learning type.

20. Describe how neural networks “learn.”

Neural networks alter their internal weights in such a way as to minimize the difference between

the predicted outputs and the actual results. This operation, referred to as training, is achieved by

exposing the network to a vast number of examples, and using an optimization algorithm,

generally backpropagation, to compute and propagate the error gradients (Null & Lobur, 2014).

Each iteration adjusts the weights, thereby increasing the accuracy step by step. By running this

operation throughout numerous epochs, the network discovers statistical relationships in the data,

which in turn enables it to generalize new, previously unseen examples (Null & Lobur, 2014).

This way, learning turns a neural network into a structure capable of intelligent prediction from a

mere untrained one.

The learning mechanism may be supervised, unsupervised, or reinforced, contingent upon the

type of data and the aim (Null & Lobur, 2014). In supervised learning, labeled data are used as a

guide for the weight changes, whereas in unsupervised methods, patterns are decided without

any intervention. Reinforcement learning is about the feedback in the form of rewards or

penalties. Neural networks are highly demanding in terms of computational power and data

volume if they are to converge properly (Null & Lobur, 2014). This quality of theirs makes them

perfect for such tasks as language translation, image recognition, and predictive analytics.

21. Through what metaphor do systolic arrays get their name? Why is the metaphor fairly

accurate?

Systolic arrays got their name from the beat of the human heart. In this system, data moves, or

“pulses,” with the same timing through a grid of processing elements (PEs) just like blood flow

in the arteries (Null & Lobur, 2014). Everyone PE does a simple operation and sends the result to

its neighbors in the same rhythm. It is indeed a metaphor as the idea of systolic arrays revolve

around regualr, rhythmic data flow to the point that control for execution is highly irregular (Null

& Lobur, 2014). The constant flow of data movement provides stable timing and high

throughput.

The comparison to nature also points the array’s decentralized and supporting characteristics.

One processing element is like one neuron in the brain; it survives, and even thrives, on its own

yet it also works coherently with the other elements in the network, thus, it is always busy (Null

& Lobur, 2014). Data “pulses” through the array in waves, completing complex matrix or signal

operations efficiently. Systolic arrays employ a very regular pattern which is the main reason

why they can dispense with a complex control unit and run synchronization overhead at a very

low level (Null & Lobur, 2014). Hence, the metaphor suggests not only the rhythm but also the

effectiveness of systolic computation, showing how performance can be increaed by organizing

the data movement in a certain way.

22. What kinds of problems are suitable for solution by systolic arrays?

Systolic arrays are perfect for scenarios that require repeated and regular computations over large

datasets. Matrix multiplication, convolution, and digital signal processing are excellent

examples, as these operations involve repetitive arithmetic on structured data (Null & Lobur,

2014). The pipelined architecture of the array enables the data to flow steadily through the

various processing elements, each doing a part of the computation. This layout reduces memory

access latency to a minimum and increases the throughput to the maximum, thus systolic arrays

are very efficient and time-critical applications like image processing and real-time analytics can

be benefited from them (Null & Lobur, 2014).

In addition, systolic arrays are very good in deterministic, high-throughput environments where

timing of the events is predictable and very important (Null & Lobur, 2014). Their regular data

movement and local communication make them ideal for hardware implementation in embedded

systems, neural network accelerators, and supercomputers. However, they are not as capable of

handling irregular or data-dependent computations (Null & Lobur, 2014). Basically, systolic

arrays are devices that operate in structured, data-parallel problems, thus they can provide

performance, scalability, and energy efficiency that are hardly ever matched by general-purpose

architectures.

EXERCISES

1. Why do RISC machines operate on registers?

ISC (Reduced Instruction Set Computer) systems mainly use registers for their operations to

increase their performance, efficiency, and to keep the execution of instructions simple.

RISC architectures, by emphasizing register-to-register operations, greatly reduce the slow

process of accessing data directly from memory, which is much slower than accessing

registers (Null & Lobur, 2014). Registers offer fast, local storage for operands and thus the

processor can carry out arithmetic and logical operations at high speed without having to wait

for data to be retrieved from main memory. Besides, this design finalizes the simplification

of the instruction set as the instruction performing a single, simple operation within one clock

cycle is the typical one (Null & Lobur, 2014).

Working with registers enables RISC processors to use regular, fixed-length instructions that

are easily decoded and efficiently pipelined. Such uniformity lowers hardware complexity

and enhances instruction throughput. Besides, register-based operations allow compilers to

be more efficient as they can assign the most frequently used variables to registers thus

reducing memory traffic. As a result, RISC architectures obtain higher execution speed,

lower power consumption and increased instruction-level parallelism. To sum up, it is mainly

through registers that RISC architectures manifest their design philosophy i.e. simplicity,

speed, and efficiency which are the core principles that distinguish them from CISC

(Complex Instruction Set Computer) systems which are more complex and memory-

dependent (Null & Lobur, 2014).

2. Which characteristics of RISC systems could be directly implemented in CISC systems?

Many of the features of RISC (Reduced Instruction Set Computer) systems may be either

directly implemented or adapted in CISC (Complex Instruction Set Computer) architectures

in order to improve their performance, efficiency, and scalability. Although RISC and CISC

were initially developed with opposite philosophies—RISC focusing on simplicity and

speed, and CISC concentrating on complex instructions and compact code—today’s CISC

systems have gradually adopted RISC principles. These hybrid strategies combine the

benefits of both designs, thus resulting in better processor performance in general.

Apart from the other features of RISC that can be found in CISC clearly, instruction

pipelining is probably one of the most essential RISC concepts that can be implemented in

CISC systems. Whereas pipelining lets several instructions overlap execution, it results in

higher throughput and efficiency. RISC architectures were equipped with equal instruction

lengths and simple operations in order to facilitate pipelining. On the other hand, with the

progress in decoding and micro-op translation units, the CISC systems like Intel’s x86

processors have restructured pipelines to make the execution of instructions more efficient

(Null & Lobur, 2014). Therefore, it implies that regardless of how complicated CISC

instructions are, internally they are broken down into smaller, RISC-like micro-operations

which are then passed along a pipeline, hence the speed is increased without any

modification of the external instruction set.

Integrating the use of a wide array of general-purpose registers is another feature which can

be merged with CISC architectures. The RISC designs focus on doing the operations on

registers rather than on memory which helps in cutting down the number of expensive

memory accesses. CISC processors may have more registers or incorporate register renaming

mechanisms to achieve the result thereby reducing data hazards and increasing instruction-

level parallelism (Null & Lobur, 2014). By increasing the use of registers, CISC processors

can be enabled to perform most of the execution speed benefits of RISC which is something

that were done by RISC without leaving their current instruction set unchanged.

Another characteristic typical to RISC that can be partially implemented in CISC systems is

the load/store architecture. In RISC appliances, only load and store instructions are allowed

to access memory; all other operations are performed between registers. Although CISC

processors normally have memory operands in most instructions, internally they can take a

similar step. At present, CISC processors already change complicated memory operations

into a series of simple load, compute, and store micro-operations which is exactly what the

RISC approach is (Null & Lobur, 2014). Thus, the process of execution control within the

processor is made easier by this method, at the same time allowing for compatibility with

older CISC instruction sets.

Besides that, fixed-length instruction formats, which are at the heart of RISC, can be

simulated within CISC systems so as to facilitate the decoding of instructions. Variable-

length instructions are inherent in CISC architectures however processors of today make use

of instruction prefetch buffers and decoders to convert CISC instructions into standard

internal formats. This method lessens the decoding work and makes parallel instruction

issuing possible (Null & Lobur, 2014).

On top of that, CISC systems may also borrow RISC compiler optimization strategies.

Compilers were an integral part of the design concept of RISC architectures which

minimized the hardware complexity and relied on efficient instruction scheduling. Similar

optimization techniques, e.g., register allocation, instruction reordering, and loop unrolling,

can be used by CISC compilers to raise performance. Such improvements at the software

level have the effect of hardware upgrading, thus CISC architectures are capable of realising

higher execution speeds with minimum design changes (Null & Lobur, 2014).

Moreover, instruction-level parallelism (ILP), a concept most closely related to RISC, is

possible in a CISC system when superscalar execution and out-of-order processing are

employed. These methods allow the execution of two or more instructions in parallel or out

of order but the program still remains correct. By using dynamic scheduling and multiple

execution units, the CISC processors come very close to the performance of the RISC

processors while still keeping their feature-rich instruction sets (Null & Lobur, 2014).

3. Which characteristics of RISC machines could not be implemented in CISC machines (based

on the defining characteristics of both architectures as listed in Table 9.1)?

Many characteristics of RISC machines have been merged into the CISC systems of today,

but the latter cannot fully comply with several essential features of RISC due to their inherent

design and architectural differences. These restrictions are the result of the difference in

philosophy between RISC, which values simplicity and regularity, and CISC, which is

characterized by the use of complex, multifunctional instructions.

For example, the one-instruction-per-cycle execution model that is typical of RISC cannot be

fully achieved in CISC. Because of the uniform instruction length and the simple addressing

modes, most of the instructions in RISC architectures are executed in a single clock cycle.

On the other hand, CISC instructions are of different lengths and complexities—some may

perform several operations within a single instruction—which naturally cannot be executed

in one cycle (Null & Lobur, 2014). Modern CISC processors, however, decompose complex

instructions into micro-operations that can be executed in parallel to speed up the execution

process, but due to the differences in instruction length and execution time, the completion of

the whole instruction in one cycle is still impossible.

Additionally, the load/store architecture is a feature that cannot be fully replicated in CISC

systems. In a RISC architecture, only load and store instructions are allowed to access

memory while all the other instructions operate on registers. This not only simplifies the

pipeline but also helps in alleviating memory bottlenecks. On the other hand, CISC

architectures permit memory operands in most instructions, thereby making it absolutely

impossible to strictly separate computation from memory access without at the same time

fundamentally changing the instruction set (Null & Lobur, 2014). Consequently, memory

access in CISC systems is more complicated and less predictable, which in turn affects

pipeline efficiency negatively.

Besides, RISC architectures have a large and uniform set of general-purpose registers, which

contributes to fast instruction execution and makes compiler optimization easier. Contrary to

this, a number of CISC processors have small, specialized registers with distinct functions

(Null & Lobur, 2014). Increasing the number of CISC registers or making their functions

more general would entail redefining the instruction set and thus, compatibility with previous

versions would be broken—something which is not doable considering the historical

significance of the CISC legacy support.

Fixed-length, simple instruction formats are very important in RISC systems as they facilitate

decoding and control logic greatly. By definition, CISC architectures are characterized by

variable-length instructions that encode complex operations and multiple addressing modes.

The variability renders decoding more difficult and it cannot be resolved without giving up

one of the most salient features of CISC, i.e. compact, multifunctional instructions (Null &

Lobur, 2014).

4. What does the “reduced” in reduced instruction set computer really mean?

The "reduced" part in Reduced Instruction Set Computer (RISC) is not simply about having

fewer instructions, but rather it is a design philosophy that focuses on the simplicity, the

efficiency, and the speed of the instruction execution. In RISC machines, the instruction set

is simplified in terms of the operations performed - the number of instructions is not

necessarily lower - so that each instruction is a simple one, which is well-defined, and

usually, it can be done in a single clock cycle (Null & Lobur, 2014). RISC processors,

therefore, are quite different from CISC (Complex Instruction Set Computer) processors,

which contain more complex instructions capable of combining multiple operations into one

instruction but consume more processor cycles.

The “reduced” feature is also indicative of simplifications made in instruction formats,

addressing modes, and hardware control units which not only make the processor design

more streamlined but also enhance the efficiency of pipelining. Since RISC instructions are

of the same length and follow a uniform execution model, the processor can fetch, decode,

and execute instructions concurrently, thus it can work at full capacity and the waiting time is

reduced to a minimum (Null & Lobur, 2014). In addition, RISC machines count heavily on

compiler optimization for the management of the simplicity of the instruction set, thus

software can efficiently utilize hardware resources without the need for complex machine

instructions.

At the end of the day, “reduced” means to realize better performance by simplifying - to

insist on doing many simple instructions very quickly instead of few complex ones slowly.

This decision results in an increase in speed, energy efficiency, and scalability which makes

RISC a core idea for the processor of the future.

5. Suppose a RISC machine uses overlapping register windows with:

10 global registers

9 input parameter registers

10 local registers

6 output parameter registers

How large is each overlapping register window?

and output, with a separate block of global registers accessible to all procedures. In normal

RISC implementations (e.g., SPARC-style), the window that changes on a procedure call

consists of the input, local, and output registers; globals are not part of the per-window

overlap, they are shared across all windows (Null & Lobur, 2014). So, with your figures - 9

input, 10 local, and 6 output registers - each overlapping register window thus has 9 + 10 + 6

= 25 registers. In case you want to state the total number of registers visible to a procedure

including the shared globals, then add 10 global registers to get 25 + 10 = 35 registers

accessible to the procedure at any time.

Since windows overlap, the output registers of the caller become the input registers of the

callee on a call. That overlap determines how many physical registers the register file must

provide and how parameters are passed. Your case is such that the caller has 6 output

registers but the callee expects 9 input registers; thus, only 6 of the callee's 9 inputs can be

satisfied by overlap with the caller's outputs. The other 3 input registers have to come from

somewhere - either by loading from memory, by using additional non-overlapping registers

in the register file, or by the compiler arranging parameter passing in another way. This

asymmetry (outputs < inputs) exacerbates the burden on the register allocator and may

increase the number of window spills and fills (memory saves/restores) thus, reducing the

performance benefits of windowing (Null & Lobur, 2014).

At last, when determining the size of the physical register file for an implementation,

designers have to consider not only the number of simultaneous windows (W) but also the

globals. Given that W windows are supported and each window requires 25 registers

(inputs+locals+outputs), the simple total register requirement is 10 globals + 25·W physical

registers. Overlap lowers the logical parameter passing cost, but mismatched in/out counts

(as here) can lead to extra memory traffic or necessitate a larger physical register file to avoid

spills. So: per-window size = 25 registers (excluding globals); 35 registers if you count the

10 shared globals as well (Null & Lobur, 2014).

6. A RISC processor has 8 global registers and 10 register windows. Each window has 4 input

registers, 8 local registers, and 4 output registers. How many total registers are in this CPU?

(Hint: Remember, due to the circular nature of the windows, the output registers of the last

window are shared as the input registers of the first window.)

To determine the total number of registers in this RISC processor, we must carefully account

for the global registers, the register windows, and the overlapping nature of input and output

registers. The problem states that the processor has 8 global registers and 10 register

windows, where each window consists of 4 input registers, 8 local registers, and 4 output

registers.

In a register window architecture, such as that used in SPARC-based RISC systems, the input

registers of one window overlap with the output registers of the previous window. This

overlap allows for efficient parameter passing between procedures without copying data to

and from memory (Null & Lobur, 2014). When a new procedure is called, the current

window shifts, and the callee’s input registers become the caller’s output registers. Because

of this design, the input and output register sets are shared between adjacent windows,

reducing the total number of unique physical registers required.

Let’s calculate the total number of registers step-by-step:

1. There are 8 global registers, which are accessible to all procedures at all times. These are

unique and non-overlapping.

2. Each of the 10 register windows contains:

a) 4 input registers (shared with the previous window’s output registers)

b) 8 local registers (unique to each window)

c) 4 output registers (shared with the next window’s input registers)

If we count the local registers, these do not overlap. Thus, there are:

10 windows × 8 local registers = 80 local registers.

Now, for the input and output registers, due to overlapping, we cannot simply multiply (4 + 4) ×

10 = 80, because each set of 4 output registers in one window overlaps with the 4 input registers

of the next window. Therefore, for all 10 windows, there are 10 × 4 = 40 unique input/output

window’s inputs. This circular overlap means that there are only 10 × 4 = 40 unique physical

registers for both input and output combined, not 80 (Null & Lobur, 2014).

Adding all unique registers together:

 8 global registers

 80 local registers

 40 shared input/output registers

Thus, the total number of physical registers in the CPU is:

8 + 80 + 40 = 128 total registers.

This configuration allows each window to access 4 input, 8 local, and 4 output registers while

maintaining efficient data transfer between procedures. The overlapping design minimizes

throughput and execution speed (Null & Lobur, 2014).

7. A RISC processor has 152 total registers, with 12 designated as global registers. The 10

registers are in each register window set?

Determining the number of local registers in each register window requires an understanding

of how registers are organized in a RISC processor. The problem states that the processor is

equipped with 152 total registers, 12 global registers, and 10 register windows, each having 6

input and 6 output registers. Since RISC architectures employ overlapping register windows,

the output registers of one window can be considered the input registers of the next window

(Null & Lobur, 2014). This overlapping technique facilitates the passing of parameters

between procedures in an efficient manner and also accounts for fewer physical registers.

The first step is to remove the global registers from the total number of registers:

152 total – 12 global = 140 registers are left for the register window system.

Each window of registers comprises three segments: input, local, and output registers. The

input and output registers are the ones that are overlapped between two adjacent windows,

which indicates that the total number of different input/output registers is equal to the number

of windows multiplied by the number of registers in an input or output group - not both.

Hence, the number of shared input/output registers is calculated as follows:

10 windows × 6 overlapping registers = 60 shared input/output registers.

Local registers are the ones that remain in a window file after the subtraction of the shared

input/output registers from the total number of windowed registers. From the 140 total

windowed registers, subtract the 60 shared input/output registers:

140 – 60 = 80 local registers in total.

There are 10 register windows, so the 80 local registers should be divided by 10 windows:

80 ÷ 10 = 8 local registers per window.

Hence, each register window would have 6 input registers, 8 local registers, and 6 output

registers. Such a well-balanced setup not only facilitates the passing of parameters but also

helps in reducing the number of memory operations, which is one of the main advantages of

RISC design (Null & Lobur, 2014).

8. A RISC processor has 186 total registers, with 18 globals. There are 12 register

windows, each with 10 locals. How many input/output registers are in each register

window?

To determine how many input/output registers exist in each register window, we begin by

examining the structure of the RISC processor. The problem states there are 186 total

registers, with 18 global registers and 12 register windows, each containing 10 local registers.

Since the local registers are unique to each window and do not overlap, we can calculate their

total first:

12 windows × 10 locals = 120 local registers.

Next, subtract both the global and local registers from the total to find how many registers

are used for input/output sharing:

186 – (18 globals + 120 locals) = 48 registers.

Because input and output registers overlap between adjacent windows, the number of unique

physical registers used for these shared groups equals the number of windows multiplied by

the number of registers per input (or output) group. Thus, we divide the 48 shared registers

by 12 windows:

48 ÷ 12 = 4 input/output registers per window.

Each register window, therefore, consists of 4 input registers, 10 local registers, and 4 output

registers. This overlapping design enhances efficiency by allowing parameters to be passed

directly between procedures without extra memory operations (Null & Lobur, 2014).

9. Suppose a RISC machine uses overlapping register windows for passing parameters between

procedures. The machine has 298 registers. Each register window has 32 registers, of which

10 are global variables and 10 are local variables. Answer the following:

To solve this problem, we first analyze the configuration of the RISC processor. The system

has 298 total registers, each register window has 32 registers, including 10 global registers and

10 local registers. This means that the remaining 12 registers in each window are used for

parameter passing, that is, for input and output registers. In a typical overlapping register

window model, such as in SPARC architectures, the input registers of one window overlap with

the output registers of the previous window (Null & Lobur, 2014). Therefore, the most logical

and balanced configuration assigns 6 input registers and 6 output registers per window.

The total number of physical registers in such a RISC system can be expressed as:

Total Registers = Globals + (Number of Windows × (Locals + Inputs))

Since output registers overlap with input registers in adjacent windows, they are not double-

counted. Substituting the known values:

298 = 10 + W × (10 + 6)

298 = 10 + 16W

16W = 288

W = 18

Thus, there are 18 register windows available in this machine.

a) How many registers would be available for use by input parameters?

Each window contains 6 input registers, and since there are 18 windows, the total number of

physical registers serving as input registers (considering overlap) is:

18 × 6 = 108 input registers.

These registers are the physical storage locations used for input parameters across all

windows.

b) How many registers would be available for use by output parameters?

Each window also includes 6 output registers, which overlap with the next window’s input

registers. Therefore, the 108 registers that serve as input registers also serve as output

registers for neighboring windows. The total unique number of registers for both input and

output combined remains 108 physical registers (Null & Lobur, 2014).

c) How many register windows would be available for use?

From the equation derived earlier, the total number of register windows is 18. Each of these

windows includes 10 local registers and 12 parameter registers (6 input, 6 output), while 10

global registers are shared by all windows.

d) By how much would the current window pointer (CWP) be incremented at each procedure

call?

The Current Window Pointer (CWP) identifies which window is currently active. When a

procedure call occurs, the CWP moves to the next window. Therefore, with 18 windows in

total, the CWP is incremented by 1 (mod 18) for each procedure call. This means that after

the last window, the pointer wraps around to the first window in a circular fashion.

7. Recall our discussions from Chapter 8 regarding context switches. These occur when

one process stops using the CPU and another process begins. In this sense, register

windows could be viewed as a potential weakness of RISC. Explain why this is the case.

Computer) architectures, whose main goal is to optimize procedure calls and parameter

passing. In other words, they avoid the overhead of saving and loading registers to memory

by creating a new set of registers, called a register window, for each procedure call.

Nevertheless, the improvement of performance for nested procedures within a single process,

at the cost of a major increase in complexity for context switches, i.e., the switching of the

CPU from one process to another by the operating system, is a trade-off of this architecture

(Null & Lobur, 2014). The logical register windows of each process hold parameters, local

variables, and return values. Hence, during a context switch, all registers representing the

state of a process have to be written to memory, so that the CPU can be loaded with the state

of a different process without any data inconsistency. Since RISC architectures with register

windows also tend to have a larger number of physical registers, the implication is that much

more data needs to be saved and restored at every context switch, which in turn causes a

higher system overhead.

The problem is that the context switches call for the operating system to save the entire state

of the CPU for each process, which includes all visible and hidden register windows, as well

as other components of the processor state. In a RISC machine with overlapping register

windows, some registers are common to windows due to input-output overlaps, but others, in

particular, the local registers, are different for each window. As a result, upon a context

switch, the computer is required to save not only the currently visible register window but

also all those register windows that are active. If, in fact, there are several levels of nested

procedure calls, the CPU can be forced to write the contents of a number of register windows

into memory in order to guarantee the correct resumption of a process thereafter (Null &

Lobur, 2014). This slows down the processor's multitasking capability, as the context switch

overhead is increased. Hence, the main disadvantage of register windows is that, although

they expedite procedure calls within a process, the performance of multitasking deteriorates

due to the increase in context switch latency.

An additional limitation of increased hardware complexity of managing register windows is

also raised in the article. Since a context switch requires tracking and saving multiple

windows, more hardware mechanisms, such as a Current Window Pointer (CWP) and

Window Invalid Mask (WIM), for determining which registers are in use and which are free,

are needed. After a process switch, these pointers have to be changed, and the windows'

contents have to be written to or read from memory. Besides complicating the CPU design,

this process loads the context switch routines of the operating system with more work. The

overhead can become particularly problematic in systems with frequent interrupts or a large

number of short-lived processes. The CPU cannot switch quickly between tasks as it spends

extra cycles on managing register windows, thus, some of the performance benefits from

RISC’s streamlined instruction set are lost.

dealing with context switching, although they contribute to the efficiency of procedure calls.

They require more time and higher resource consumption for saving and restoring register

states, thus, the cost of switching between processes is increased. The more register windows

a RISC machine has, the more data needs to be saved, so the time for context switch will be

longer than for architectures with a smaller number of registers, e.g., CISC (Complex

Instruction Set Computer) systems. This trade-off emphasizes the tension in computer

architecture design that lies between optimizing performance for single programs and

maintaining overall system responsiveness in multitasking environments.

8. Suppose that a RISC machine uses 5 register windows.

a) How deep can the procedure calls go before registers must be saved in memory?

(That is, what is the maximum number of “active” procedure calls that can be made

before we need to save any registers in memory?)

Since there are 5 register windows, the maximum level of nested procedure calls that can be

made without any register spilling to memory is five. Each nested call moves the Current

Window Pointer (CWP) to a new window, so the callee gets its own set of input, local, and

output registers. When there are five calls, all windows are in use; if a sixth call is nested, a

physical window that already contains live state will have to be reused, so the architecture

has to save (spill) some window contents to memory before it can reuse that physical register

set (Null & Lobur, 2014). Therefore the maximum number of active procedure calls without

any memory saves is five, one for each available window, because register windows are the

means by which per-call register state is isolated.

b) Suppose two more calls are made after the maximum value from part (a) is reached.

How many register windows must be saved to memory as a result?

Suppose after a maximum of five nested calls, you try to perform the sixth and seventh calls.

In that case, the register state of two windows must be saved to the memory. More

specifically, the hardware/OS on the sixth call is compelled to spill one window (the oldest or

the one determined by the window-management policy) to the backing store so that the

number of physical windows necessitates the spilling of a window so that the callee can have

a new logical window, thus two extra calls beyond the five-window capacity result in two

spilled windows (Null & Lobur, 2014).

c) Now suppose that the most recently called procedure returns. Explain what occurs.

Once the most recent procedure return takes place, the CWP is decremented (it points back to

the caller's window), and the callee's window is free to be reused. In a situation where

windows have been spilled to memory due to an excessive number of calls, a return might

also cause the restoration (fill) of a previously spilled window into the register file if the

returning context requires the register contents that were saved. In a scenario where the

returning procedure used a window that had not been overwritten, hence no restores are

necessary, the return simply makes the caller's registers visible again. If there were spills, the

return instruction normally reloads the spilled window that has to be made visible again so

that program correctness is maintained (Null & Lobur, 2014).

d) Now suppose one more procedure is called. How many register windows need to be

stored in memory?

After this return, the next call will use the newly freed window first; it is decided whether

additional windows need to be stored by the condition if there are still some outstanding

spills and if any spilled windows have already been restored. In a standard scenario of an

implementation that restored one spilled window on return, there would be one spilled

window left in memory; hence the new call would have to save that remaining live window

before giving the callee a fresh window - i.e., one window would have to be stored.

However, if the system restored all spilled windows on return (thus, costing extra time), the

fresh call would not have to cause any additional spills. Therefore, the typical minimal

solution is that one more window has to be stored in the case of two prior spills and a single

return/restore sequence (Null & Lobur, 2014).

11. In Flynn’s taxonomy:

a) What does SIMD stand for? Give a brief description and an example.

In Flynn's classification, SIMD is an abbreviation for Single Instruction, Multiple Data. This

is an architectural model in which a single control unit can send one command that is

executed simultaneously on multiple data elements. Such operations are efficient in the cases

where the same operation is to be applied on large data sets, e.g., multimedia processing,

image filtering, or scientific simulations. To illustrate, if an image is being processed, the

same arithmetic operation (say, increasing brightness) can be done on thousands of pixels at

the same time.

Current SIMD realizations comprise vector processors and the SIMD extensions in CPUs,

e.g., Intel's SSE and AVX instruction sets (Null & Lobur, 2014). These architectures achieve

higher throughput by exposing data-level parallelism and lessening instruction-fetch

overhead.

b) What does MIMD stand for? Give a brief description and an example.

MIMD refers to Multiple Instruction, Multiple Data. Here, several processors can carry out

different instructions on different data at the same time. Since each processor works on its

own, MIMD is great for distributed systems and a multiprocessor setting. For instance, a

multicore CPU or computer cluster where each core or node can execute different programs

or threads at the same time. MIMD architectures are the choice of the majority of servers,

supercomputers, and parallel computing setups, which are used for intricate problem-solving

and multitasking (Null & Lobur, 2014).

12. Flynn’s taxonomy consists of four primary models of computation. Briefly describe

each of the categories and give an example of a high-level problem for which each of

these models might be used.

Flynn's taxonomy categorizes computer architectures by the number of concurrent instruction

and data streams that they can handle. The four primary models are SISD, SIMD, MISD, and

MIMD. Each of these models represents a different form of parallelism and data processing

behavior (Null & Lobur, 2014).

The Single Instruction, Single Data (SISD) model is the one that describes the conventional

sequential computer system, where one instruction is applied to one data element at a time.

The architecture in question is characteristic of uniprocessor systems, e.g. early Intel

processors or simple embedded systems. SISD is a proper computing paradigm if the

operations performed by the applications are executed sequentially, as in the case of word

processing, elementary arithmetic operations, or single-threaded programs where the tasks

have to be performed in a strict order (Null & Lobur, 2014).

The Single Instruction, Multiple Data (SIMD) model carries out a single instruction on

multiple data elements concurrently. Such parallelism finds a perfect match in the

implementation of repetitive, data-parallel tasks, e.g. matrix multiplication, image processing,

or scientific simulations. The examples of SIMD architectures abound in modern GPUs and

vector processors. By doing the same operation over large data arrays, SIMD systems gain

enormous speedups in computationally intensive workloads (Null & Lobur, 2014).

The Multiple Instruction, Single Data (MISD) model means that several processors run

different instructions on the same data. Theoretically, in practice, MISD is hardly ever found;

however, it can be implemented in fault-tolerant systems that support redundancy and are,

thus, more secure, e.g., spacecraft or avionics, where the redundant calculations verify the

data correctness among different processing units (Null & Lobur, 2014).

The Multiple Instruction, Multiple Data (MIMD) model is the most versatile one that enables

multiple processors to perform different instructions on different data at the same time.

MIMD topology is a basis for both distributed and parallel computing systems, such as

supercomputers, multicore processors, and cloud computing clusters. MIMD configurations

are, thus, able to cope with large-scale problems arising in weather prediction, artificial

intelligence, or big data analytics (Null & Lobur, 2014).

13. Explain the difference between loosely coupled and tightly coupled architectures.

Loosely coupled and tightly coupled, in computer architecture, are the terms that describe how

share and coordinate access to memory and communication resources are done by multiple

processors in a system. When it comes to tightly coupled architecture, i.e. a shared-memory

multiprocessor system, the story is about multiple CPUs that share a single physical memory

space and communicate through this common memory. As each processor has direct access to

the same address space, it can share data rapidly and synchronize efficiently. This layout is

best for parallel processing where the tasks are heavy on the frequent exchange of

information, e.g., scientific simulations or real-time systems. On the downside, it may

experience memory contention and its scalability can be limited as adding more processors

(Null & Lobur, 2014) is not favorable.

On the other hand, a loosely coupled architecture or distributed memory system, respectively,

is made up of independent processors that each has its own local memory. The processors

communicate via message passing over a network. The design is more scalable and hence, it is

the choice of clusters and distributed systems, e.g., cloud computing and large-scale data

processing applications. The main advantages of loosely coupled systems are higher fault

tolerance and better modularity; nevertheless, they have a longer communication latency than

tightly coupled systems (Null & Lobur, 2014).

14. Describe the characteristics of MIMD multiprocessors that distinguish them from

multicomputer systems or computer networks.

Which means that each processor performs its own independent instruction and data

operations. As a result, MIMDs are true parallel machines that have distinguished themselves

from other models by their close coupling and sharing of control facilities.

Typically, all processors in an MIMD system are connected by a high-speed interconnection

network and can operate independently while accessing the memory of the system via a bus or

communicating by message passing. The processors of MIMD multiprocessors run under a

single operating system and thus represent a unified control structure which guarantees the

efficient management of tasks and the allocation of resources. Such close coordination among

processors improves the system's capabilities, particularly in computationally intensive

applications such as artificial intelligence, real-time simulations, large data processing (Null &

Lobur, 2014).

Contrary to simpler architectures such as SISD or SIMD, MIMD systems are capable of

performing complex, non-uniform tasks simultaneously and hence they are highly versatile in

contemporary computing environments.

The first major differences between MIMD multiprocessors on the one hand and

multicomputer systems or computer networks on the other are their memory organization,

control structure, and communication mechanisms. Basically, MIMD multiprocessors may be

regarded as tightly coupled systems in which processors share a common memory and

communicate through shared variables or as loosely coupled systems in which each processor

has its own local memory but is still under the same control system. However, multicomputer

systems and general-purpose computer networks are made up of completely independent

computers each having its own operating system, memory, and I/O devices, and they

communicate through message passing over slower network connections.

As opposed to that, MIMD multiprocessors are single operating system image-based

multiprocessors that take care of all the processors as one system thereby providing global

coordination and faster communication. Such tight coupling leads to lower latency and faster

synchronization than in multicomputer networks which are often subject to communication

delays due to network overhead (Null & Lobur, 2014). Also, the processors in MIMD

multiprocessors are closer to each other, for example, they are on the same motherboard or in

the same chassis, thus the speed and the reliability are increased.

Another factor that sets apart is the extent of the coordination of the tasks and the sharing of

resources. In MIMD multiprocessors, processors work closely together on shared

computational tasks, thus they break down the workload dynamically and access shared

memory resources in an efficient manner. The system’s operating system and hardware

architecture thus provide the means for direct inter-processor communication and memory

access, which results in very low waiting time for the execution of parallel algorithms. On the

other hand, computer networks and multicomputer systems depend on external

communication protocols such as TCP/IP for data exchange, which results in higher latency

and also requires that message passing for coordination be explicitly mentioned. Moreover,

MIMD multiprocessors by and large use advanced synchronization methods, e.g., semaphores

or locks, to maintain the consistency of shared data structures. These systems find their best

uses in such application areas as parallel databases, large-scale simulations, and machine

learning, in which processors must be able to coordinate in real-time (Null & Lobur, 2014).

Hence, although both MIMD multiprocessors and multicomputer systems are designed to

achieve parallelism, MIMD multiprocessors attain a much higher level of effectiveness,

rapidity, and harmony as a result of their integrated hardware, unified control, and faster

communication mechanisms.

15. How are SIMD and MIMD similar? How are they different? Note, you are not to

define the terms, but instead compare the models.

Both SIMD and MIMD architectures are aimed at parallelism which means performing

multiple operations at the same time to increase the speed of the system. In fact, both models

try to speed up the computational process and make it more efficient by dividing the workload

between the different processing units. In/addition, the coordination and synchronization are

also important in MIMD as well as in SIMD processors to guarantee that the execution is

correct and efficient. They are both used as a basis for supercomputing, which has been

conducting experiments in scientific fields, image processing, and AI applications. Besides

that, they both rely on the existence of certain hardware and control means to facilitate the

data transition and still keep the processors in sync during the computation (Null & Lobur,

2014).

Nevertheless, the primary difference between SIMD and MIMD is the way how they route

instructions and data streams. Single instruction in SIMD can control multiple units working

on different data at the same time. In other words, it is very efficient when a large data set has

to undergo repetitive operations such as a vector or a matrix. On the other hand, MIMD

systems enable each processor to have its unique set of instructions and they, therefore, can

operate on different data independently hence, this model has more advantages and can be

used in complex non-uniform tasks solutions. As Long as SIMD architectures are great for

data-level parallelism, we can say that MIMD architectures are the best for task-level

parallelism such as running multiple independent programs or threads concurrently (Null &

Lobur, 2014).

16. What is the difference between SIMD and SPMD?

The primary distinguishing feature between SIMD (Single Instruction, Multiple Data) and

SPMD (Single Program, Multiple Data) is that the former has less control and flexibility than

the latter in the way multiple processors execute instructions. In a SIMD set-up, one control

unit commands all processing elements to do the same instruction at the same time, and each

processor takes the different pieces of data and applies that identical operation. This method

delivers very tightly synchronized parallelism and is perfect for execution of repetitive

computations over big data, like in image processing, matrix operations, or signal filtering. All

processors are strongly connected, running in absolute lockstep under one instruction stream

(Null & Lobur, 2014).

On the other hand, SPMD denotes a programming model that implies a different hardware

architecture concept. With the SPMD system, a single program is executed independently by

several processors, though not necessarily they will be in sync. Each processor can take

different paths of the program, depending on the conditional statements and the data it

receives. This model is widely applied in distributed-memory MIMD architectures and gives

more room for complex problem-solving. While SIMD is very strict in execution, SPMD

allows processors to behave asynchronously, thus being more suitable for varied

computational workloads (Null & Lobur, 2014).

17. For what type of program-level parallelism (data or control) is SIMD best suited?

For what type of program-level parallelism is MIMD best suited?

SIMD (Single Instruction, Multiple Data) is a type of architecture that is most appropriate for

data-level parallelism, which is a situation that requires the same operation to be performed

multiple times on data sets. In a SIMD device, a single command can govern several control

units, which by definition means that they must perform one and the same operation on

different data states. Consequently, SIMD devices are good for specimen of uniform

computations in image processing, vector and matrix calculations, and scientific simulations.

Thus, when upgrading the brightness of an image each pixel can be changed at once by the

same register operation. The effectiveness of SIMD lies in its capacity to handle repetitive,

well-structured computations in which the process synchronization is simple (Null & Lobur,

2014).

The MIMD (Multiple Instruction, Multiple Data) model, to contrast, is a model that power-

level parallelism can be achieved if it is used to execute one program differently in different

processors on diverse data sets. It is a tool which, by virtue of allowing different kinds of tasks

to be done at different times without waiting, can be used for the development of such

complex applications as web servers, database management, and distributed simulations. In a

MIMD system each processor is an individual entity, free to perform any thread of the

program it selects amongst multitasking and scalable parallelism of varied workloads (Null &

Lobur, 2014).

18. Describe briefly and compare the VLIW and superscalar models with respect to

instruction-level parallelism.

Both VLIW (Very Long Instruction Word) and superscalar architectures try to utilize the

instruction-level parallelism (ILP) concept—where multiple independent instructions can be

executed simultaneously to enhance processor performance. Nevertheless, these two differ

mostly in the way they get this parallelism and which one, hardware or compiler, is

responsible for identifying it.

Superscalar architecture realizes this by the processor's hardware, at runtime, dynamically

detecting independent instructions and hence multiple instructions can be issued per clock

cycle. The CPU has complex scheduling logic, dependency checking, and out-of-order

execution units that together enable the CPU to make the decision about which instructions

can be executed in parallel without affecting the final result. Such making them superscalar

systems more adaptable as well, since they can optimize performance even if the code is not

explicitly written for parallelism. Anyway, this approach raises the complexity of hardware

and power consumption, as the device for instruction scheduling is longer due to the

additional circuitry required for it (Null & Lobur, 2014).

On the other hand, VLIW architectures relocate the detection of parallelism from hardware to

the compiler. The compiler examines instruction dependencies and at compile time it merges

independent instructions into a single long instruction word for parallel execution. This

converts the processor implementation to a simpler one because there is no need for complex

scheduling logic in the processor. Nevertheless, VLIW performance is very dependent on the

compiler and code predictability (Null & Lobur, 2014).

19. Which model, VLIW or superscalar, presents the greater challenge for compilers?

Why?

The VLIW (Very Long Instruction Word) model is a bigger challenge for compilers as it

transfers the whole responsibility of figuring out and scheduling parallel instructions to the

compiler, which is one more time, the hardware has no role in it. In a VLIW setup, the

compiler is obliged to check for instruction dependencies, handle hazards, and combine

several independent operations into one single long instruction word that can be

simultaneously executed. This makes it necessary to have very advanced optimization

methods so as to use the hardware resources efficiently and at the same time, not to have

pipeline stalls or execution conflicts. With superscalar architectures, the hardware

dynamically schedules instructions and resolves dependencies at runtime while in VLIW the

processor must be guided by compile-time analysis, hence it is less adaptable to

unpredictable instruction flows and runtime conditions (Null & Lobur, 2014). Therefore, to

be able to get maximum performance out of VLIW systems, one has to come up with a very

complex compiler design which is also capable of doing dependency analysis and instruction

reordering.

20. Compare and contrast the superscalar architecture to the VLIW architecture.

The superscalar architecture achieves this by hardware, on the fly, it can it can it can it can it

can it can it can it.cntins to multiple execution units, dynamic scheduling logic, and

dependency-checking circuits to figure out which instructions can be executed in parallel.

Thus, the CPU is able to carry out instruction-level parallelism during runtime which

performance is increased without the need for special compiler optimization. Superscalar

architectures are very adaptable and thus are great for different workloads, however, this

advantage is offset by the increased hardware complexity, power usage, and design difficulty

(Null & Lobur, 2014) that are associated with the superscalar approach.

On the other hand, VLIW (Very Long Instruction Word) architectures rely on the compiler to

find and group independent instructions into a single long instruction word that is then

executed. The rationale behind this approach is to have a simple hardware without the need

of dynamic scheduling, and dependency-checking circuits. Nevertheless, it places a bigger

burden on the compiler to detect instruction-level parallelism with high accuracy. VLIW

processors, theoretically, can perform at high levels if the code is predictable but they are not

so good with irregular branching or runtime dependencies that limit the parallel execution

that they are capable of (Null & Lobur, 2014).

21. Why are distributed systems desirable?

Distributed systems are attractive as they provide better performance, scalability, reliability,

and sharing of resources over a network of multiple interconnected computers. Such systems,

by splitting the work among several machines, are thus able to process bigger and more

complicated problems efficiently and at the same time they preserve fault tolerance - if one

node fails, the others can still operate. In addition, distributed systems make it possible to

have the resources spread out over the globe so as to allow collaboration, load balancing, and

efficient utilization of the computing power. This kind of architecture is the one that is used

to support nowadays applications like cloud computing, big data analytics, and web services

through giving the features of flexibility, redundancy, and parallel processing (Null & Lobur,

2014).

22. What is the difference between UMA and NUMA?

The main distinction between UMA (Uniform Memory Access) and NUMA (Non-Uniform

Memory Access) is the method by which processors access memory in a multiprocessor

system. For a UMA architecture, all processors have a physically shared memory and the

access time to any memory location is the same for all. Although this design makes

programming easy and guarantees stable performance, it can cause memory contention

situations when more processors compete for the same memory bus that limits scalability.

Unlike that, memory in a NUMA system is divided into the areas that are local to each

processor, so the access to the local memory is faster than the remote memory. Thus, the

NUMA enhances the scalability and the performance of the large multiprocessor systems by

alleviating the memory bottlenecks. However, it complicates the management of data and

software optimization (Null & Lobur, 2014).

23. What are the main problems with using crossbars for interconnection networks?

What problems do buses present in interconnection networks?

Crossbar interconnection networks enable fast, non-blocking communication between

processors and memory modules with the possibility of multiple simultaneous data transfers.

Nevertheless, their biggest drawback is cost and scalability. The reason is that the number of

crosspoints (switches) increases quadratically with the number of processors and memory

units, thus the hardware becomes expensive and complicated to implement. For a system

with n processors and n memory modules, n² crosspoints are needed. This difficulty escalates

the wiring density and power consumption so that crossbars become unusable for large-scale

multiprocessor systems, albeit their excellent performance (Null & Lobur, 2014).

Besides that, the crossbar networks have a significant physical design and synchronization

problem. It is very difficult to manage timing and coordination of simultaneous data transfers

when the number of processors is increased. Slowdown of signal propagation and contention

for switching elements result in the reduction of the system's efficiency. Moreover, crossbars

should have sophisticated arbitration logic to cope with multiple requests for the same

destination memory module thus increasing latency and hardware overhead. So, in fact,

crossbars are a quick, direct way of communication in small systems but their physical and

logical complexity makes them incapable of scaling to bigger configurations (Null & Lobur,

2014).

Bus-based interconnection networks, as a counterpart, hold a shared communication channel

that connects multiple processors and memory units. The main issue with buses is contention,

only one data transfer can take place at a time on a shared bus. When more processors are

added, the bus turns into a communication bottleneck because every processor has to wait for

its turn. This contention results in lowered system performance and restricted scalability, thus

bus systems are only appropriate for small-scale multiprocessor configurations or systems

with light communication demands (Null & Lobur, 2014).

Moreover, buses have limited bandwidth and electrical loading problems. When more

devices are connected to the bus, signal degradation, propagation delay, and synchronization

difficulties become worse, thus transmission speed decreases. Increasing bus width or

frequency can solve these problems to some extent but there will be a higher hardware cost

and more complex design. Besides that, buses are without fault tolerance features—if the

shared communication line is damaged, the whole system may be interrupted. On the

contrary, more advanced interconnection topologies like meshes or hypercubes offer several

communication paths and thus, are more reliable. Therefore, although buses are easy and

cheap, they are not efficient in highly parallel systems (Null & Lobur, 2014).

25. Describe write-through and write-back cache modification as they are used in

shared memory systems, and the advantages and disadvantages of both approaches.

Write-through and write-back are two fundamentally different ways of handling shared

memory in computer systems that are most commonly dealt with in the context of cache

modifications. In write-through, the data is first written to the cache and then, if a cache miss

occurs, it is updated in the main memory as well. In the main memory, the data is

synchronized with the cache blocks of each processor, thus assuring that all processors have

the most recent data. The most significant drawback of write-through is performance since,

in this case, memory writes occur more frequently and, as a result, so does bus traffic (Null &

Lobur, 2014).

On the other hand, the write-back technique delays updating the main memory until the time

when the replaced or invalidated cache line is changed. Hence, the updates are done only in

the cache, while the rest of the memory is kept intact, which is the reason for performance

improvement due to fewer memory writes. The significant advantage of write-back caching

is that it only requires the memory to be accessed for a limited time and thus, it conserves bus

bandwidth. Still, it poses a problem of cache consistency since the same data may be held in

several caches, and a certain one may be outdated. To solve this problem, a number of cache

coherence protocols, including MESI, have been developed. Therefore, write-through is more

consistent whereas write-back is faster (Null & Lobur, 2014).

26. Should the memory of a dataflow system be associative or address-based? Explain.

Memory for a dataflow system has to be associative rather than address-based. In a

conventional address-based memory system, the data is accessed via exact memory addresses

that are explicitly determined by the program’s control flow. But, in a dataflow architecture,

the operation of the instructions is reliant on the availability of data and not on sequential

program order. Associative memory provides the possibility of data retrieval on the basis of

content instead of an address, which is absolutely in line with the data-driven nature of

dataflow systems. The instruction that corresponds to the operands can thus be fired

automatically and executed without the necessity of a control sequence if all of the operands

for an instruction are available (Null & Lobur, 2014).

Switching to associative memory leads to greater efficacy because it makes the system able

to dynamically and on its own find the data tokens with the operations that await them, thus,

the system does not have to wait at times when there is no work for the processor in control-

based architectures. The great advantage of this is that very great parallelism is possible

because there is no limit to the number of instructions that from now on can be run

concurrently as long as their input data is there. An address-based memory, conversely,

would limit this parallelism by imposing a sequential access pattern and thus the system’s

inherent flexibility and performance would be reduced. Hence, associative memory is more

adequate to the data-driven execution model in that it affords rapid, parallel data matching

and it is open to very high degrees of computational concurrency (Null & Lobur, 2014).

27. Do neural networks process information sequentially? Explain.

Neural networks do not sequentially process information. Rather, they process data in a very

parallel fashion. In a neural network, each neuron works concurrently, thus it receives inputs,

performs computations, and sends outputs to other neurons. The parallelism is the same as

the human brain, where billions of neurons process information simultaneously. Unlike

conventional sequential computing architectures, which handle one instruction at a time,

neural networks do multiple calculations simultaneously, thereby they can efficiently work

with big and complex datasets such as images, speech, and patterns (Null & Lobur, 2014).

Because of their parallel structure, neural networks can process data at a higher speed, and

their fault tolerance is also improved. Even if some neurons fail, the network is still able to

produce valid results since the computation is spread over a large number of interconnected

nodes. This feature also makes learning via training possible whereby weights are changed

across several neurons at the same time to reduce the error. Sequential processing

architectures cannot handle such dynamic adaptation. Hence, the inherent parallelism of

neural networks is what makes them so powerful in pattern recognition, decision-making,

and AI applications (Null & Lobur, 2014).

28. Compare and contrast supervised learning and unsupervised learning with regard

to neural networks.

Supervised learning and unsupervised learning are the two main methods of neural networks

training. They differ mainly in the way they use data and feedback. When the network learns

in a supervised way, it gets the labeled datasets, i.e. each input is matched with a known,

correct output. The mechanism learns by itself when it sees the difference between its

predicted outputs and the actual ones and thus modifies the internal weights in order to

decrease the error through some algorithms like backpropagation. This method needs a great

deal of precisely labeled data, but in general, it leads to very accurate and stable models.

Supervised learning suits best to tasks such as image recognition, speech processing, and

medical diagnosis, i.e. the cases where the right results are already known (Null & Lobur,

2014).

On the other hand, unsupervised learning means feeding neural networks with unlabeled

data, so the algorithm needs to find the inner patterns, groupings, or structures without any

explicit hints. The network detects the relations or similarities in the data, in most cases,

through clustering or dimensionality reduction methods. This type of training is open to the

use of customer segmentation, anomaly detection, and pattern discovery, which are solely

domain of exploratory analysis. Although unsupervised learning does not call for a lot of

preparation of training data, it is quite difficult to assess since no correct answers are there

beforehand. Therefore, supervised learning concentrates on the accuracy of the prediction,

whereas unsupervised learning is more about discovering the hidden structures of the data

(Null & Lobur, 2014).

29. Describe the process of supervised learning in neural networks from a mathematical

perspective.

From a mathematical perspective, supervised learning in neural networks involves

optimizing a function that maps inputs to desired outputs using a labeled dataset. The process

is rooted in minimizing the difference between predicted and actual outputs through iterative

weight adjustment.

At its core, a neural network represents a function f(x; w), where x is the input vector and w

represents the weights and biases of the network. Given a training dataset D = {(x_i,

y_i)}_{i=1}^N, where y_i denotes the target output for input x_i, the goal is to minimize a

loss function L(y_i, f(x_i; w)), which quantifies the error between the predicted and actual

output. A common choice for regression tasks is Mean Squared Error (MSE):

L = (1/N) Σ(y_i - f(x_i; w))^2

For classification, the cross-entropy loss is often used:

L = - Σ Σ y_ik log(ŷ_ik)

where ŷ_ik is the predicted probability for class k.

The learning process involves adjusting weights to minimize this loss using gradient descent

or one of its variants (e.g., stochastic gradient descent, Adam). The weight update rule is

expressed as:

w_(t+1) = w_t - η ∇_w L

where η is the learning rate and ∇_w L is the gradient of the loss with respect to the weights.

The gradient indicates the direction of steepest increase in the loss function; thus, subtracting

it reduces the loss iteratively.

The backpropagation algorithm computes these gradients efficiently by applying the chain

rule of calculus through each layer of the network. For a single neuron, the output o is

calculated as:

o = φ(Σ w_j x_j + b)

where φ is the activation function (e.g., sigmoid, ReLU, tanh), w_j are the weights, x_j are

the inputs, and b is the bias. The derivative of the loss function with respect to each weight is

computed recursively from the output layer back to the input layer, adjusting weights in

proportion to their contribution to the total error.

This iterative optimization continues until convergence, typically when the loss function

stabilizes or reaches a minimal threshold. During training, regularization techniques such as

L2 weight decay or dropout may be applied to prevent overfitting. The trained model can

then generalize to unseen data, effectively approximating the true underlying function f*(x)

that maps inputs to outputs (Null & Lobur, 2014).

30. These two questions deal with a single perceptron of a neural network.

a) The logical NOT is a little trickier than AND or OR, but can be done. In this case,

there is only one Boolean input. What would the weight and threshold be for this

perceptron to recognize the logical NOT operator?

b) Show that it is not possible to solve the binary XOR problem for two inputs, x₁ and x₂,

using a single perceptron.

(a) Logical NOT Operation

Use the perceptron activation function: y = 1 if (w * x + b > 0), else y = 0.

For a single Boolean input x ∈ {0,1}, we want to implement the logical NOT operation,

which outputs 1 when x = 0 and 0 when x = 1.

Choose the weight w = -1 and bias b = 0.5. Checking both cases:

- When x = 0: (-1)(0) + 0.5 = 0.5 > 0 → y = 1 (correct)

- When x = 1: (-1)(1) + 0.5 = -0.5 ≤ 0 → y = 0 (correct)

An equivalent representation using a threshold θ is w = -1 and θ = -0.5. Alternative scaled

values (e.g., w = -2, b = 1) would also work.

The essential idea is that the weight must be negative and the bias positive so that the output

flips between 1 and 0 based on the input.

(b) XOR Operation

The XOR (exclusive OR) function cannot be represented by a single perceptron because it is

not linearly separable.

The XOR truth table for inputs (x1, x2) is as follows:

(0,0) → 0

(0,1) → 1

(1,0) → 1

(1,1) → 0

Let the perceptron compute y = 1 if (w1 * x1 + w2 * x2 + b > 0). This produces the following

inequalities:

1. For (0,0): b ≤ 0

2. For (0,1): w2 + b > 0

3. For (1,0): w1 + b > 0

4. For (1,1): w1 + w2 + b ≤ 0

Adding (2) and (3) gives: (w1 + w2 + 2b) > 0

From (4): (w1 + w2 + b) ≤ 0

Subtracting yields: b > 0

However, (1) states that b ≤ 0. This contradiction means that no real weights (w1, w2, b) can

satisfy all conditions simultaneously.

Therefore, the XOR function cannot be represented using a single linear decision boundary.

To model XOR, at least a two-layer neural network or a nonlinear activation mechanism is

required.

31. Explain the differences between SIMD and systolic array computing when the

systolic array is one-dimensional.

SIMD (Single Instruction, Multiple Data) and systolic array computing represent parallel

processing to some extent, but their fundamental differences lie in how data flow and

synchronization are managed, especially in a case of one-dimensional systolic arrays. With

SIMD, a control unit sends out a single instruction that is carried out by several processing

elements (PEs), each working on a different piece of data that can be stored either locally or

in memory. All PEs perform the same operation simultaneously and hence, SIMD is a perfect

tool for the likes of image processing or vector arithmetic where the same operations are

applied to vast datasets. The system is dependent on centralized control and synchronization

to a great extent, which ensures that all PEs are executing the same instructions at every

clock cycle (Null & Lobur, 2014).

On the other hand, a one-dimensional systolic array is a set of processing elements that are

connected in a line and the data flows in a controlled fashion from one PE to another, like

blood flowing through arteries—hence the name “systolic.” Each PE executes part of the

computation and hands over intermediate results to the next PE in a pipeline fashion. Unlike

SIMD, systolic arrays are asynchronous; each PE which is semi-independent works and is

activated when data arrives, thereby negating the need for a central instruction stream. This

method is very effective in terms of data locality and throughput for the likes of matrix

multiplication or convolution operations. While SIMD is about simultaneous uniform

execution, systolic arrays are about continuous, data-driven computation flow (Null & Lobur,

2014).

32. With respect to Flynn’s taxonomy, where do systolic arrays fit? What about clusters

of workstations?

Systolic arrays can be considered as SIMD (Single Instruction, Multiple Data) within Flynn's

taxonomy. This is due to the fact that a systolic array has multiple processing elements that

do the same operation on different pieces of data, which is similar to a SIMD architecture.

Nevertheless, the major difference is in the manner in which data is transferred through the

system. Systolic arrays perform the data transfer in a pipelined manner, with data flowing

from one processing element to another, each element performing its share of the

computation and passing results to the next. This regular, data-driven communication pattern

makes systolic arrays a hybrid of SIMD and pipelined processing systems, that are

characterized by parallel data movement and local computation rather than centralized

instruction control (Null & Lobur, 2014).

Moreover, clusters of workstations are classified as Multiple Instruction, Multiple Data

(MIMD) within Flynn's taxonomy. Each workstation in these systems acts as an independent

processing unit that can follow its own instruction stream and operate on its own dataset.

Typically, communication between workstations is through message passing over a network,

which allows the execution of complex, distributed applications. This independence of

clusters enables them to perform different computational tasks concurrently, thereby, making

them very flexible and scalable. Clusters, unlike the tightly synchronized systolic arrays,

represent a loosely coupled parallel architecture that is suitable for distributed computing

environments (Null & Lobur, 2014).

Reference

Null, L., & Lobur, J. (2014). The Essentials of Computer Organization and Architecture (4th

ed.). Jones & Bartlett Publishers.

Homework 9: Advanced Concepts in Computer Architecture and Parallel Processing

Students also viewed