with Leigh Ann Yoder
Parallel Processing and a Sorting Network
We began class with a brief discussion about our fairy tales, specifically the tailor and his insertion sort. The students are learning that there are many algorithms for solving the same problem, and it is quite easy to identify the most efficient algorithms. The question becomes, why would you ever want to use an inefficient algorithm if you know there is a better way? Using the tailor analogy, it is easy to see that one needs to consider the specific circumstances of a particular problem in order to choose the most efficient algorithm.
Speaking of efficiency, our computers are NEVER fast enough! Computer scientists are constantly searching for new and improved ways of solving problems quicker. Although our Quicksort from last week seemed quite quick, when working with millions of numbers it could actually turn into a dreadfully slow process.
This week was all about Parallel Processing. We started our lesson with a life size demonstration of a Sorting Network. In a sorting network the students could see that 12 comparisons could actually be done in the time of 5, if we used multiple processors to do the job.
After everyone had a chance to walk through the human network, they were all given a challenge to design their own sorting network. I believe all of the students were successful at this!
Parallel vs. Serial Processing
Next, we compared Parallel Processing to Serial Processing. In parallel processing, several steps of an algorithm can be worked on at the same time, thus speeding up the overall time required to complete the task. Serial processing cannot be done in this manner. Each step of the algorithm must be completed before moving on to the next. The analogy used was digging a ditch. We could employ 12 people to dig a ditch that was 1 foot wide by 12 feet long. Twelve people would complete this task 12 times faster than one person working alone. However, if we wanted to dig a ditch 1 foot wide and 12 feet deep, we could not use this method. The second foot of depth cannot be dug until the first foot is completed.
We wrapped up class with a friendly competition. The students were divided into groups and given the task of adding 32 four-digit numbers. The goal was to divide the task to speed up the process. However, accuracy was important, so they were encouraged to develop a check system. The girls finished first, but the boys came closer to the actual answer.
Next week we will continue learning about Networks, which were introduced this week.