Learning Scenario - Time-to-Science (Excel)

Basic Model:

Description

Time-to-Science explores the benefits and detriments of increased parallel computing. The user is presented with two sliders that control the data load and the work load. The purpose and goal of the model is to optimize the time it takes to complete a task by finding the correct number of processors needed. An inverse linear relationship exists between the number of processors and processing time.

Background Information

Parallel computing is one of the most under-used and under-optimized features of modern computing. While the initial thought to a computer user might be that more cores would get a process done faster, in actuality, there is a small amount of time required to transfer workload between processors-known as overhead-which can harm the overall productivity of the computations. Initially, when more processors are added, the overhead decreases significantly. After that, though, more processors just become a hindrance. This phenomenon is known as Amdahl's Law. The goal, then, of parallel computing and this model is to find the right balance between number of processors and the data load given. Through the graphs and data displayed on this model, students will be able to see the point at which more processing power becomes unnecessary.

Science/Math

The fundamental principle behind this model is HAVE = HAD + CHANGE. At any point, the following calculations are happening:

• 1. The workload time per processor is calculated in the TTSA column (Workload/Processors) according to the user set variables
• 2. The total data transfer time between processors is calculated in the TTSB column (Data Load*Processors) according to the user set variables
• 3. The total time to complete the ask is calculated in the TTST column (TTSA+TTSB)
• 4. All three columns are plotted on the graph as the dependent variables against the independent variable, the number of processors

The changes in this scenario mimic the real-world problems that even the simplest computer user faces. When applications use parallel computing and multi-core processors to accomplish large tasks, they are limited by Amdahl's Law more so if the data load is large. Basically, if the calculations are interdependent on each other (i.e. calculation of a galaxy that is dependent on the velocity and position of other planets), Amdahl's Law will be more of a limiting factor, while with multiple individual calculations it will not be. Through experimentation, one can learn about the inverse relationship between the number of processors and the processing time and when this idea can be applied.

Teaching Strategies

An effective way of introducing this model is to present students with a hypothetical situation of a supercomputer and discuss the benefits and detriments of adding more nodes to the system. Ask the following questions:

• 1. What would the addition of more nodes to a supercomputer do to the overall productivity of the computer? Explain.
• 2. How does overhead affect the overall efficiency of computers? How would overhead be a problem for supercomputers?
• 3. Picture the overhead required for dividing the data between the multiple processors of a supercomputer. If the system had 150 processors, how would it affect the time for the task to complete? Could some tasks be better completed with only a few processors?
• 4. What type of relationship do you think there is between the number of processors and the time it takes to complete the task? Explain your answer.

Students should write down their hypotheses and compare them to the results of the simulation.

Implementation:

How to use the model:

This model has a couple inputs that can be manipulated in order to study the affect the variables have on the graph of processors versus processing time:

• 1. The work load is the total number of computations necessary to finish the work
• 2. The data load is total amount of data that must be held and/or transferred by the processors in order to complete the job

These parameters may be changed by moving the respective sliders at the top of the model. The resulting graph will update instantaneously. After the model has been recalculated, the graph may be analyzed and studied in relation to the outputs on the left of the graph. Work load and data load are calculated into the model to determine the computation and overhead time. TTSA, TTSB, and TTST may be viewed in numerical form next to the graph. For more information on Excel, reference the Excel tutorial at: http://shodor.org/tutorials/excel/IntroToExcel.

Learning Objectives

• 1. Investigate and understand Amdahl's Law and exploring how the addition of processors does not always optimize the processing time
• 2. Understand Big-O and its application to parallel computing

Objective 1

Amdahl's Law dictates that with an increasing number of processors comes an increased amount of overhead. When the time it takes to divide the tasks between processors becomes greater than the time it takes to actually compute the task, then the computer hits a diminishing returns and is not working in the most efficient method possible. This model will demonstrate Amdahl's Law by allowing students to decide the work load and data load for the system. Students should change the sliders on the graph and answer the following questions:

• 1. Change the data load and workload to something moderate (~50 work load and ~.031 data load). What is the overall shape of the graph? As the number of processors increases, what is the increase in speed? (Look at the TTSST graph)
• 2. What do the TTSA and TTSB graphs represent? Why are their shapes the way they are?
• 3. Find the minimum of the TTST graph. What does this point represent? In dealing with parallel computing, would you want to avoid or aim for this point? Explain.
• 4. What does the intersection between the TTSA and TTSB graphs represent? How is this related to TTST?
• 5. If the Data Load was very small (~0.002) and the Work Load large (>81), what would be the point of diminishing returns? Is this point visible on the graph?

Students should now have a better understanding of Amdahl's Law and the advantages and disadvantages of increasing the processor number. They may compare their answers to these questions to their hypotheses and analyze the difference between the two.

Objective 2

Big-O notation describes the complexity of an algorithm. It is used in computer programming to estimate the amount of memory that will be required to process a large number of inputs. Big-O can be applied to the Time-to-Science model by analyzing the shape of the graph. In a hypothetical situation, the processing speed increases linearly with more processors [O(n)]. Ask the following questions to guide the students in analyzing the model for Big-O:

• 1. The y-axis of this model displays the speed increase, while the x-axis displays the number of processors. What is the relationship between the two variables?
• 2. Set the model to display a hypothetical scenario with no workload. What shape does the TTST graph always take, no matter what the data load is set at? Why?
• 3. One way programmers calculate the efficiency of an algorithm is to analyze a function in terms of O(n), pronounced "Big-Oh of n." A function that varies in complexity directly with the number of inputs it has is O(n) and is linear, and one that varies directly with the square of the number of inputs it has is O(n2). Which one would you say this model is? Explain.
• 4. When calculating Big-O, the constant in the algorithm is always ignored. This can be done, since n will eventually overpower the constant, and the behavior as the function approaches infinity is what is most important for analytical purposes. What would both the constants and n represent in parallel computing?

Extensions:

• 1. Explore the other limiting factors to processing power, such as physical limitations
• 2. Study the application of parallel computing to crash simulations, as used by the NCAC
• 3. Learn about the different types of parallel computing and the advantages/disadvantages of each

Extension 1

Parallel computing can be limited by more than just the number of processors in the system. It can also be slowed by factors such as the physical space between the physical size of the transistors on microchips and inefficient communication to the processor. While Amdahl's law cannot be completely eliminated in a program, the way that the program communicates with the processor can be more efficient. Ask students to research ways in which the size of the microchip and the communication can prohibit the computer from running efficiently. This can be tied into a variety of subjects and taken to a variety of levels depending on the field being studied. Ask the following questions:

• 1. What physical limitations does a processor have? Why is there always going to be a limit on how small a single processor can get? How does parallel computing hope to solve this problem?
• 2. There are many different things that a programmer can do to improve the efficiency of his or her program in communicating with the processor. Name a few of these and how they help to improve efficiency.

Supplemental Resources: ARM Documentation on parallel computing: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0538e/BABFGJGF.html

Extension 2

Many fields require parallel computing in order to process large amounts of data and effectively analyze a simulation. One such example is the National Crash Analysis Center (NCAC) at George Washington University, which uses supercomputing in order to analyze crash tests. Instead of spending thousands of dollars on actual crash tests, the NCAC is able to plug in models of cars, run the simulation, and find the extent of the damage to the car. Students should search for the NCAC and study their application of parallel computing to a real-world situation. Ask the following questions to guide their research:

• 1. How does the NCAC use parallel computing? Why do they need to use supercomputers to run these simulations?
• 2. Would the NCAC's model be limited by the same factors discussed earlier in reference to parallel computing? Think and search for some limitations that could be applied to this situation.

Extension 3

There are multiple classifications of multi-processor machines. Have students research the different types, including SISD, SIMD, MISD, and MIMD and their uses. Describe this in terms of "coarse" and "fine" parallelism. Ask the following questions:

• 1. What is the difference between the four different types of data processing? Why would one be advantageous over another?
• 2. Define the terms "coarse" and "fine" parallelism. Why are they called that? Match up each type of parallel computing with either term, "coarse" or "fine."
• 3. What are the problems that arise by using each system? What are their limitations?

Related Models

Bunny Comparison

• The Bunny Comparison model will extend the idea of limiting factors to a situation to something other than computers. In this simulation, the population of bunnies grows exponentially, but it is limited by factors such as carrying capacity and predators. While students studied the diminishing returns of multiple processors and the limiting factors to having multiple processors in the Time-to-Science model, the bunny model will show how limiting factors affect populations and their growth.


• Population Growth
• The HAVE = HAD + CHANGE model is more pronounced in the Population Growth and allows students to see the changes they make instantly. Similar to the Bunny Comparison model, this simulation sets up a population that is growing at a specific rate according to a number of factors. The population has an equilibrium point where the deaths and limiting factors are equal to the number of births. This idea connects to the Time-to-Science model by using limiting factors. In the Time-to-Science model, students studied the factors that prohibit a system of processors from completing a task when the number grew too large. Population growth reflects the same idea of limiting factors found in the Time-to-Science model.