Parallel Algorithm Design

The parallel algorithm for a given problem attempts to divide it into sub-problems which can then be solved concurrently on the different processors of a parallel computer.

The design of a parallel algorithm can be viewed as consisting of four stages - Partitioning, Communication Analysis, Granularity Control and Mapping. The following simple example illustrates some of the issues involved in each of the stages.

Consider the following scenario: n answer-scripts have to be marked, each of which contains the answers to m questions. The scripts could be viewed as the data, and the marking process itself as the computation to be performed on it.

In order to design a parallel solution to this problem, it must first be decomposed into smaller tasks which can be executed simultaneously. This is referred to as the partitioning stage.

This can be done in one of two ways. Each script could be marked by a different marker - this would require n markers. Alternatively, marking each question could be viewed as a task. This would result in m such tasks, each of which could be tackled by a separate marker, implying that every script passes through every marker.

In the first approach, the data (scripts) is first decomposed and then the computation (marking) is associated with it. This technique is called domain decomposition.

In the second approach, the computation to be performed (marking) is first decomposed and then the data (scripts) is associated with it. This technique is called functional decomposition. The partitioning technique that will be chosen often depends on the nature of the problem.

Suppose one needs to compute the average mark of the n scripts. If domain decomposition was chosen, then the marks from each of the markers would be required. If the markers are at different physical locations, then some form of communication is needed, in order to obtain the sum of the marks.

The nature of the information flow is specified in the communication analysis stage of the design. In this case, each marker can proceed independently and communicate the marks at the end. However, other situations would require communication between two concurrent tasks before computation can proceed.

It may be the case that the time to communicate the marks between two markers is much greater than the time to mark a question. In which case, it is more efficient to reduce the number of markers and have a marker work on a number of scripts, thereby decreasing the amount of communication.

Effectively, several small tasks are combined to produce larger ones, which results in a more efficient solution. This is called granularity control. For example, k markers could mark n/k scripts each. The problem here is to determine the best value of k.

The mapping stage specifies where each task is to execute. In this example, all tasks are of equal size and the communication is uniform, so any task can be mapped to any marker. However, in more complex situations, mapping strategies may not be obvious, requiring the use of more sophisticated techniques.

Parallel algorithm design is an interesting and challenging area of computer science which requires a combination of creative and analytical skills.

Recursion

A definition is said to be recursive if the name of the concept being defined recurs within its definition. Put in other words, a process or a function is recursive if it can re-activate itself. You can find out about recursion here.

An unusual use of recursion in a definition comes from Professor Seymour Papert, Professor of Media Technology, at MIT (The Massachusetts Institute of Technology) and the inventor of the graphical programming language LOGO. Here are Papert's instructions on how to make a circle. First, take a step forward, then turn a little to the right, then make a circle. His description is a very unusual one because it describes a circle as a process rather than as a static geometric shape. His description is recursive because making a circle is defined in terms of making a circle. Recursion is often used to define functions.

Factorial

The factorial of a number n, written n!, is the product of the numbers between it and zero. A function to compute factorials can be defined like this.

0! = 1
n! = n * (n - 1)!

You can use the function below.

Fibonacci

In the fibonacci sequence, each number is the sum of its predecessors. The first two numbers are both one. The fibonacci function is defined like this.

fib(0) = 1
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

You can use the function below.

Greatest Common Divisor

Just to emphasize that recursion is not a new idea, here is a method for calculating the greatest common divisor [or highest common factor] of two numbers. The method was invented by the Greek mathematician Euclid of Alexandria who lived between [approximately] 330BC and 275BC.

gcd(x, y) = y, if x is zero
gcd(x, y) = gcd(y, x), if y < x
gcd(x, y) = gcd(y mod x, x), otherwise

You can use this function below.

Prime Factors

The function for finding the prime factors of a number n is relatively straightforward.

1. If n is even, one factor is 2, then find the prime factors of n/2.

2. If n is divisible by 3, remove this factor and then find the prime factors of the remainder.

3. If n is divisible by 5, remove this factor and then find the prime factors of the remainder.

4. If n is divisible by 7, remove this factor and then find the prime factors of the remainder.

5. ...

It might seem that we must first calculate the prime numbers so that we may perform steps 2, 3 and subsequently. In fact, just using the odd numbers will be enough since an apparent factor of 15 will be removed as a factor of 3 and a factor of 5. Our recursive definition uses two functions.

pfr(n) = 2 and pfr(n/2), if n is even
pfr(n) = pf(n, m), if n is odd

The pf function uses m as the odd number counter.

pf(1, m) = none
pf(n, m) = n, if n < m²
pf(n, m) = m and pf(n/m, m), if m divides n
pf(n, m) = pf(n, m + 2), otherwise

You can use the function below.

Base conversion

To convert a number from one base to another is simple if the number can be represented as a single digit; you simply write down the digit. If the number cannot be represented in a single digit then divide by the base, convert the result to the other base and after it simply write down the digit which represents the remainder, even if the remainder is zero. You can try this below. You can enter bases such as those shown below but the method described above cannot be used to calculate unary representations.

• Enter 01 for binary (Base 2);
• Enter 012 for ternary (Base 3);
• Enter 01234567 for octal (Base 8);
• Enter 0123456789ABCDEF for hexadecimal (Base 16).

Recursion

A definition is said to be recursive if the name of the concept being defined recurs within its definition. Put in other words, a process or a function is recursive if it can re-activate itself. You can find out about recursion here.

An unusual use of recursion in a definition comes from Professor Seymour Papert, Professor of Media Technology, at MIT (The Massachusetts Institute of Technology) and the inventor of the graphical programming language LOGO. Here are Papert's instructions on how to make a circle. First, take a step forward, then turn a little to the right, then make a circle. His description is a very unusual one because it describes a circle as a process rather than as a static geometric shape. His description is recursive because making a circle is defined in terms of making a circle. Recursion is often used to define functions.

Factorial

The factorial of a number n, written n!, is the product of the numbers between it and zero. A function to compute factorials can be defined like this.

0! = 1
n! = n * (n - 1)!

You can use the function below.

Fibonacci

In the fibonacci sequence, each number is the sum of its predecessors. The first two numbers are both one. The fibonacci function is defined like this.

fib(0) = 1
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

You can use the function below.

Greatest Common Divisor

Just to emphasize that recursion is not a new idea, here is a method for calculating the greatest common divisor [or highest common factor] of two numbers. The method was invented by the Greek mathematician Euclid of Alexandria who lived between [approximately] 330BC and 275BC.

gcd(x, y) = y, if x is zero
gcd(x, y) = gcd(y, x), if y < x
gcd(x, y) = gcd(y mod x, x), otherwise

You can use this function below.

Prime Factors

The function for finding the prime factors of a number n is relatively straightforward.

1. If n is even, one factor is 2, then find the prime factors of n/2.

2. If n is divisible by 3, remove this factor and then find the prime factors of the remainder.

3. If n is divisible by 5, remove this factor and then find the prime factors of the remainder.

4. If n is divisible by 7, remove this factor and then find the prime factors of the remainder.

5. ...

It might seem that we must first calculate the prime numbers so that we may perform steps 2, 3 and subsequently. In fact, just using the odd numbers will be enough since an apparent factor of 15 will be removed as a factor of 3 and a factor of 5. Our recursive definition uses two functions.

pfr(n) = 2 and pfr(n/2), if n is even
pfr(n) = pf(n, m), if n is odd

The pf function uses m as the odd number counter.

pf(1, m) = none
pf(n, m) = n, if n < m²
pf(n, m) = m and pf(n/m, m), if m divides n
pf(n, m) = pf(n, m + 2), otherwise

You can use the function below.

Base conversion

To convert a number from one base to another is simple if the number can be represented as a single digit; you simply write down the digit. If the number cannot be represented in a single digit then divide by the base, convert the result to the other base and after it simply write down the digit which represents the remainder, even if the remainder is zero. You can try this below. You can enter bases such as those shown below but the method described above cannot be used to calculate unary representations.

• Enter 01 for binary (Base 2);
• Enter 012 for ternary (Base 3);
• Enter 01234567 for octal (Base 8);
• Enter 0123456789ABCDEF for hexadecimal (Base 16).

Systems Administration

Most modern computing facilities are based on a wide variety of different hardware, ranging in size from portable PCs to powerful workstations and servers. These machines are usually interconnected as part of a complex network with many different protocols and software packages used to provide the required services. The job of integrating, developing and managing these complex systems is called Systems Administration.

Some typical questions that might concern a systems administrator include:

• With 400 software packages on the system, there will be constant changes and updates required. How can we arrange for 300 machines to always have the same up-to-date version?
• In a network of several hundred machines, there will nearly always be at least one machine which is down. How can we be sure that this doesn't always disrupt hundreds of other machines on the network?
• How can we ensure that valid users have easy access to information on the network, while still keeping this information secure against unauthorised access?
• If it takes one person to install and maintain a single machine, how can we avoid requiring 300 people to install and maintain 300 machines?
• How can we arrange for a user to log on to any one of hundreds of machines and still have access to the same files and programs?
• How can we design the network so that tens of extra machines can be easily added without overloading, or requiring a major re-configuration, of existing systems?

More information about the departmental systems is available here. A good starting point for further information on Systems Administration in general, is the web page for the Systems Administrators Guild (SAGE).

Virtual Reality

Virtual reality (VR) is a technology which allows users to participate in, and interact with, a 3D computer-generated world, or virtual environment (VE). In essence, VR aims to provide a new and more natural means of Human-Computer Interaction.

How Does It Work?

There are two flavours of virtual reality: Desktop and Immersive. Desktop VR simply requires a standard computer monitor to display the 3D world, e.g. popular games on the PC like Doom, Descent etc. can be considered Desktop VR because they allow the player to explore and interact within a 3D environment.

By comparison, Immersive VR requires the use of special display devices to make the user feel more enclosed in the virtual environment. We can do this by either making the displays much bigger (e.g. projection screen systems) or by bringing the displays closer to the eyes (e.g. head-mounted displays, like the one opposite).

We may also use new input devices to allow the user to interact with the world in a natural manner. For example, the person on the right is using a glove device so that they can directly manipulate and select objects in the virtual environment with their hands.

In order to use the head-mounted display to look inside a virtual world, or a glove to interact with that world, we need some form of tracking technology which can monitor 6 degrees of freedom. That is, track the position (x,y,z) and orientation (yaw,pitch,roll) of your head or hand in 3D space. With this information, the computer knows when you move your body part and can update the image of the virtual world accordingly.

What Is VR Used For?

VR arguably provides the most natural means of communicating with a computer because it allows us to use our inherent 3D spatial skills that have evolved over thousands of years (such as walking, gesturing, looking, grabbing etc.) There is a therefore a vast range of potential applications for VR. Below is a small cross-section of some of the uses which VR technology has already been used for:

• Architectural Design: Architects can now use VR technology to designing and walking through a building or room. E.g. here is the UNC Walkthrough Project .
• Art: VR is a new medium for artists to express their visions. For example, take a look at the VR-ART Virtual Gallery .
• Education: Systems have been designed to help disabled children, allow the visualisation of mathematical concepts, perform virtual lectures & conferences etc. For example, here is the Virtual Reality and Education Laboratory and the VIRART Educational Applications of VR page.
• Medicine: There is much interest in the possibility of for virtual surgery and the provision of other aids for the surgeon, e.g. in the fields of ultrasonic imaging, MRI, drug design etc. For example, how do you fancy attending the Virtual Clinic ?
• Training: VR can be used to safely train personnel for high-risk activities. For example, VR technology was used by NASA for their Hubble Space Telescope Repair Training System .
• Scientific Visualisation: Scientific visualisation is the use of computers to understand complex phenomenon. For example, manipulating and viewing complex molecules or computational fluid dynamics models. E.g. click here to see the NASA Ames' Virtual Windtunnel .
• Entertainment: There are of course a number of VR games available in arcades and for your home computer. Here is the Atlantis VR Entertainment Resource Guide .
• Virtual Prototyping: Creating a computer-generated prototype is quicker, cheaper and also easier to modify. The Virtual Manufacturing project at Bath University is an example of this.
• VRML: The Virtual Reality Modeling Language (VRML) is a developing standard for describing interactive 3D scenes delivered across the Internet. Click here for the VRML Repository .

If you want to find more information about virtual reality on the World Wide Web, then you can take a look at Toni Emerson's Internet Resources in Virtual Reality .