Note: I accidentally deleted the orignal description of this assignment. This is a reconstruction. -- Prof. Cunningham
This assignment's due date was extended to 13 February because of the University 5-day shutdown because of the ice storm.
Do exercises 5, 6, and 8 on page 22 of the Chandy/Taylor textbook. Implement and test the programs.
Because I scheduled an exam on the due date for this assignment, I will not consider it late if turned in by Tuesday, 5 March.
Implement a PCN procedure primes(n,P) that computes and returns the list P of all prime numbers less than or equal to integer n, for n >= 1. The primes in list P must be in increasing order.
Remember that an integer m, m > 1, is prime if and only if the only positive integers that divide m are 1 and m. Furthermore, note that 2 is the first prime and any larger integer is prime if and only if it is not divisible by a smaller prime.
The algorithm I want you to use is a concurrent "pipeline" variant of the Sieve of Eratosthenes.
Suggestion: You may want to connect a procedure to the right end of the pipeline that creates and connects a new cell for each value that reaches it.
Test your program in an appropriate manner. Use several different values for n. The main program must display the list of primes returned in a pleasing format.
Hand in a listing of your program and printouts of your test results to Professor Cunningham by the due date. (The Unix script commands enable terminal interactions to be captured in a file.) Also email a copy of your program source code to Professor Cunningham at cunningham@cs.olemiss.edu.
Remember that the School of Engineering's Honor Code is in effect in this class.
Implement and test a PCN program for the following "message router" problem. Submit a listing of your program and output from your tests.
Consider a message router with M sender channels (numbered from 0) and N receiver channels (numbered from 0). One sender is connected to each sender channel and one receiver to each receiver channel. From time to time a sender may send a message to one of the receivers via the router--perhaps a different receiver for each message.
A message consists of a finite sequence of tokens. A sender presents one token at a time to the router. Likewise, the router presents one token at a time to the intended receiver.
Tokens are of three types. A header token marks the beginning of a message and identifies the intended receiver's channel address. A data token carries data associated with the message. A trailer token marks the end of message. A message begins with a header token, continues with zero or more data tokens, and ends with a trailer token. Neither data nor trailer tokens carry any information that identifies the receiver of the message. The router must not change the value of the data. However, the router may modify the address field of the header token during routing of the message to the intended receiver.
The order of the tokens in a message is important and, therefore, must be maintained by the router. Hence, the tokens of multiple messages cannot be interleaved on the channels connected to the senders and receivers.
The router itself consists of an M * N grid of switches. Each sender sends its messages to a different row of the grid and each receiver receives its messages from a different column. The tokens of a message travel along a row until the destination column is encountered then travel along the column toward the receiver.
The router should close all receiver channels and terminate when all sender channels have closed and all messages have been delivered.
For example, we can picture a router with three sender channels (at the left, numbered from 0 at the top) and four receiver channels (at the bottom, numbered from 0 at the left). (The paper handout has a drawing.)
Challenge: Implement the switches in such a way that they do not need to know their locations within the grid.
Do one of the following programming assignments.
This subproblem was motivated by the DNA string matching procedure discussed in section 7.4.1 of the Chandy/Taylor textbook.
Implement a PCN procedure substrings(str,sub,P) that takes strings str and sub and returns a list of all positions at which the substring sub appears in the base string str. The first character (if any) in the string is at position 0, the second character at position 1, etc. A substring occurs at a position k of the base string if the substring's first character matches the character at position k, its second character matches position k+1, and so forth until all of the substring's characters match the characters of the base string. Different occurrences of the substring may overlap.
Both str and sub might be quite long, so a solution that constructs the possible elements of the list P concurrently might be advantageous (e.g., difference list).
Examples: Let b = "010110111011110".
substrings(b,"01",P) terminates with
P defined as [0,2,5,9].
substrings(b,"11",P) terminates with
P defined as [3,6,7,10,11,12].
substrings(b,"00",P) terminates with
P defined as [].
This subproblem asks you to implement a program using the manager-worker load-balancing technique described in section 7.4.4 of the Chandy/Taylor textbook.
Implement a PCN program that consists of a manager and n workers. Each worker repeatedly accepts two strings, str and sub, from its input stream, performs the search substrings(str,sub,P), and returns the list P on its output stream.
The manager accepts tuples {str,sub} describing a string search task and allocates the task to an idle worker. The manager tries to keep all four workers busy if there are more tasks to do. However, the manager should not assign a task to a worker until the worker has completed its previous task. When the manager receives the results from a worker, the manager should print the base string, the substring, and the resulting list of positions.
Note: You will need to use sys:distribute and sys:merger to communicate between the manager and the workers. You may design the structure of the messages passing back and forth between the worker and manager processes as you need---more than data than str, sub, and P may need to be passed.
Test your program with various numbers of workers (i.e., values for n), but let one of those values be 4. Also test your program with several different strings and substrings. The strings do not have to be long, just appropriate for testing the various programs.
Document and format the source code appropriately. Display the printed output in a pleasing format. Hand in a listing of your program and printouts of your test results to Professor Cunningham by the due date. Also email a copy of your program source code to Professor Cunningham at cunningham@cs.olemiss.edu.
Remember that the School of Engineering's Honor Code is in effect in this class.
This assignment is similar to problem 6 in chapter 10 of the Chandy/Taylor textbook.
Using the information hiding style, design a PCN procedure bintree(I) that encapsulates a binary search tree "data structure". Implement and test the procedure. (Each node of the binary search tree holds one integer value; the values in the tree are ascending from left to right.)
Within bintree(I), the binary search tree "data structure" must be represented by a concurrent tree of programs. That is, each node program will hold one integer from the data structure and the concurrent node programs will communicate by exchanging messages.
In procedure bintree(I), parameter I is a stream of "command messages" to the program. Implement both of the following "commands":
Also implement one of the following "commands":
You may need to implement other "commands" internal to the tree of programs.
Suggestions: Implement and test your program in pieces. For example, you may want to get the command/response interface of bintree working before you implement the concurrent tree of programs. You might possibly want to implement the tree as a data structure within bintree before implementing it as a tree of programs. Since the delete and inorder commands are more complicated, you may also want to get insert and find commands working before you implement the other command.
Test your program thoroughly! Document and format your program appropriately. Hand in a listing of your program and printouts of your test results to Professor Cunningham by the due date. Also email a copy of your program source code to Professor Cunningham at cunningham@cs.olemiss.edu.
Challenge (for extra credit): Use a balanced binary tree technique, such as the AVL tree algorithms, to implement the concurrent tree of programs.
Remember that the School of Engineering's Honor Code is in effect in this class.
UP to ENGR 664 root document?