CS475 Lab 6: Back to Card Game

Introduction

The purpose of this exercise is for you to better usderstand and analyze the card game and associated algorithm that we did in the first day of class. In the lab, you will be in a small group, actually (re)play the game a few times, and try to think about some questions about it (mostly easy, some subtle, and some that will require offline thinking).

Card Game Rules:

Basic step: repeat ad nauseum (while true do):

receive a card from the left
compare with card in your right hand (if you have nothing in the right hand, i.e., in the beginning, just keep the one you get)
keep largest (swap if needed)
give a card to the right

Protocol

Only right hand used for communication
Keep left hand card private (close to the chest)
Last player places output card face down and stacks them up.
Only the first player does input and only the last one does output.
One team leader/conductor (feeds inputs from a deck of cards)
Ace is highest

Let's Play!

Split into groups with 5 players: 4 PEs (precessing elements) and one conductor. Play the game with only 4 cards. Replay a couple of time and look at the cards coming out. Discuss what the algorithm does.

Now let's analyze the algorithm, qualitatively as well as quantitatively.

First set of questions:

set that the number of cards is equal to the number of PEs (p). Define one step as one iteration through the read-compare/swap-optionally-write cycle.

After how many steps will the i-th PE receive its first card?
How many steps does the i-th PE execute?
What is the invariant that holds after the i-th PE has executed P steps?
Analyze the total execution time of the algorithm, from sart to finish.

Second set of questions:

We now want to use the p-PE "machine" to process a larger number of inputs, say n=k*p. So play the game a couple of times with 8 cards. Carefully observe what's happening, and then answer the following questions.

After the first (and in general, the i-th) PE has read p cards (i.e., one round), what can you say about the cards that it currently holds? And any others?
Same questions as above, but after the PE has read all n=k*p cards?
Generalize all the details above and determine precisely the algorithm, when/what is to be output, how are data stored, how many rpunds/passes, and what is the job of the conductor.
Derive precisely the execution time of the algorithm.