Sphere Online Judge (SPOJ) progress

SPOJ is one of the main sites that host programming challenges. The problems in SPOJ are for the most part much easier than the ones in Project Euler (which I have also posted about, although I have neglected it for several months...), so they are quite nice to try to solve in new programming languages. At this moment there are >10K users who have submitted at least one correct solution to one of the programs, so the place is very active. The graph below will show my progress in SPOJ, although I don't really intend to compete. I will only look for problems that look interesting to develop my programming skills.

Debugging Fortran+MPI codes with "The Portland Group" debugger (pgdbg)

I have to admit that I didn't get the Fox algorithm in my previous post correct the very first time, so I had to do some parallel debugging. In the past, I have used gdb, and the Intel Debugger, and now it was time to try pgdbg (The Portland Group debugger). Next in line is TotalView.

At our institution the Portland compiler's version installed is 10.5, but this had some issues with my current workstation linux distribution (Ubuntu 10.04 64 bits), so I installed the current latest version: 10.6. Installation was very simple with their install script, and once the license file was in place it was time to try it.

Compilation of the code can be done with the included MPICH1, with the following command:


angelv@vaso:~/fox$ pgf90 -o fox -Mmpi=mpich1 -g fox.f90


Since we will be using ssh to connect to the other processors (actually just a number of processes all running in my local workstation), we need to first get the ssh security sorted out (tips from the "PGI Tools Guide" documentation, page. 90). We generate the ssh keys with a passphrase (and copy them to the authorized keys):


$ ssh-keygen -t dsa

$ cd $HOME/.ssh
$ cp id_dsa.pub authorized_keys


And then, from a new terminal we will just have to do the following, and enter the passphrase just once, and all subsequent ssh connections will be passwordless:


$ eval `ssh-agent -s`
$ ssh-add


With this in place, we can run our code with the included MPICH1 version:


angelv@vaso:~/fox$ mpirun -stdin fox.in -np 4 ./fox


In order to run it with the debugger, we just add the option -dbg=pgdbg:


angelv@vaso:~/fox$ mpirun -stdin fox.in -dbg=pgdbg -np 4 ./fox



The following image shows a moment during the debugging session, where 4 processes have been created, and we are at the end of the first stage in the Fox algorithm. The window in the bottom shows how you can easily see the values of variables (whole matrixes included, which can be indexed according to Fortran syntax) for all (or a selection of) processes involved in the computation.

I need to try it for a longer period, but overall it looks like a very usable parallel debugger. The Portland Group has a video demo of the debugger here.

Fox algorithm for matrix multiplication in parallel with Fortran90+MPI

I'm now re-reading the book "Parallel Programming with MPI" by Peter S. Pacheco and doing some of the exercises in there. An interesting one is the Programming Assignment n.1 in page. 133, which involves fully implementing the Fox parallel algorithm for multiplying matrixes (see for example).

Below is Fortran90 code (version 1... some things need to be improved...) that does it (a better looking source code is at Pastebin, although I'm not sure for how long it will stay there...)


PROGRAM FOX
  IMPLICIT NONE
  include "mpif.h"

  INTEGER :: procs, rank, error
  INTEGER, DIMENSION(MPI_STATUS_SIZE) :: status

  INTEGER :: g_order, g_side, my_g_row, my_g_column, my_g_rank, comm, row_comm, col_comm, block_mpi_t
  INTEGER :: rows
  REAL, DIMENSION(:,:), ALLOCATABLE :: matrixA, matrixB, matrixC, localA, tempA, localB, localC
 
  CALL MPI_Init ( error )
  CALL MPI_Comm_size ( MPI_COMM_WORLD, procs, error )
  CALL MPI_Comm_rank ( MPI_COMM_WORLD, rank, error )
 
  CALL Read_Matrix(rank,error,rows,matrixA,matrixB,matrixC)
  CALL Setup_grid(g_order,g_side,error,comm,my_g_rank,my_g_row,my_g_column,row_comm,col_comm)
  CALL Distribute_matrixes(g_side,rows,block_mpi_t,error,matrixA,matrixB,localA,localB,localC,my_g_row,my_g_column)
  CALL Perform_Fox_Algorithm(my_g_row,my_g_column,g_order,localA,tempA,localB,localC,row_comm,col_comm,status,error)
  CALL Print_Last_Result(rank, my_g_rank, g_side, comm, procs, error, status, localC, matrixC, tempA)

  
  CALL MPI_Finalize (error)

CONTAINS
 
  SUBROUTINE Print_Last_Result(rank, my_g_rank, g_side, comm, procs, error, status, localC, matrixC, tempA)
    INTEGER, INTENT(IN) :: rank, my_g_rank, g_side, comm, procs
    INTEGER, INTENT(OUT) :: error
    INTEGER, DIMENSION(:), INTENT(OUT) :: status
    REAL, DIMENSION(:,:), INTENT(IN) :: localC
    REAL, DIMENSION(:,:), INTENT(OUT) :: matrixC, tempA

    INTEGER :: grow,gcol,i
    INTEGER,DIMENSION(2) :: coordinates

    IF (rank .EQ. 0 .AND. my_g_rank .NE. 0) PRINT*, "Houston, we have a problem with I/O"

    CALL MPI_SEND(localC,g_side*g_side,MPI_REAL,0,0,comm,error)

    IF (rank .EQ. 0) THEN
       matrixC=0
       DO i=1,procs
          CALL MPI_Recv(tempA,g_side*g_side,MPI_REAL,MPI_ANY_SOURCE,0,comm,status,error)
          CALL MPI_Cart_coords(comm,status(MPI_Source),2,coordinates,error)
          grow = coordinates(1)
          gcol = coordinates(2)
          matrixC(grow*g_side+1:(grow+1)*g_side,gcol*g_side+1:(gcol+1)*g_side) = tempA
       END DO
    PRINT*,"============ Matrix multiplication in parallel ==================="
    CALL Print_Matrix(matrixC)
    END IF
  END SUBROUTINE Print_Last_Result


  SUBROUTINE Print_Matrix(M)
    REAL, DIMENSION(:,:) :: M
    INTEGER :: side,row,column

    side = SIZE(M,1)

    DO row=1,side
       DO column=1,side-1
          WRITE(*,'(F10.3)',ADVANCE='NO'), M(row,column)
       END DO
       WRITE(*,'(F10.3)'), M(row,side)
    END DO
  END SUBROUTINE Print_Matrix


  SUBROUTINE Perform_Fox_Algorithm(my_g_row,my_g_column,g_order,localA,tempA,localB,localC,row_comm,col_comm,status,error)
    INTEGER, INTENT(IN) :: my_g_row,my_g_column,g_order,row_comm,col_comm
    INTEGER, INTENT(OUT) :: error
    INTEGER, DIMENSION(:), INTENT(OUT) :: status
    REAL, DIMENSION(:,:), INTENT(IN) :: localA
    REAL, DIMENSION(:,:), INTENT(INOUT) :: tempA,localB,localC

    INTEGER :: source,destination,stage,bcast_root

    localC = 0
    source = MOD(my_g_row + 1,g_order)
    destination = MOD(my_g_row + g_order - 1,g_order)

    DO stage=0,g_order-1
       bcast_root = MOD(my_g_row + stage,g_order)

       IF (my_g_column .EQ. bcast_root) THEN
          CALL MPI_BCAST(localA,g_side*g_side,MPI_REAL,bcast_root,row_comm,error)
          CALL Matrix_Multiply(localA,localB,localC)
       ELSE
          CALL MPI_BCAST(tempA,g_side*g_side,MPI_REAL,bcast_root,row_comm,error)
          CALL Matrix_Multiply(tempA,localB,localC)
       END IF
       CALL MPI_Sendrecv_replace(localB,g_side*g_side,MPI_REAL,destination,0,source,0,col_comm,status,error)
    END DO
  END SUBROUTINE Perform_Fox_Algorithm


  SUBROUTINE Matrix_Multiply(A,B,C)
    REAL, DIMENSION(:,:), INTENT(IN) :: A,B
    REAL, DIMENSION(:,:), INTENT(OUT) :: C
    INTEGER :: side,row,column

    side = SIZE(A,1)

    DO row=1,side
       DO column=1,side
          C(row,column) = C(row,column) + SUM(A(row,:)*B(:,column))
       END DO
    END DO
  END SUBROUTINE Matrix_Multiply


  SUBROUTINE Distribute_matrixes(g_side,rows,block_mpi_t,error,matrixA,matrixB,localA,localB,localC,my_g_row,my_g_column)
    INTEGER, INTENT(IN) :: g_side,rows,my_g_row,my_g_column
    INTEGER, INTENT(OUT) :: block_mpi_t,error
    REAL, DIMENSION(:,:), ALLOCATABLE, INTENT(OUT) :: localA,localB,localC
    REAL, DIMENSION(:,:), INTENT(INOUT) :: matrixA,matrixB

    CALL MPI_TYPE_VECTOR(g_side,g_side,rows,MPI_REAL,block_mpi_t,error)
    CALL MPI_TYPE_COMMIT(block_mpi_t, error)
    
    CALL MPI_BCAST(matrixA,rows*rows,MPI_REAL,0,MPI_COMM_WORLD,error)
    CALL MPI_BCAST(matrixB,rows*rows,MPI_REAL,0,MPI_COMM_WORLD,error)

    ALLOCATE(localA(g_side,g_side),tempA(g_side,g_side),localB(g_side,g_side),localC(g_side,g_side))
    localA = matrixA(my_g_row*g_side+1:(my_g_row+1)*g_side,my_g_column*g_side+1:(my_g_column+1)*g_side)
    localB = matrixB(my_g_row*g_side+1:(my_g_row+1)*g_side,my_g_column*g_side+1:(my_g_column+1)*g_side)
  END SUBROUTINE Distribute_matrixes


  SUBROUTINE Setup_grid(g_order,g_side,error,comm,my_g_rank,my_g_row,my_g_column,row_comm,col_comm)
    INTEGER, INTENT(OUT) :: g_order, g_side,error,comm,my_g_rank,my_g_row,my_g_column,row_comm,col_comm

    INTEGER,DIMENSION(2) :: dimensions,coordinates
    LOGICAL,DIMENSION(2) :: wrap_around,free_coords

    g_order = SQRT(REAL(procs))
    g_side = rows / g_order

    dimensions = g_order
    wrap_around = .TRUE.
    CALL MPI_Cart_create(MPI_COMM_WORLD,2,dimensions,wrap_around,.TRUE.,comm,error)
    CALL MPI_Comm_rank ( comm, my_g_rank, error )
    CALL MPI_Cart_coords(comm,my_g_rank,2,coordinates,error)
    my_g_row = coordinates(1)
    my_g_column = coordinates(2)

    free_coords(1) = .FALSE.
    free_coords(2) = .TRUE.
    CALL MPI_Cart_sub(comm,free_coords,row_comm,error)

    free_coords(1) = .TRUE.
    free_coords(2) = .FALSE.
    CALL MPI_Cart_sub(comm,free_coords,col_comm,error)
  END SUBROUTINE Setup_grid

  SUBROUTINE Read_Matrix(rank,error,rows,matrixA,matrixB,matrixC)
    INTEGER, INTENT(IN) :: rank
    INTEGER, INTENT(OUT) :: rows,error
    INTEGER :: i
    REAL, DIMENSION(:,:), ALLOCATABLE, INTENT(OUT) :: matrixA,matrixB,matrixC

    IF (rank .EQ. 0) THEN
       READ*, rows
       CALL MPI_BCAST(rows,1,MPI_REAL,0,MPI_COMM_WORLD,error)
       ALLOCATE(matrixA(rows,rows),matrixB(rows,rows),matrixC(rows,rows))
       DO i=1,rows
          READ*, matrixA(i,:)
       END DO
       DO i=1,rows
          READ*, matrixB(i,:)
       END DO

       !! Calculate the matrix multiplication for comparison                                                                                                                          
       matrixC = 0
       CALL Matrix_Multiply(matrixA,matrixB,matrixC)

       PRINT*, "CALCULATED IN PROCESS 0"
       PRINT*, "=======MATRIX A=========="
       CALL Print_Matrix(matrixA)
       PRINT*, "=======MATRIX B=========="
       CALL Print_Matrix(matrixB)
       PRINT*, "=======MATRIX C=========="
       CALL Print_Matrix(matrixC)
    ELSE
       CALL MPI_BCAST(rows,1,MPI_REAL,0,MPI_COMM_WORLD,error)
       ALLOCATE(matrixA(rows,rows),matrixB(rows,rows))
    END IF
  END SUBROUTINE Read_Matrix

END PROGRAM FOX


And given the following matrixes:


angelv@vaso:~/fox$ cat fox.in
8
3.4 4.2 2.1 9.3 5.6 7.8 3.4 6.3
6.6 7.6 2.1 7.2 3.5 7.9 2.0 8.3
8.6 4.1 7.5 3.5 7.1 9.6 4.1 8.1
5.8 4.7 8.6 3.6 7.4 4.3 1.2 0.2
9.9 5.3 8.9 3.7 6.5 9.7 3.6 5.3
8.2 4.7 9.3 3.8 6.7 8.4 4.7 6.4
6.8 8.0 2.8 8.9 9.8 3.2 6.8 8.7
6.4 7.6 8.3 4.3 6.5 4.1 3.9 3.8

3.5 5.7 8.6 4.6 7.5 9.0 2.8 6.0
8.9 3.4 7.3 3.3 5.3 8.2 3.6 3.9
8.3 0.8 2.1 1.6 4.7 6.4 3.4 8.8
7.3 4.3 3.3 2.7 4.5 6.6 9.3 5.9
6.7 6.7 8.0 2.8 3.7 5.7 7.7 8.3
7.8 4.0 8.9 2.9 1.4 0.8 7.8 8.2
3.4 7.1 5.7 9.0 6.1 7.9 8.9 7.7
2.6 4.1 6.9 8.2 9.3 5.0 7.1 4.6




We can compile it and run it as:

angelv@vaso:~/fox$ pgf90 -Mmpi=mpich -o fox fox.f90

angelv@vaso:~/fox$ mpirun -stdin fox.in -np 4 ./fox
 CALCULATED IN PROCESS 0
 =======MATRIX A==========
     3.400     4.200     2.100     9.300     5.600     7.800     3.400     6.300
     6.600     7.600     2.100     7.200     3.500     7.900     2.000     8.300
     8.600     4.100     7.500     3.500     7.100     9.600     4.100     8.100
     5.800     4.700     8.600     3.600     7.400     4.300     1.200     0.200
     9.900     5.300     8.900     3.700     6.500     9.700     3.600     5.300
     8.200     4.700     9.300     3.800     6.700     8.400     4.700     6.400
     6.800     8.000     2.800     8.900     9.800     3.200     6.800     8.700
     6.400     7.600     8.300     4.300     6.500     4.100     3.900     3.800
 =======MATRIX B==========
     3.500     5.700     8.600     4.600     7.500     9.000     2.800     6.000
     8.900     3.400     7.300     3.300     5.300     8.200     3.600     3.900
     8.300     0.800     2.100     1.600     4.700     6.400     3.400     8.800
     7.300     4.300     3.300     2.700     4.500     6.600     9.300     5.900
     6.700     6.700     8.000     2.800     3.700     5.700     7.700     8.300
     7.800     4.000     8.900     2.900     1.400     0.800     7.800     8.200
     3.400     7.100     5.700     9.000     6.100     7.900     8.900     7.700
     2.600     4.100     6.900     8.200     9.300     5.000     7.100     4.600
 =======MATRIX C==========
   260.900   194.020   272.070   178.530   210.450   236.380   297.220   275.730
   274.180   199.380   307.390   197.010   245.450   266.250   285.240   277.610
   311.840   232.300   352.690   225.580   277.280   303.160   320.440   360.720
   247.510   147.520   219.820   111.300   167.610   225.640   198.500   256.890
   327.930   227.120   350.150   209.450   269.700   313.690   306.850   365.810
   318.490   224.600   336.210   216.270   271.960   310.980   311.220   361.910
   319.570   268.880   357.800   255.450   309.740   359.100   362.840   349.110
   288.990   190.670   279.080   175.760   235.560   291.560   257.210   301.530
 ============ Matrix multiplication in parallel ===================
   260.900   194.020   272.070   178.530   210.450   236.380   297.220   275.730
   274.180   199.380   307.390   197.010   245.450   266.250   285.240   277.610
   311.840   232.300   352.690   225.580   277.280   303.160   320.440   360.720
   247.510   147.520   219.820   111.300   167.610   225.640   198.500   256.890
   327.930   227.120   350.150   209.450   269.700   313.690   306.850   365.810
   318.490   224.600   336.210   216.270   271.960   310.980   311.220   361.910
   319.570   268.880   357.800   255.450   309.740   359.100   362.840   349.110
   288.990   190.670   279.080   175.760   235.560   291.560   257.210   301.530
angelv@vaso:~/fox$ 

Classical Guitar Forum

About a month ago I joined the Delcamp Classical Guitar Forum, and so far I've found it amazing. This one is the Forum in English, though there are also sites in French, Italian and Spanish.

There are a lot of people participating (composers, guitar players, luthiers), the conversations are very well kept to the subject (with well organized topics), and the people are really helpful and friendly.

And the resources are also very good. In it you can find information about technique, many recordings of common repertoire pieces, plenty of music scores, etc.

All in all, this is by far the best place in the Internet for sharing guitar experiences with other musicians. If you happen to stumble here and have any interest in Classical Guitar, make sure you visit the Delcamp Forum.

Thanks Jean-François Delcamp for starting this out!

Opera Mail vs. Thunderbird 3.1 vs. GMail

During the last seven months I've been using the Opera Web browser and its integrated Mail Reader, but the experience started to become a bit painful, so I am going back to Firefox/Thunderbird.

Some of the things that pushed me to do this were:

• With the Opera browser I was not aware of anything like FoxyProxy, which is very useful for me when accessing my company intranet.
• My web bank page did not show properly (perhaps their fault?) with Opera.
• Had issues with logging in my favourite forum with Opera (oddly enough not in all computers).
• The full editor of blogger does not display properly in Opera.
• I didn't notice Opera browser being particularly faster than Firefox.
• Opera Mail did not let me put my own tags to messages, which was a bit annoying sometimes.
• Opera Mail did not let me configure my mail servers with not standard ports, which was annoying if I wanted to access my company servers through SSH tunnels.
• In a few occasions Opera Mail just stopped working, and after restarting all the messages would be gone (the local copy only), so it had to download them again from Google Mail.
• Lately Opera Mail started to think that I had millions of messages and would never finish synchronizing with Gmail. After restarting it, it would recognize again properly that I have only thousands.

So, I decided to try the new Thunderbird 3.1 for e-mail, and if it was up to the job, then go back to the Firefox/Thunderbird tandem. So, I collected the things that I need from a mail reader and did a comparison of Thunderbird, Opera Mail, and Gmail. I'm not interested in doing a comparison of all their features, only the ones that I tend to use. I haven't looked in any depth at the documentation of any of the readers, so some of the things here might be wrong. If you find that any of this information is incorrect or that there are better ways of doing something, please let me know, I'd love to hear it. Thunderbird did now manage to do everything I needed, and I don't get the problems mentioned above (plus it is open source software), so I'm now migrating to Firefox/Thunderbird... for how long?

Here it is a list of things that I want my mail reader to do:

• No folders, use tags instead

Folders are a nuisance, much better tags. You can apply several tags to the same message, and when searching for a particular tag is like you put a message in different folders at the same time.

- GMail: tags are called labels, and you can easily create arbitrary new labels and assign as many as you want to each message.

- Thunderbird: you can also create Tags and assign as many as you want to each message.

- Opera Mail: as far as I know, only the prebuilt tags.

• Don't mark messages as read automatically

- GMail apparently marks a message as read as soon as you open it. I don't like this at all. I don't even want to mark a message as read after a given set of time. For me "unread" means that I still have to do something with it, so I want to mark it as "read" only when I decide.

- Thunderbird. No problem. In Preferences, Advanced, unmark "Automatically mark messages as read", and I have to mark them as read explicitly.

- Opera Mail. This was also easily configurable.

• Efficient searching and filtering of messages

This is probably the most important feature for me, and for basic searches I think the three readers are very good. For "incremental searches" I think Gmail is the winner, but Thunderbird 3.1 second.

By incremental search I mean a situation like this: I want to find all mails that have something to do with "braemore statements", and once I found these, I want to find which ones have the word "winter" in the body.

- GMail. This is very good for incremental searches. Type "braemore statements" and a list of mail appears, then type "winter" and press again and bingo.

- Thunderbird. If I type all the words of an incremental search in the "Search all messages" box (thus not making it really incremental), then I also get the result, but ideally one would only type "braemore statements", then click on "Open as list" and then do a "Filter these messages", including the Body, but this does not work well and it seems to hang forever. (Filtering by body does seem to work at least in the Inbox, but it looks like it is really slow, while the Ctrl+K search is really fast. Go figure....).

- Opera Mail. The search option was very fast and quite good in general. For incremental searches it is very good. Type "braemore statements" in the general search box, then one the mails have been found, type "winter" in the quick filter, and bingo! This is what I was hoping it would work in Thunderbird as well, but for some reason it is not just yet.

• Good keyboard shortcuts

-  Gmail apparently does have shortcuts, but I doubt that they are comparable to Thunderbird or Opera in this respect.

• Make "read" messages disappear from view but keep them available

- GMail: I'm sure there has to be a way to do this, but it was not obvious.

- Thunderbird. In my Inbox I just click on the "Unread" quick filter and bingo. I only see the "unread" ones but all the rest are somewhere in there. Much cleaner view.

- Opera Mail also does this without any issues.

• Good display of HTML messages

- Obviously no trouble with this in Gmail, and Thunderbird does it very well also. With Opera Mail I had trouble with quite a few HTML formatted messages. I don't like HTML messages, but people insist on sending them, so I guess I have to be able to read them.

• Possibility of deleting attachments

- I could not find how to do this in either Gmail or OperaMail. With Thunderbird is just one of the options of the attachment itself.

• Different personalities 

 This is useful for sending personal mails, or mails to newsgroups, etc. with different mail addresses and/or signature.

- Gmail: I don't think this is possible at all.

- Thunderbird:  it has support for different personalities, and I have used it in the past. Very convenient. This, together with the possibility of using non-conventional ports was very useful for me. Different personalities with Google Mail as SMTP server does not seem to work (Gmail at the end sends the message with you gmail address, and that's all), but when using non-standard port for my SMTP server, I can send (regardless of where I am) mail through my company SMTP server (via ssh tunnels). This allows me to fake my e-mail address (to avoid spam) when sending messages to newsgroups, and to send mail to internal mailing lists at our company (which rejects mails if coming from an outside address).

- OperaMail. I think this is only possible if you have different mail accounts, so you can select which one to use every time you send a message, but I don't think it is possible having, for instance, different signatures associated with the same mail account.

• Automatic filtering of messages

OperaMail has something that is very useful: The automatic views of mails sent to newsgroups. With Thunderbird is not so automatic, but it does require little work: one can create Search Folders (Ctrl+Shift+F), where one can create complicated searches, and then save it as a search folder. For instance, I created a search folder called "Direct", where I only see mail that is directed personally to me, another search folder where I only see mail that has a particular mailing list address in the "To or CC" fields, etc. This is similar to the old folder mentality, but the messages don't go into any folder, they all can stay in the same folder, and this is just different filtered views of it. Much more powerful and convenient.