Concurrent BASH: Utilize your Dual-Core or Quad-Core processors

We can use batch command to send a series of tasks into a queue, and let it runs by itself. It monitors the load average and admit more tasks when it is low. However, the load average is not changing fast enough for many purposes. In addition, it lacks synchronization facility which is important when you want to make sure some concurrent operations complete before you proceed. Making it user-unfriendly, we have to write the script into a command stream for the batch command.

Hence, I'm trying to design a system to overcome problems as mentioned. Your BASH program can do like the following:

prun.bash:
#!/bin/bash
cd /tmp/xman
date
for i in *.ogg ; do

spawn oggdec *.ogg

done
synchronize
echo "Done"
date
exit 0

xman@sai xman $ time ./prun.bash
Sun Aug 27 21:44:13 SGT 2006
Done
Sun Aug 27 21:44:26 SGT 2006
real 0m13.279s
user 0m0.020s
sys 0m0.072s

Isnt that's cool? Multiple oggdec which decode ogg files will run in parallel on your dual-core or quad-core machine but with limited max number of threads at a time. The Dual-Core machine completes the decoding in merely 13.3s.

Now let me decode using serial script. The serial script:

xman@sai xman $ cat run
#!/bin/bash
date
for i in *.ogg ; do

oggdec "$i" &> /dev/null

done
echo "Done"
date
exit 0

xman@sai xman $ time ./run
Sun Aug 27 21:38:26 SGT 2006
Done
Sun Aug 27 21:38:46 SGT 2006
real 0m20.625s
user 0m19.273s
sys 0m1.004s

Serial script is unable to utilize two cores simultenously. Hence, it's important to use concurrent facility in order to fully utilize the processors that you are using.

Using BASH to manipulate all files in a directory - Cont

Chris pointed out I can simply do

for i in *; do echo $i ; done

I can recall I struggled on the problem file names broken into parts. I spent much time to solve it. There is nothing much to argue if all other programs except your current script were written correctly. If you forgot to " " your $i, see what will happen below.

xman@sai tmp $ ls -Q
"text1.txt" "text version 2.txt"
xman@sai tmp $ for i in * ; do mv $i $i.txt ; done
mv: target `2.txt.txt' is not a directory
xman@sai tmp $

Now we have two solutions.

Solution I:

for i in *; do mv "$i" "$i.txt" ; done

But do remember to double quote your file names. ;)

Solution II:

export IFS=$'\n'
for i in * ; do $i $i.txt ; done

There is nothing wrong if you use "$i".

Currently, I'm not sure what will break what will not if I set IFS=$'\n'. Certainly, if you are using some broken scripts that forgot to " ", with IFS=$'\n', you are still fine. Then, I'll rather locally use IFS=$'\n'. ;) If IFS=$'\n' does break other things, please tell me!

Running Reversi on Multiple Platforms

I have made little changes to let the xversi-c to play by itself. Get a copy of the benchmark version now xversi-c-benchmark-v0.1.tgz with binaries for Linux x86 or x86_64 included. It basically sets evaluation level to 6, so that it will run for a while. I first run it on my PC, surprisingly, the 64bit version is running much faster.

Host: AMD64 X2 4200+ (2.2GHz)
Compiler: GCC 4.1.1 64bit
Time 3m0.532s

Compiler: GCC 4.1.1 32bit
Time 5m7.210s

Before running this, I thought applications that do not use 64bit data types extensively probably would not benefit from running in 64bit mode. I have yet to investigate the exact causes of this performance difference. I do hope you can shed the light for me if you are experience in this. :)

See performance of the same program on other platforms, you probably will find another surprises.

Host: Itanium II 1.5GHz
Compiler: Intel(R) C Itanium(R) Compiler for Itanium(R)-based applications Version 9.0 Build 20050430 Package ID: l_cc_p_9.0.021
Time 6m35.306s

Host: Itanium II 1.4GHz
Compiler: Intel(R) C Itanium(R) Compiler for Itanium(R)-based applications Version 9.0 Build 20051201 Package ID: l_cc_c_9.0.030
Time 7m16.698s

Compiler: GCC 4.1.0
Time 6m8.471s

Host: Intel Core Duo 1.83GHz
Compiler: GCC
Time 5m5.423s

Host: Intel Pentium 4 HT 3GHz
Compiler: Intel(R) C Compiler for 32-bit applications, Version 9.0 Build 20051201Z Package ID: l_cc_c_9.0.030
Time 5m7.080s

Compiler: GCC 4.1.0
Time 4m37.404s

It's quite impressive to see that Intel Core Duo is on par with the Pentium 4 HT 3GHz, considering the clockspeed difference. And the GCC 4.1.0 is actually outperforms the Intel compiler v9 quite significantly. However, I didnt try out all the compiler switches in Intel compiler. On all the platforms, I merely use -O3. Regarding Itanium II, they are famous with their floating-point performance. In this case, that does not apply, as evaluations merely use Integer operations. In addition, Itanium II has lower clockspeed than other platforms. With higher clockspeed, it will probably work faster than other platforms.

Using BASH to print/manipulate all files in a directory

There are two files in my tmp directory.

xman@sai tmp $ ls
file1.txt file version 2.txt

You are probably familiar with simple for-loop in BASH script. But, see the following:

xman@sai tmp $ for i in `ls`
> do
> echo $i
> done
file1.txt
file
version
2.txt
xman@sai tmp $

Opssss, it doesnt print out each of the file names properly when there is space characters in the file names. The file names will be broken when there are spaces. Instead, you probably want to do the following:

xman@sai tmp $ export IFS=$'\n'
xman@sai tmp $ for i in `ls`
> do
> echo $i
> done
file1.txt
file version 2.txt
xman@sai tmp $

So now you can manipulate each of the files in a directory properly.

Installing & Configuring a Batch Scheduler: Torque + Maui

Installing Torque (PBS)

1. Download and extract the source from Cluster Resources
2. > ./configure --prefix=/usr/local/torque --set-cflags=-O2
3. > make
4. > make install
5. > make packages (will generate .sh files for distribution)
6. Create a system account TORQUEADMIN
7. Add /usr/local/torque/bin and /usr/local/torque/sbin to path.
8. Initialize PBS server files and create default queue.
1. > ./torque.setup TORQUEADMIN
   Note that "pbs_server -t create" is running in background.
   torque.setup is similar to following:
1. > pbs_server -t create
2. > qmgr -c "set server scheduling=true"
3. > qmgr -c "create queue batch queue_type=execution"
4. > qmgr -c "set queue batch started=true"
5. > qmgr -c "set queue batch enabled=true"
6. > qmgr -c "set queue batch resources_default.nodes=1"
7. > qmgr -c "set queue batch resources_default.walltime=3600"
8. > qmgr -c "set server default_queue=batch"
9. > qmgr -c "set server operators += TORQUEADMIN@SERVERNAME"
10. > qmgr -c "set server managers += TORQUEADMIN@SERVERNAME"
    
9. Check pbs_server running status.
1. > qstat -q
2. > qmgr -c 'p s'
3. Stop the pbs_server, runs "qterm -t quick"
   
10. Install pbs_mom into all compute nodes by running the generated script torque-package-mom-linux-ia64.sh in all compute nodes.
11. Add server node information to compute nodes.
1. Create /usr/spool/PBS/server_name with the server hostname.
• > cat /usr/spool/PBS/server_name
  shannon
  
2. Create /usr/spool/PBS/mom_priv/config
1. Create the file with the following lines.
   $pbsserver shannon1 # note: IP address of host running pbs_server
   $logevent 255
   $restricted shannon1 # note: IP address of host running pbs_server
   $usecp shannon1:/home /home
   
12. Add compute node information to server node
1. Create /usr/spool/PBS/server_priv/nodes
1. Create the file with the hostnames. e.g.
   shannon2 np=2
   shannon3 np=2
   shannon4 np=2
   shannon5 np=2
   
13. Start pbs_server on server node, and pbs_mom on all compute nodes.
1. > qterm -t quick
2. > pbs_server (in server node)
3. > pbs_mom (in all compute nodes)
   
14. Verify torque
1. > qstat -q
2. > pbsnodes -a
3. > echo "sleep 30" | qsub
4. > qstat
   

End of Torque installation.

Installing Maui

1. Download and extract the source from Cluster Resources
2. > CFLAGS=-O2 ./configure --with-pbs=/usr/local/torque --with-spooldir=/usr/spool/maui --prefix=/usr/local/maui-3.2.6p13
3. > make
4. > make install
5. Create a system user mauiadmin.
6. Edit /usr/spool/maui/maui.cfg
1. Set ADMIN1 mauiadmin
7. Add mauiadmin to PBS manager and operator list.
1. > qmgr -c "set server managers += mauiadmin@shannon"
1. > qmgr -c "set server operators += mauiadmin@shannon"
8. Change owner of /usr/spool/maui and /usr/local/maui/sbin to mauiadmin.
   

End of installing Maui.

Running Torque and Maui
1. pbs_server (on server node only, must be started using root).
2. pbs_mom (on compute nodes only, must be started using root).
3. maui (on server node only)

# Prepared at 16 March 2006

Does it do what you claim it does?

I was adding functionality to the Parallel Reversi. I came across this code:

numMove = list.GetNum() ;
for(i = 0 ; i <= numMove ; i++) { ... }

Oh oooooo ...... how could I make such a mistake? That will cause the accesses to the movelist array out of bound. But it's strange that I had been running the Parallel Reversi for many times without problems. Strange~~~~ I checked the move list implementation to confirm:

public int GetNum() {
return num ;
}

Mmmmm, seems like I made a mistake since long time ago. I then changed to

for(i = 0 ; i < numMove ; i++) { ... }

and declared I fix I bug that never give any complaints. Today I checked again and surprisingly find that the variable num range from 0 to Number_of_moves - 1. Oh nooooooo, I just fixed a correct implementation and introduced a bug. :S :'( ...... The variable names num, numMove quickly lead me to an understanding that they contain value number of moves. However, the move list implementation does not do what the variable names claim what they contain. It will be much better if I use GetMaxIndex() rather than GetNum(), or change num to index+1, any ways that make several components consistent. Phew ....... Now I declared the previous fix was a mistake, and now I fixed a mistaken fix.

Lesson learned:

• Verify your program does what your variable, function names, or even comments claimed what it does. Otherwise, the consequences could be frustrating, dangering, destructive, ......
• If I see such codes in a program, I'll definitely doubt the correctness of the entire program. I should have reviewed my codes for consistency. It's ashame to find this appears in my own programs.
• Next question, should I update all calls to GetNum()? If this function is called everywhere, I guess it's not a good idea to anyhow update a reusable component, as my mass updates could be error prone. I shall just add in some CONSISTENT comments in GetNum() to clarify.

Running slow using the Parallel version?

I recall that the Distributed Parallel Reversi, xversi-java-parallel-v0.8b, was able to achieve reasonable speedup when the level of evaluation is large enough. However, when I run it on my AMD Dual-Core machine, I realize the serial version, xversi-java-v0.7a, is much faster. :S (Jaw drops). I then went to check changes between the serial and parallel versions, what would cause this to happen? ...... after much struggling, I find that I'm using gcj package. Phew~~~~~ The serial version running on GCJ is reasonably fast, but the evaluation is extremely slow in the parallel version. I suppose, the RMI implementation in GCJ is causing delays. Finally, I simply install latest Java package from SUN, and it just runs fast. :) So, now I can increase the level of evaluation to improve the computer's reversi skill.
From my timing of the runs of computer vs computer, it took merely 30 seconds to 1 minute for the SUN Java to complete. However, it took more than 10 minutes for the GCJ Java to run. I dont know how long it will take, I just give up running. :p

Distributed Parallel Reversi in Java: You have Dual-Core? Quad-Core Processors?

Let's catch up with the technology trends on multi-core processors. If you have bought a dual-core, or quad-core, or a large shared memory parallel machine, or a cluster of computers, then you can run this Distributed Parallel Reversi, xversi-java-parallel-v0.8b.tgz, to make them busy.
Running Distributed Parallel Reversi: Step-by-step

1. Launch a server in each of your machines that will provide reversi evaluation services.
   
• xman@sai xversi-java-parallel-v0.8b # java -Djava.security.policy=xversi.policy XversiEval localhost 9394
  Registered XversiInterface
• localhost: Machine name, or its IP.
• 9394: Port number for the client to connect to. Remember to set your firewall to allow this port.
  
2. Setup a machine info file called nodeinfo.txt.
   
• xman@sai parallel # cat nodeinfo.txt
  2
  localhost:9394
  localhost:9394
• 2: There are 2 entries about machine information.
  
• localhost: Machine name or its IP. I include two identical lines because I'm running this on a dual-processor or dual-core processor machine. This will make the parallel reversi to utilize the two processors in the system.
  
3. Launch the Java Applet.
• xman@sai parallel # appletviewer -J-Djava.security.policy=xversi.policy test.html
  Number of Node : 2
  before lookup
  Node 0 localhost:9394
  name 0 //localhost:9394/xversiInterface
  Node 1 localhost:9394
  name 0 //localhost:9394/xversiInterface
  after lookup
• I've forgotten how do you specify the policy to a browser to launch the Java applet. TELL ME IF YOU KNOW! ;)

Notice that in picture below, two processors in the system are running at full speed to evaluate different moves at the same time. :) Hence, if you bought a dual-core, quad-core, ... or even a cluster of computers, enjoy the benefit of parallel computing. :) Ideally it will run N times faster with N processors.

Click to see larger picture

Latest Reversi in Java: After much "backup recovery"

The latest Reversi in Java had been kept safely in my backups for quite some time. I recall that I did backup it into CDs, together with many versions of reversi I developed. After backup into CDs, all the files become capital letters, hence, I have to change all the files into correct case before I can launch the Java applet (Stupid backup). That took me quite some time, together with cleaning up many different versions. It was a mistake I didnt use any version control software such as CVS, SVN, ... during development. From now onwards, all changes shall check-in into my svn repository.
Here is the latest Reversi in Java, xversi-java-v0.7a.tgz under GPL, which added some little features on top of xversi-java-v0.6b:

1. Show a green dot of computer's last move.
2. Compute end game when the game is near end.
3. Draws the piece with better aspect ratio as we resize the board.

Lessons learned:

• Always document your changes to your documents, codes, ... Use tools such as CVS, SVN, ... to help tracking the changes.
• I shall prepare a changelog file in the future releases.
• Backup each version of your programs into a package such as .tgz, or .zip, such that when you recover from your backup, program files attributes, from filenames to their permissions, are recovered to the original. Versioning helps you to clean up the mess.
• Portable is good. :) After few years, these reversi programs are still running properly without much issues. :)
  

Reversi in Java: The first presentable board game

I believe you'll not want to use command interface to play board game Reversi. Try this out, Reversi in Java xversi-java under GPL. The package includes both source codes and .class files. To play, simply extract files in the package and open the test.html using appletviewer or a browser with Java support. The implementation is lightweight, all the drawings are generated real-time, without using any picture files.
This had been further extended to use RMI (remote method invocation) to support parallel evaluation. However, it's troublesome to run and requires some security setting of the Java applet to be able to access host file. If you think it's interesting, stay tuned. :)

REVERSI: Yet another program that I had put in storeroom for a long time

I started with writing a Reversi board game in Java. Then I ported it to C++, called xversi-c which is under GPL and hope that it will run much faster. The implementation ideas are simple:

• Generate all possible moves.
• For each of the moves generated above, evaluate and keep the best move.
  
• The real question is, how do we evaluate each of the possible moves?
• Just use your imagination, to determine whether a move is good, just find out what are all the next possible moves? what are all the next next possible moves? ...... eventually, the board will be filled up with all the possible moves :)
• Practically, we cannot imagine too many moves. At one point, we will want to use some criteria to determine whether a move is good. I have use some simple heuristics to calculate a score for each move.
• Count number of pieces. When game started, we dont want to have many pieces. But as game closer to end game, we want more pieces.
  
• Count mobility, that's the number of moves that each player has. Having more moves, probably means having more controlling power over opponent.
• Count the number of corners obtained.
  
• As the game closer to the end, number of possible moves are limited. Thus, when game is near end, I set it to compute all the possible moves till the end. At the end, evaluation is simple, simply count the number of pieces each player has.
• For more information about evaluation, search for Game tree generation with alpha-beta prunning.
  

Phew..... no point having too many explainations. :) Read the codes if you care. :) I hope it's readable enough. :p

My first open source programs

Have been writing many toy programs which end up in the recycle bin, and then flush to no place. I hope from now onwards, my programs can have longer livespan. Let me start with some bash scripts, xman utility under GPL:

• xman_rm: Move given files into the folder ".deleted". So that I can recover the files in the future if we need to.
• xman_list_rb: List files deleted using xman_rm.
• xman_clean_rb: Delete all files found by xman_list_rb permanently.
• xman_create_pdfdb: Process given folder recursively for .pdf files. Convert all .pdf files into .txt and store in database folder.
• xman_lowercase: Convert all given file names to lowercase.
• xman_uppercase: Convert all given file names to uppercase.
• xman_chext: Convert file extension to another extension.
• xman_tolower_filter: Convert strings from stdin to lowercase.
• xman_toupper_filter: Convert strings from stdin to uppercase.

Hope these scripts may help you for your work. If not, you may still learn some bash scripts from these. :) You may also suggest useful scripts for routine work.