Presentation - Georgia State University

Report
Integrating Concepts from Parallel and Distributed Computing into
the Undergraduate Curriculum
Introducing Parallelism
through Sorting
Eileen Kraemer
The University of Georgia
Department of Computer Science
Overview
We are implementing an integrated approach to the
inclusion of concepts in Parallel and Distributed
Computing (PDC) in the undergraduate Computer
Science curriculum.
Timeline:
– Spring ‘11
• Intro to Computing and Programming (CSCI1301)
– Fall ‘11
• Software Development (CSCI 1302)
– Spring’12
• C++ and Unix Systems Programming (CSCI 1730)
• Data Structures (CSCI 2720)
The University of Georgia
Department of Computer Science
Intro to Computing & Programming
Adaptation of this course involves the inclusion
of several guest lectures, the first of which uses
an evaluation of sorting algorithms to motivate
and define parallelism and provide a platform
for the discussion of the benefits and limitations
of parallel processing.
Thursday, April 21st
3 sections
~100 students
The University of Georgia
Department of Computer Science
Introducing Parallelism
Concepts:
–
–
definition and rationale of parallel and
distributed computing
parallel sorting
The University of Georgia
Department of Computer Science
Pre-test
Students were first asked to complete a
survey of their knowledge of parallelism,
sorting, and time complexity concepts.
– See appendix for questions and representative
responses.
The University of Georgia
Department of Computer Science
Motivating the notion of cost
Human Bubblesort
– Roles:
• Processor
– Directed the students to change places, according to algorithm
• Array elements 0 .. 7
– held up signs with their value (57,92,77, ...)
• Comparison counter
– Given a bag of 50 Tootsie rolls. Had to pay one per compare.
• Swap counter
– Given a bag of 50 chocolate eggs. Had to pay one per swap.
• Step counter
– Kept a tally of the number of operations.
The University of Georgia
Department of Computer Science
Time Complexity Analysis
XXXXXXXX
We keep track of the
number of
XXXXXXX
comparisons & swaps &
then
XXXXXX
use this sketch to
convince
XXXXX
ourselves that
Bubblesort
XXXX
is an n2 algorithm.
XXX
The University of Georgia
XX
Department of Computer Science
Human MergeSort
Students again act out the process of
sorting an array of 8 elements.
Use Mergesort
Time Complexity Analysis performed
The University of Georgia
Department of Computer Science
MergeSort: time complexity
1
2
3
4
–
–
–
X
5 XX
6 XX
7 X
8 X
9 XX
XXXXXXXX
XXXX
XX
X
11 -
XXXX
12 13 14 -
X
15 XX
16 -
X
17 X
XX
18 -
The University of Georgia
Department of Computer Science
19 -
XX
X
Observation:
The “array elements” spend most of their
time waiting around with nothing to do
Idea:
– use more processors!
The University of Georgia
Department of Computer Science
Human Parallel MergeSort
The University of Georgia
Department of Computer Science
Time complexity analysis & discussion
faster in terms of time (steps)
– but same number of comparisons
– and there’s a limit to the benefit of add’l
processors
– and some processors participate only briefly
• sequential elements remain
The University of Georgia
Department of Computer Science
Conclusion
What affects running time?
– size of problem
– choice of algorithm
– use of parallelism
• nature of problem; percent sequential
– code optimization
– leveraging domain knowledge
• characteristics of input set (e.g., already ordered)
The University of Georgia
Department of Computer Science
Post-survey administered
Currently under analysis
The University of Georgia
Department of Computer Science
Appendices
The University of Georgia
Department of Computer Science
Explanation ...
This lecture was presented on 4-21-11 to
100 undergraduate CS students.
Compilation and analysis of their
responses is under way and will be
included in this appendix. Results of
analysis will be incorporated into the
presentation.
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
What does “parallel computing” mean?
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
What are some of the benefits of parallel
computing? That is, why might parallel
computing be useful/helpful?
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
How are these benfits limited, if at all?
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
What are some of the costs of parallel
computing?
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
Imagine that you have 8 test papers and that you
want to put them into order by grade, from
lowest to highest. The operations that you can
use in performing the sort are:
– to compare the values of two papers
– to swap the locations of two papers in the collection
You don’t have any information about the actual
test grades or the initial ordering of the test
papers.
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
How many comparisons might you have to
perform, roughly?
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
How many swaps might you have to
perform to sort the papers?
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
Assume that each compare or swap takes
one second, an any other work takes 0
time. How long might it take to sort the
papers?
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
Now, imagine that you are asked to sort
1024 papers rather than 8. You can have
some friends help you, but you have to pay
them $5 to enter the room and $1 for each
time step (time required for a compare or
swap) during which they are present. Your
goal is to minimize the time and the cost of
performing the sort.
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
Explain how you and your friends would
share and coordinate the work of sorting
the papers.
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
How quickly can you sort the papers now?
Explain, briefly.
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
How many comparisons are required?
Explain, briefly.
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
How many swaps are required? Explain,
briefly.
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
How many friends would you use?
Explain, briefly.
The University of Georgia
Department of Computer Science
Pre-test Questions & Responses
Name all the factors you can think of that
might affect the running-time of a sorting
program. Then, number the factors in
order, using #1 for the factor that has the
most effect and higher numbers for factors
with lesser effects.
The University of Georgia
Department of Computer Science

similar documents