Module 1: Additional Reading

Question 1

A _ is a graphical representation of possible solutions to a decision based on different conditions. It splits a complex problem into simpler decisions, leading to an outcome.

Answer 1

decision tree

Question 2

A _ in a decision tree represents the depth or stage of the tree

Answer 2

level

Question 3

The _ represents the position of individual bits

Answer 3

bit position

Question 4

The _ in a decision tree for number representation defines the subset of values that can result from decisions made at each node, gradually narrowing the possibilities until a single value is reached.

Answer 4

range

Question 5

The distinctive feature of a _ is that for any switch, the number of links going down to its siblings is equal to the number of links going up to its parent in the upper level.

Answer 5

fat tree

Therefore, the links get “fatter” towards the top of the tree, and the switch in the root of the tree has the most links compared to any other switch below it.

Question 6

_ is the number of inputs a node can accept.

Answer 6

Fan-in

Question 7

_ is the number of outputs a node can generate or broadcast to other nodes.

Answer 7

Fan-out

Question 8

Used to construct a ternary tree

Answer 8

Fan-out of 3

Question 9

A _ is an electronic circuit designed by using components like diodes, transistors, resistors, capacitors, etc., and capable of performing logical operations

Answer 9

logic gate

Question 10

Helps in managing and amplifying the signals before they are fanned out to the destination

Answer 10

Buffers

Question 11

_ is a general term for anything that involves delivering hosted services over the internet.

Answer 11

Cloud computing

Question 12

It is a special case of a more common mechanism called a multicast in which a value is sent to a subset of nodes.

Answer 12

Broadcasting

It has one sender and multiple receivers

Question 13

It is the collection of information from
several sources into one sink (fan-in
tree). The idea is similar to a multicast, in that a tree is employed, this time to move
information from the leaves to the root.

Answer 13

Convergecast

It is a fundamental operation of distributed systems, and is commonly used in sensor networks, must be aggregated into a node.

Question 14

It has one/more senders and one/more recipients participate in data transfer traffic.

Answer 14

Multicasting

It has one or more senders and multiple receivers.

Question 15

Dependencies in the tree can be used to illustrate speedup and efficiency, two important concepts in parallel processing.

Answer 15

Parallelism

Question 16

The _ is a package that supports spawning processing using API similar to the threading module.

Answer 16

tree

Question 17

May be used to model the hierarchical relationship between a set of elements (including computational tasks).

Answer 17

Tree

The relative positions of these elements within the tree could be used to determine which tasks can run in parallel and which are (sequentially) dependent on each other.

Question 18

In a computational setting, the number of venues may correspond to the number of processors, and the number of days needed for the tournament corresponds to the time needed for the computation.

Compared with the sequential 7-day solution, the parallel 3-day solution finishes 7/3 faster.

In the setting of parallel computing, this quantity is called the _.

Answer 18

speedup of the computation

Question 19

These have additional circuitry via which the gate outputs can be enabled or disabled.

Answer 19

Tri-state gates

These are useful in digital systems where devices communicate via common wires called buses. Only one device can talk at a time; the others are disabled. These provide the opportunity to introduce a bus.

Question 20

It is used to send control signals and data between the processor and other components.

Answer 20

The bus

high-speed internal connection

• The PCI bus, Ethernet, FireWire (IEEE1394), and USB are commonly used standards.
• Buses also model other communication systems with shared resources (such as wireless systems)

Question 21

In a computer network, there are mainly six
types of physical topology, they are:

Answer 21

1. Bus Topology
2. Ring Topology
3. Star Topology
4. Mesh Topology
5. Tree Topology
6. Hybrid Topology

Question 22

Conclusion
* Trees and graphs can represent parallelism and distributed computing.
* The first area in which parallelism was explored was circuit complexity.
* The simplicity of circuits as a model was a key reason, as was the relation of the circuit model to physical circuits.
* Limiting parameters such as fan-in, types of gates, and uniformity of construction allowed the investigation of different computational complexity questions.
* Circuit complexity strongly relates to the complexity of parallel computation.

Answer 22

Noted