Parallel computing		27.3.2003

Exercise 10

Last lecture at Thu 20.3.2003, last exercises at Thu 27.3.2003

2nd intermediate exam at Tue 1st April 08.00 -- 10.00 at M1.

The total maximum of X-exercises is 22. Total maximum of whole course is 72.

Total number of standard exercises is 39, thus the bonus for x marks is
7.2 * (x-13) / 26, i.e., each mark above 13 is worth ~0.2769 points.

46) Rewrite the game of exercise 32 using Fortran 90 vector
    operations. Implementation of the game of exercise 31 at web page.
    f90 compiler at cs: /opt/SUNWspro/bin/f90. A brief introduction to
    Fortran 90:
    http://www.pcc.qub.ac.uk/tec/courses/f90/ohp/header_ohMIF_1.html

47) Rewrite the game of exercise 36 using Fortran 90 vector operations.

48) Draw a data-flow diagram a prefix sum for N=8. Time optimal diagram
    follows the PRAM prefix algorithm (the picture shows it for N = 16,
    Pmax = 15, Time = 8, Work = 120). 

    Instead, draw the diagram by using at most 3 parallel operations at
    a time. Try to make the whole computation as fast as possible (with
    using 3 processors). Use operations copy  and add . Dividing one
    input (or intermediate results) to input for two operations takes
    one copy operation. Draw each parallel operation to same horizontal
    level.

49) Define a protocol for agreeing a dinner time for N (e.g., 5) persons
    using (GSM) SMS messages. Try to keep the total number of messages
    at minimum. You can assume that all of you know each other's GSM
    numbers and have a (logical) linear (or circular) order. Do not
    assume that your only suggestion succeeds. Instead, assume
    constraints from every participant.  Further, let us assume that any
    a single person may disappear (switch off the phone, etc.). The
    person can be unreachable already at the beginning, or disappear in
    any stage of the agreement. If other persons are able to agree, they
    do not need to care about the disappeared person. You may assume
    that the messages are delivered fast and all (non-disappeared)
    persons react in five minutes.

50) Estimate the time required to crack a 56-bit DES key by a
    brute-force attack using a 3000 MIPS (million instruction per
    second) workstation, assuming that the inner loop for a brute-force
    attack program involves around 50 instructions per key value, plus
    the time to encrypt an 8-byte plaintext. Encryption can be done at
    speed 5 MB/s.  Perform the same calculation for a 128-bit IDEA key.
    Extrapolate your calculations to obtain the time for a 10 TIPS (10^12
    ops/s) parallel computer (or an Internet consortium with similar
    processing power).  In a brute-force attack, we try all possible
    keys, and compare resulted ciphertext to the original. If the
    ciphertexts match, we have the key.