ECS 223: Reading and Reading Questions
Answers to the
reading questions are due in class, in writing, on the day that
the reading is due.
You do not have to copy the questions.
- Th April 4: Work-Depth models, and Brent's Scheduling Theorem.
Read page 11-top of page 14 in the Blelloch/Maggs Parallel
Algorithms chapter (hereafter PA), and pages 15-end of secion 2.4 in
the Vishkin Thinking in Parallel eBook (hereafter TIP).
We won't be getting into network architectures right now.
- Assume a circuit only includes add gates with two
inputs, as in
Figure 4 in PA. Is it possible to
design a circuit that adds up n numbers in O(1) time? Why or why not?
- At the top of page 16 in TIP, he means that all of the
three PRAM schedules numbered 2,3,4 are asymptotically
possible for the Work-Time algorithm in 1.
State formally and precisely
what it means that, for instance, schedule
3 is asymptotically possible. Where do you put the big-Oh and why?
You do not need to write out what Big-Oh notation means, you
can assume that is standard. Review it yourself if necessary.
Let me try this again.
What I think he wants to say is that
given the work-time algorithm in item 1,
it is possible
to produce a PRAM algorithm which in some asymptotic sense has
the running time described in item 2,3 or 4. I'd like you to write
this down as a more formal statement, using big-Oh notation, just
for statement 3.
- For Tues 4/9: Prefix sums. In PA, read section 3.2. In
TIP, read from the beginning of Section 3 through the end of
3.1. On segmented scans, read Section 1.5 in
Blelloch's chapter
on prefix sums, which contains lots of other useful
information, including a broader definition of the operations
for which scan is useful. You'll have to skip back to Section 1.3
to see how the split in quicksort is done.
Section 1.5 justifies segmented scan by
referring to Section 1.4; don't worry about that for now,
we'll talk about it in class.
- Do exercise 2 in Section 3.1 of TIP. You can assume that all the
processors know address A.
- Describe the quicksort split using scan, either in words or in pseudo-code.
- For Thurs 4/11:
Read about pointer jumping in Section 9.2 of TIP (starting on page 64).
Start reading
about the selection problem, starting at the beginning of Section 5 in TIP
and going until the end of Section 5.2.
-
In Section 9.2 he mentions the question we had at the end of class,
"We note that even if we revise the algorithm to avoid
repeated pointer jumping for elements whose next pointer already
reached the end of the list, the work complexity will remain
O(n lg n)."
Why is this?
-
In Algorithm 1 in Section 5.2, we break the problem into m/(lg m) groups
of size (lg m) each. Would the Reducing Lemma still hold if we
broke the problem up into sqrt(m) groups of size sqrt(m) each?
- For Tuesday, April 16: Read Section 2.7 in the book
An Introduction to Parallel Algorithms (AIPA)
on three-coloring a ring.
We'll end up using the optimal Algorithm 2.10, but the "superfast"
algorithm is cool in other ways. We'll do the Exercise 2.45 mentioned
as part of the algorithm in the homework.
- Describe using Algorithm 2.9, the initial coloring algorithm,
on a tree instead of a cycle. Assume the tree is
rooted, and given by nodes with parent
pointers, so that each node has one out-going pointer, with the root node
pointing to itself.
- Thursday, April 18: John Owens on GPUs and CUDA. Here are
his slides.
- Tuesday, April 23: Homework due. We will discuss Problems 2.44 and 2.45,
along with more on radix sort, in class. This will lead in nicely to
John Owens' discussion of radix sort on the GPU on Thurs 25.
- Thursday, April 25: John Owens on scan and sort on the GPU. Here are
his slides.
- For Tuesday, April 30: Read AIPA from the beginning of Chapter 3 to the end
of 3.1.1, on list ranking.
- Lemma 3.3 shows how to identify an independent set from a 3-coloring in
O(1) depth. What depth would be required just to pick the color assigned to
the most elements? Would that impact the running time of the overall algorithm?
- For Thursday, May 2: Read AIPA Section 3.2 on the Euler Tour technique.
- For Tuesday, May 7: Read AIPA Section 3.3 on rake and compress.
- Section 3.3.3 describes how to make an arbitrary tree binary.
Is it possible to do this in O(1) depth? Explain how, if possible, and
why not, if impossible.
- For Thursday, May 9: Read AIPA Section 5.1, up through 5.1.2, on
connected components. We may get to start the section on Minimum Spanning
Trees as well.
- Exercise 5.1 - how do you remove the concurrent write?
- For Tuesday, May 14: MapReduce: simplified data processing on large clusters, by Dean and Ghemawat.
- Consider the colored prefix-sum
homework problem we did (2.44). How would you solve this in the Map-Reduce
framework? Can you produce the output records in the same order in which
they appeared originally? Note that you may use more than one cycle of
Map-Reduce in a program.
- For Thurs, 5/16, we will start reading
Sorting, Searching, and Simulation in the MapReduce Framework, by Goodrich, Sitchinava and Zhang. I expect we will get through the end of Section 2.
Instead of the PRAM simulation in Section 3,
I will try to describe the easier EREW simulation from Section 7 of
A model of computation for MapReduce, by Karloff, Suri and Vassilvitskii.
No reading question.
- Tues, 5/21: Read Section 9.2 on independent
set in a planar graph, refering back to the probability review in Section
9.1 as necessary; in particular, Chernoff bounds are on pages 438-9.
- In the proof of Lemma 9.2, why do they have to consider every other vertex
(eg. only the even ones) along the cycle, in order to apply the Chernoff
bound? Can you think of some way to apply the Chernoff bound to the similar
algorithm we did in the first problem of HW 2?
- For Thurs, 5/23: Read Section 9.4 through the end of 9.4.2.
- The matrices g(0) and g(1) are defined as the inverses of the
matrices fP(0) and fP(1). Verify this arithmetically.
Are these the left inverses, the right inverses, or both? Is it important
that they are the left inverses, the right inverses, or both?