Homework 1: MPI and MATLAB*P

Outline

• Create a directory called 'your user name'-hw1
  For example, cly-hw1
• Create four subdirectories, prob1, prob2, prob3, prob4
• Put your files (source code, txts) in the appropriate directory
• tar your directory by: tar cf 'your user name'-hw1.tar 'your user name'-hw1
  For example, tar cf cly-hw1.tar cly-hw1
• gzip it:
  gzip cly-hw1.tar
• Put this file in the root of your home directory,
  cp cly-hw1.tar.gz ~
• The file will be collected at 2/13 11:59pm EST. This corresponds to 2/14 4:59am GMT, which the server uses.

Let S be a random string of the alphabet Q = { A, C, G, T } with length mn. S is distributed among m processors such that processor i has a substring S_i of length n. S equals concat(S_0, S_1, ..., S_(m-1)).

Let I be an input string of the alphabet Q.

Write a program which, when run on m processors (-np m) does the following:

• Ask user for input n.
• Generate S of length mn by having each process generate the local random substring S_i.
• Ask user for input I.
• Locate all occurrence of I in the string S. Then collect and print the following statistics:
  
  • The minimum 'gap' (in characters) between two occurrences
  • The average 'gap' between two occurrences
  • The maximum 'gap' between two occurrences
• Loop back and ask user for input I. Repeat.

• Source code
• Executable, or Makefile that builds the executable

• You need to consider those substrings that 'straddle' between S_i and S_(i+1)
• MPI_Reduce would be useful at some point
• Q: In reasonably large data sets, the chance of having 0 instances of a letter on any 1 node would be extremely small, so is it required that the code be able to handle the 0 instance condition?
  A: Well, the chance of having 0 instances also depends on the length of the pattern to be matched. But anyway, your code should handle the 0 instances case gracefully.

• Q: Along the same lines, is the statistics calculation step required to be parallelized or can I bump the string up to the master node to calculate the statistics? I just want this clarified before I do more work than I need to.
  A: The statistics calculation has to be parallelized.

• Q: For the first problems of homework1, it says the string Icould straddle across S_{i} and S_{i+1}, is it possible that the string can also across more than 2 processes? Say e.g. I spans from S(2) to S(5)
  A :Ignore cases of I spanning more than 2 processes, i.e. assumen I is at most of length n+1

• IMPORTANT Q: On a different note, how do you define the distance between two strings in the first problem? Is it the distance between the first character in each string? or the distance between the last character of one string and the first of the next one? (Which might lead to complications if two strings overlap)
  A: Good question. As a proper course 6 student I'll define it as the distance between the first character in each string.

• Q:

  By gap's between occurences, do you mean between two adjacent occurences or
  each occurence and each other occurence?
  
  I.e. in the following example:
  
  string:
  aTCTCTagTCT
  substring:
  TCT
  
  Are the gaps 2(between first and second), 5 (between second and third)
  OR
  2 (between 1 and 2), 7 (between 1 and 3), and 5 (between 2 and 3).
  

  A: Between 2 adjacent occurences. So 2,5.

• This guide to mm mode would be very helpful.
• x should be a row-distributed col vector.
• DON'T even try creating A in its entirety. NOT even as a test or anything. (2^16)^2 * 8 = 2^35 = 32GB. The cluster will run out of memory and very likely hang. As a rule of thumb, before creating a large matrix, do some "back of the envelope" calculation to see if it makes sense (we have 1GB on each node, shared by two processors. So treat it as 512MB per processor).
• Note that by the way 'mm mode' works, each process will only have a local piece of the vector x. Think about how this will affect your computation of y = Ax, and add in any necessary step.
• Q: Specifically, in problem 3, it seems that to do the y=Ax step in mm mode requires some way of letting each processor know which part of the matrix it has (since we don't actually want to pass parts of matrix A to each processor). How do we do this?
  A: x is distributed row-wise (according to clarification). So if you think about how matrix-vector mult works, you'll see that the part of A that is used on each processor depends only on np, the number of processor. You are right that you don't want to pass A around. Even more than that, you don't even want to construct any part of A at all anywhere.

• Google - search for clusters with HPL results. Compare.
• Log into a cluster on which you have account. Run HPL for 1 nodes, 2 nodes ... interpolate.

• Your text/ps/pdf file