Progress report for week 43

This week I haven’t made any significant progress on DECS. I’ve mostly been catching up on work in the other courses and finished a few projects here and there. The draft report has been my main focus on DECS, and will continue to be so until I finish it. My goal is to finish it sometime during this week.

NOTE: This post has been imported from my old it’s learning ePortfolio DECS blog.

Progress report for week 42

I’ve been working on the new modular approach and I’m in the process of fitting the pieces together. After that is done I’m going to be working more with BOINC to complete the parallelization stuff. I’ll also try to get one of those draft report out soon.

In the course “Developing Distributed Services” I modeled and simulated DECS with GPenSIM (a MATLAB Petri net tool), and the report can be found here. I’m thinking if maybe some of that might be interesting to include in the DECS report as well.

I looked into doing some cross compiling with gcc so that all the binaries could be compiled on the same machine. What you have to do is to build binutils, gcc and glibc for each target platform. It’s a bit of a stretch so currently I’m sticking with the slightly more cumbersome, but fully working method of just compiling the program on the platforms I need and manually copying the binaries to the BOINC server.

NOTE: This post has been imported from my old it’s learning ePortfolio DECS blog.

Petri net modeling and simulation of a distributed computing system

This report (LaTeX source) was written as an assignment for a course in development of distributed services. It talks about the modeling and simulation of a distributed computing system based on BOINC. This system is called Generic Distributed Exact Cover Solver (DECS) which is a separate project I’ve been working on. For the simulation it uses GPenSIM, which is a package for MATLAB to model and simulate Petri nets. The GPenSIM files used in this project are also available for download.

NOTE: This post has been imported from my old it’s learning ePortfolio project blog.

Progress report for week 41

This week I have been working on a way to implement my Dancing Links parallelization idea. I found out that my DLX library implementation was too monolithic so I had to devise a plan to split it up into smaller pieces. Currently it has been divided into the following parts:

  • dlx – The Dancing Links algorithm library is where the exact cover problem is actually solved. It depends on the sbmatrix library to provide the matrix data structure.
  • sbmatrix – The Sparse Boolean Matrix library takes care of the exact cover matrix data structure. It is entirely self contained and can easily be used independently of the DECS project.
  • fileio – File Input/Output library which deals with the DECS file format. It can read/write matrices from/to file by using the data structure provided by sbmatrix . It should also be the only place where byte ordering problems are “take care of”.

Work is currently in under way to complete the migration to the new modular approach. The benefits will be much looser coupling between the components which will allow better extensibility, better integration of existing components and less code duplication.

I finally undestood how Donald Knuth’s own Dancing Links implementation in C (CWEB) works. The GOTO statements did a good job in obscuring the actual flow of control. Using plain loops, like the pseudo code in his paper, would have made a big difference in readability. The implementation didn’t provide any additional insight so it was probably a waste of time to study it, except as an exercise to better learn C.

The DLX library has been improved by adding some cleanup functions which should eliminate most of the previous memory leaks. The it’s learning ePortfolio host also looks like it has stabilized. yey…

NOTE: This post has been imported from my old it’s learning ePortfolio DECS blog.

Progress report for week 40

Dell is dragging their feet so my laptop is still not operational. I’ve added configuration files for CMake, which is a cross-platform, open source make system. CMake successfully compiles all the DECS executables and libraries in Windows under MinGW by using CMake’s “MinGW Makefiles” generator. It also works without a hitch under Linux with the “Unix Makefiles” generator. I ran into some trouble trying to build DECS with the “Visual Studio 8 2005” and “NMake Makefiles” generators. For some unknown reason Visual C++ 2005 has decided not to generate the .lib files which are required to successfully link against libdlx and libnqdecs. Maybe creating the VC++ project files manually will cure the problem. After adding the CMake support I released DECS version 0.2 on Google Code.

I’ve downloaded the BOINC VMWare virtual machine and configured a local BOINC server with the uppercase sample application. I also downloaded the BOINC source code (including sample applications) and successfully compiled the sample applications for the i686-pc-linux-gnu, windows_intelx86 and windows_x86_64 platforms. Then I deployed the newly compiled application versions to the BOINC server and tested the one for windows_intelx86.

I encountered another strange problem with VC++ when I tried to compile the BOINC sample applications. Some “access denied” error kept showing up when VC++ tried to embed some manifest to the executables. It disappeared when I turned off manifest embedding. Later when I had successfully compiled all the sample applications I turned the manifest embedding back on and the problem was nowhere to be seen. Standard Microsoft logic I guess. Not that I care what the manifest thing does anyways.

I’ve also figured out a way to parallelize the Dancing Links algorithm, so implementing that will be the main focus from now on, along with writing on the report. The end result will be that the matrices being sent to the worker nodes will be smaller than the original matrix. This will require some changes to the file format and also a smart way to merge the results back together. Hopefully I’ll have a distributed computing sytem that actually works by the time the deadline rears its ugly head.

NOTE: This post has been imported from my old it’s learning ePortfolio DECS blog.

Milestone 2 achieved

The DLX library has been verified to work correctly and provide the correct number of solutions for n-queens with n=2,3,4,5,6,12.

Hurray! :D

NOTE: This post has been imported from my old it’s learning ePortfolio DECS blog.

Progress report for week 39

Good news, bad news. The bad news is that my laptop still hasn’t been fixed and I’ve had some trouble accessing the BOINC homepage lately, so I haven’t got a chance to download and test it for myself. I keep getting “connection timed out” when I’ve tried accessing it from school and at home.

The good news is that I’ve received two much needed reference books:

  • “The C Programming Language, Second Edition” by Kernighan and Ritchie
  • “The C++ Programming Language, Special Edition” by Stroustrup

I admit that I liked Kernighan and Richie’s book best because it’s about 700 pages shorter than the one by Stroustrup and it’s more to the point. I’m thinking about reading the C book from beginning to end because I like K&R’s writing style. Even though C++ is a more comprehensive language than C, a significant portion of the content in the C++ book feels superficial. It’s a good reference book, but not one that I would read from beginning to end. In that respect I prefer Bruce Eckel’s two “Thinking in C++” books.

I finally wrote the missing code for initializing the “boolean matrix circular quad-linked list” (BMCQL) data structure used by the DLX algorithm. That means that the libdlx library is more or less functional. However, not everything went according to plan. I spent about 6 hours to debug some silly mistakes I did in a couple of getters and setters. I was almost certain that I was doing something wrong with some of the pointers, but strangely enough they appeared to work without a hitch. On the bright side at least I gained a much better understanding of how pointers work.

A program using libdlx to solve exact cover problems has also been written. I’ve simply called it “dance”. It has been used to verify that the DLX algorithm has been implemented correctly. I’ve only tried it on a couple of small matrices I have written by hand, but I’ll soon test it on some n-queens problems as well.

By successfully implementing the DLX algorithm the first milestone of the project has been achieved. The completion of the second milestone will be announced as soon as I’ve been able to verify the correctness of the implementation by running it through some of the n-queens problems.

I’ve added some pseudo code to the report about the BMCQL data structure initialization and written more about the implementation. The dance program and the DLX library version 0.1 has been released on Google Code. The binaries are only available for Windows, but it shouldn’t be too much of a problem to compile it in Linux. A basic makefile will be added shortly.

Update: As you might notice I also figured out how to reorder the posts into reverse chronological order. Unfortunately I’ve been unable to find my way back to where this functionality is hiding so this post is stuck in the wrong position (at the bottom).

Update: After some research I found the ordering functionality. On the Portfolio page where you have a list of the portfolio elements you have to change the category. Use the drop down list on the right side and change it to “No category” (or whatever category you’re trying to sort) instead of “All” in order to access the ordering mechanism. Makes perfect sense, right?

Update: The BOINC homepage appears to be back online.

NOTE: This post has been imported from my old it’s learning ePortfolio DECS blog.