10 - Architecture and Parallelism

Question 1

How can you create an ALU?

Answer 1

Integrating: A full-adder, 2s-complenter, shifter, and comparator.

There’s a logic unit for each bit, with its own carry in, carry out, decoder, and logical unit.

Question 2

What does the internal bus do?

Answer 2

It allows the control unit, ALU, registers, addressing unit, etc.

The speed of the entire system will depend on bus width (number of bits that can transfer simultaneously) and bus length (the motivation for miniature computers).

Bus arbitration - the problem is that only one set of signals can be sent per clock cycle. (e.g. a register transfers something to ALU, but also data transfer to general register). The bus arbitration system decides which gets to go first.

Also, there may be multiple busses on which they go.

Question 3

How is memory made up of gates?

Answer 3

Gates combine to make switches, which combine to make memory cells, which are then combined and integrated to make memory chips.

Question 4

What are the two major types of memory?

Answer 4

1. RAM (Random access memory) - programs can access and manipulate memory cells while the computer is running.
   - - This can be addressed by machine instructions through the memory address register, manipulated through the data register, etc.
2. ROM (read-only memory) - cannot be changed while the computer is running.
   - - Ordinarily burned into a single configuration (e.g. bootup).

Question 5

How quick is a clock cycle?

Answer 5

The computer can transition to a new “state” at every tick of the system. (near light-speed).

Clock cycle length determines CPU speed (mostly). However, clock cycle length depends on distance between components.

Question 6

How has CISC architecture been improved?

Answer 6

• • more efficient microprograms
• • more powerful ISA level instructions
• • cache memory
• • more registers
• • wider buses
• • making it smaller
• • more processors
• • floating point instructions

Question 7

What are the limitations of improving CISC?

Answer 7

Improving a specific architecture requires instructions to be backward compatible.

However, the improvements that you can make come at the expense of backward compatibility (SOME companies have built in the old and the new -> not an improvement, just a transition).

Question 8

What is RISC?

Answer 8

Reduced instruction set architecture. These instructions are like CISC micro-instructions.

There’s a much smaller set of instructions at ISA level because there’s no need to go through decoding.

For example, smartphones use RISC. Even though the programs look much longer, they execute faster (b/c they do several things). RISC architecture is generally used in embedded systems so that the programs execute much faster.

Question 9

What are the major RISC design principles?

Answer 9

1. Instructions are executed directly by the hardware (no microprograms)
2. Instruction cache (maximize rate of fetching instructions).
3. Instructions easy to decode (a separate fetch unit, often with its own cache)
4. Only 2 instructions from memory (LOAD and STORE).
5. Plenty of registers.

Question 10

How is speed generally improving now?

Answer 10

1. Try to miminize memory and I/O accesses
   - - Cache
   - - Separate I/O unit (buffers/ processing)
   - - Separate network communication unit (NIC)
2. Parallel processing

Question 11

What are the two types of parallelism?

Answer 11

1. Instruction-level parallelism
   - - pipeline
   - - cache
2. Processor-level parallelism
   - - multiprocessor (multiple CPUs, common memory)
   - - multicomputer (multiple CPUs, each with own memory)

Question 12

What is pipelining?

Answer 12

The hardware must provide separate units responsible for its part of the instruction, and when that is done, it will work on the next instruction as the previous one is working on the previous instruction.

U-1 - instruction fetch
U-2 - instruction decode
U-3 - operand fetch
U-4 - instruction execute
U-5 - operand store

Question 13

What is instruction caching?

Answer 13

The hardware provides area for multiple instructions in the CPU.

• • reduces number of memory accesses
• • instructions available for immediate execution
• • might cause problems with decision, repetition, and procedure structures in programs

Question 14

What is multiprocessor parallelism?

Answer 14

Multiple processors all accessing the same shared memory (the jobs can be split among all the processors).

One of the ways they are managed is to have a master processor to direct them. Another way is to have them communicate with each other.

Question 15

What is multicomputer parallelism?

Answer 15

Each of the processors has its own memory and communicates with the others through an interconnection network (the job is split up and assigned to those that have their own memory, etc.).

Question 16

How do multiprocessors and multicomputers compare?

Answer 16

Multiprocessors are difficult to build, but relatively easy to program.

Multicomputers are easy to build (given networking technology), but extremely difficult to program.

Hybrid systems (like cloud computing) have integrated aspects of both.

Question 17

How do multiprocessors and multicomputers coordinate?

Answer 17

A multiprocessor system communicates through circuits/memory.

A multicomputer system communicates through networking technologies, like packets (data, source/destination information, etc.) or links, switches, and interfaces, etc.

Question 18

What is software parallelism?

Answer 18

Even though there have been advances in hardware, it’s been difficult for software to take advantage of those resources. It’s a major research area.

One factor is the parallelizability of algorithms, which depends on number of processors, trade-offs and efficiency (of synchronizing), and parsing sequential/parallel parts.

Question 19

What is Amdahl’s law?

Answer 19

When there’s a mixture of parallel parts and sequential parts, there’s a potential for some speedup, as represented by the formula:

speedup = n / (1 + (n-1)f)

n = number of processors
f = fraction of code that is sequential
T = time to process entire algorithm sequentially (one processor)

Note: the total execution time is = fT + ((1-f)T)/n – because the parallelizable part is shared equally among n computers.

Question 20

An algorithm takes 10 seconds to execute on a single 2.46G processor. 40% of the algorithm is sequential. Assuming zero latency and perfect parallelism in the remaining code, how long should the algorithm take on a 16 * 2.4G processor parallel machine?

Answer 20

f = .4
1-f = .6
T = 10s
n = 16

speedup = n / (1+(n-1)f)
= 16 / (1 + 15(.4)) = 16/7.

The expected time is T/speedup, so 10s / (16/7) = 4.375 seconds.

Alternatively, (.410) + (.610)/16, or the sequential plus the parallel divided by the number of processors.

Question 21

Assuming perfect scalability, what are the implications of Amdahl’s Law when n approaches infinity?

Answer 21

As you add more and more processors, the speedup factor becomes closer and closer to 1/f.

Therefore, if f = .4, parallelism can never make it run more than 2.5 times as fast.

Question 22

Why is parallel computing such a big research area?

Answer 22

It depends on so many aspects of hardware and software (although software has not been keeping up with hardware advances)

Hardware: CPU speed of individual processors, I/O speed of individual processors, interconnection network, and scalability.

Software: Parallelizability of algorithms, application programming languages, operating systems, and parallel system libraries.

Question 23

What additional factors does hardware parallelism have to consider (beyond those of single-processor machines, like CPU and I/O speed) for performance?

Answer 23

Interconnection network

1. Latency (wait time), including distance and collisions/collision resolution.
2. Bandwidth (bps), including bus limitations and CPU, I/O limitations (multicomputer systems might not even have the same type of processors).

Scalability
– adding more processors affects latency and bandwidth

Question 24

What are some of the enhancements available for software parallelism?

Answer 24

Parallel system libraries:

1. Precompiled functions designed for multiprocessing (e.g. matrix transformations)
2. Functions for control of communication (e.g. background printing)

Application programming languages

1. Built-in functions for creating child processes, threads, parallel looping, etc.
2. Mostly imperative (e.g. C)

Operating systems that can take a parallelizable program and assign the tasks.

Question 25

What are some applications of parallelism?

Answer 25

Multi-user networks (e.g. even local LAN network).
– Internet server -> manage multiple servers simultaneously.

Speed up single processes

• • chess example (deep blue)
• • expert systems
• • other AI applications