Progress report for week 51

The DECS project report is complete and has been delivered for evaluation. The report can also be downloaded from the link below. I’ll also add some work units to the BOINC server soon, so that people can try it out.

If you happen to need software for plotting I highly recommend gnuplot. I also tried R for a few hours, but that is a chapter in my life I would rather forget. gnuplot lets me do exactly what I needed in a few simple steps, which is more than I can say about R. It might be because the documentation for gnuplot is so exellent or because there are so many good tutorials, but I managed to whip up a couple of graphs in no time at all. If you want some work done, and you want it done now then gnuplot is your friend.

BTW, this is probably the last DECS progress report as well. At least on this website. At least for now :)

Jan Magne,
Over and out

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

Progress report for week 50

A new draft of the report is complete. This time all the chapters are in place and all the “??” references has been eliminated.

The following is a list of modifications made to chapter 1 and 2:

• Fixed typos and minor word and sentence bugs.
• Moved first paragraph of Section 2.1 to Chapter 1.
• Added reason for redifining ‘one’ to ‘non-zero’ (disambiguation) in second paragraph of Section 2.1.
• Added reduced and identical matrix disambiguation in Section 2.1.
• Fixed notation ambiguity at the end of Section 2.1.
• Added a bit about backtracking in the third paragraph of Section 2.2.
• DeKnuthified some of the content.
• Added formal definition of exact cover to section 2.1. (Does it confuse more than it helps?)
• Added some information and a couple of illustrations about n-queens to the introduction.
• Added n-queens example with primary and secondary columns in Section 2.1.1. It also makes use of the formal exact cover definition.

Pluss the addition of the chapters about implementation, testing and simulation and the conclusion.

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

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 48

Lots and lots and lots and lots of work on the report :)

The report is coming along nicely. A draft of the first two chapters is available here. I only added the beginning as that is more or less stabilized. The rest of the report is still undergoing some significant changes so I choose not to include those chapters yet. There are some ”??” references which didn’t resolve because the sections they refer to are not included. For the moment you can just ignore them.

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

Progress report for week 45 – 47

/dev/null

For the most part I’ve been busy with other things like exam reading and a few projects. However, last week I got back to writing on the report so I’m back in business.

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

Progress report for week 44

Not much happened this week either. I’m finishing a couple of projects this week before I finally can get back to work on DECS.

I got a C on the Petri net model and simulation report of DECS that I mentioned in week 42. The reason given was that the model did not take into account the possibility of deadlocks and resource starvation.

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

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.

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.