02158 Concurrent Programming        Fall 2024
Lab : Go Concurrency

Home

Plan

Material

Purpose

Time and Place

Preparations

You should download the command line development tools for Go as desribed in Minilab 5

If you want to use a particular IDE, you may import a proper Go-plugin as described here. However all problems are readily handled with an ordinary text editor and the command line tools.

You should be familiar with the Go concurrency notions as presented at the lectures and have had a look at the corresponding examples.

For further information about the Go language, see golang.org and especially the reference manual at https://golang.org/ref/spec.

Go has an elaborate module notion enabling groups of packages (modules) to interact in a controlled manner. In this lab, however, it suffices to use a more simple approach in which only a single main package with a main() function is compiled and executed using the go run <program>.go command.

Instructions

The lab has two exercises A and B. Exercise A is an introductory exercise, while Exercise B will be part of Mandatory Assignment 4.

A: Voting System

In a small state an election takes place between two candidates, A and B. In order to have transparent result, the votes will be shown in real-time while being counted. From a number of polling stations the results are sent to a broadcaster. For a single test polling station this is shown in the program voting.go. Here the goroutine station simulates a polling station and the main program acts as the broadcaster.

Download the program and run it using the command:

  go run voting.go

Now, for the real election eight polling stations are to be used. The results from these are to be collected through a binary tree of collector nodes each relaying the results from two stations/nodes towards the root node which itself should deliver the results to the broadcaster.

For eight instances of the polling station, setup a pattern of channels and (seven) collector nodes such that the results are shown as soon as the last station has sent its last result.

You may start by writing the collector node and test it using two polling stations and tree dedicated channels. Then generalize to eight stations.

Hint 1: Draw the communication structure! How many channels will you need?
Hint 2: Use a systematic numbering of the collector nodes (and their output channels). If you start giving the root # 1, what would be the numbers of the two childrens of any node # i ?
Hint 3: Declare an array of sufficiently many voting channels and distribute them to the collectors according to your numbering scheme as you go along creating the goroutines.

Option: To reduce the results streams, mitigate the broadcaster to send out the current tally only every two seconds while still collecting results. For this, a regular tick channel may be used.

B: Sieve of Eratosthenes

Given a positive integer constant N you should write two versions of a Go program that finds the first N prime numbers [starting at 2] according to the concurrent version of Eratosthenes' Sieve described in [Andrews 7.6.3]. The solution should print the resulting prime numbers in order like this (for N=5):

    The first 5 prime numbers are:
    2
    3
    5
    7
    11
    Done!

Basic Version

A skeleton program for a solution is found in eratosthenes.go which defines functions for two different goroutines: sieve and odds.

Starting from this program, you should:

• Define sieve shuch that it receives prime number candiates on the in channel and sends filtered candiates on the out channel.

  The goroutine should hold the first candidate received as is "own" prime number and discard any multiples of this from the output stream.

• Define odds such that it generates a sequence of odd numbers on the out channel.

  Furhtermore, the odds goroutine should be seen as holding the first prime number, 2, and print that when appropriate.

• Declare and initialize a sufficent number of synchronous channels and create a pipeline where the output of a single instance of odds is pipelined through N-1 instances of sieve.
• The main program should receive any numbers on the out channel of the last sieve element and discard them.
• The odds goroutine should output sufficent odd numbers to fill all the sieve elements. If you output 10*N odd numbers, you will be safe for N < 10⁶. Any surplus numbers should be gobbled by the main program.

• When the odds goroutine has output the last odd number, it should print its own result (2), and then close the out channel.
• When a sieve element observes that the in channel is closed, it should print its own prime number and then close the out channel.
• When the main function sees that the output channel from the last sieve element closes, it should print the end message.

Hint: Since all numbers communicated are positive, the closedness of a channel can be established if the integer type's "null" value, 0, is received rather than using the ok communication flag.

Try to increase N. Do you consider the concurrent version of Eratosthenes' Sieve an efficent way of finding prime numbers?

Describe your approach and hand in your Go program as eratosthenes1.go

Self-terminating Version

Always sending 10*N odd numbers through the pipeline will generally be a waste. On the other hand, as the density of prime numbers decreases as N grows larger, for N very large, it might not even be enough. Therefore you should now make a modified version of the basic sieve in which the generator routine stops the odd number stream as soon as it detects that the last sieve element has received its prime number.

• The sieve goroutines should remain unchanged.
• The out channel of the last sieve element should be directed back to odds (using an extra parameter) rather then being read by the main program.
• When odds detects a number from the last sieve element, it should stop the odd number stream and start the termination procedure.
• When odds can ensure that the last prime number has been printed, the main progam should be informed via a dedicated communication channel.

Describe your deliberation and hand in your solutions as eratosthenes2.go

Happy sifting!

Hans Henrik Løvengreen, Nov 17, 2024