Progress report for week 49

The report is comming along nicely. It is currently undergoing revision and is expected to be done by the deadline the 20. December.

Inspired by a comment by Hein Meling I put together some notes on how the Dancing Links algorithm could be made non-recursive (read: neither recursive nor iterative). It was more of a side comment from his side, but I’m prone to fall for nerd sniping so this is nothing new.

The BOINC server for the project is now available for the public. It’s not really production ready yet, but take a look if you’re interested.

NOTE: This post has been imported from my old it’s learning ePortfolio DECS 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.

Progress report for week 37

In week 37 I’ve been working on the report and I’ve written about the architecture design and about exact cover problems and a bit about how the Dancing Links algorithm works. I’ve been looking into some of the other Dancing Links implementations which are released as open source and tried to see how they solved the problems. Most of the implementations were made for one specific purpose (solve sudoku, n-queens and polyomino problems). This is different from my implementation which will be a generic solver, but with direct support for some of the specific problems.

The file format which the problem matrices will be stored in has been sketched out, but I need to investigate what features the Grid middleware has for dealing with file transfer and reading. My main canditate is BOINC, but I’ll be checking out other possible options soon.

I’ve been a bit busy with another report so I’ve not been able to fully implement one of the problem transform like I had planned. Other than that everything is going according to the plan. I’ll make an extra effort to neutralize the slippage the following weeks.

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

Progress report for week 36

In order to expand my limited knowledge of C/C++ I’ve started to read and use the following books as reference material:

  • “Thinking in C++, Volume 1, 2nd Edition” by Bruce Eckel (free version)
  • “Effective C++, 3rd Edition” by Scott Meyers
  • “Sams’ Teach Yourself C in 21 Days, 4th Edition” by Peter Aitken and Bradley L. Jones

I’ve also read an article or two in the book “Game Programming Gems” (edited by Mark DeLoura) while looking for a good way to store and manipulate the boolean matrices for the DLX algorithm. I’m leaning towards using Andrew Kirmse’s code from the “Simple, Fast Bit Arrays” article which has a license on the following form: “As long as you keep the copyright notice you can do whatever you want with it”. Not sure how that will interact with the GPL license I’m using, but I’ll figure out something.

I’ve checked out Donald Knuth’s own DLX program: dance.w. He uses a system called CWEB (hence the .w) to write his programs so I had to download, compile and run that in order to convert dance.w into dance.c. Then I could finally compile it. With my limited C knowledge I only understood bits and pieces, but I’ll keep trying as I learn more. I could argue that I don’t understand everything because he uses a handful of GOTO statements, but that’s not where I get stuck. Still, I don’t think Dijkstra would have approved of those GOTOs. Knuth has also written a more general version of the DLX program named gdance.w, but I’ll visit that after I’ve intellectually conquered dance.w.

My own implementation of the DLX algorithm in C++ is also complete. I’ve spent more than a few hours trying to befriend C++ and I think I’m finally getting the hang of it. I’ve implemented the algorithm as a shared library (.dll in Windows .so in Linux) by following the pseudo code from Knuth’s paper. My code uses the same variable names and it follows the same structure as in the paper. The storage, manipulation and transformation algorithms which takes the input boolean matrix and turns it into a collection of objects is still under development. This means that I’ve not actually tested the DLX implementation, but seeing how similar it’s to the pseudo code there is a fair chance that it might actually work.

I’ve also reread the paper “PRP – Parallel Recursive Procedures” by Arne Maus and Torfinn Aas in order to get some more ideas on how to parallelize the DLX algorithm. As I was implementing the DLX algorithm I wrote a bit about the implementation and some other challenges which are yet to come. Currently the progress on the project is as scheduled by the project plan.

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