A few days ago a diploma dropped in the door, meaning that after 3 years at Aalborg University I’ve got a “Bachelor of Science (BSc) in Computer Science”, as it says on the paper… I’m of course continuing as a master student next – no reason to get out “there” in the real world, where you have to work, assuming you don’t what to starve

Anyways, it occurred to me that I haven’t blogged about my Bachelor project. So I better get it done now, as I’m off for vacation in California later tonight… This semester we worked in groups of 3, and was supposed to write a 12-20 pages article, as opposed to a 100-200 pages report. Which turned out to be quite challenging, but also somewhat nice, because we got to polish every sentence.

As the title of the post indicates we did a project about Petri nets, a very simple but powerful modeling language. To achieve a “feeling” of novelty we introduced global discrete variables, that you can condition on and modify in transitions, and called our new model for Petri nets With Discrete Variables (PNDV). Whilst, to my knowledge, this have not been done before, we didn’t focus on showing that PNDVs where particularly useful for any specific purpose. So that part of the project feels a little shoehorned, at least to me, and maybe only me, because we all got an A for the project.

Nevertheless, assuming that the PNDV model (we invented) is interesting, then the graphical Petri net editor and verification tool we wrote during this project might also be interesting. In a desperate search for a name we came up with PeTe, yes is spelled pretty weird, but also quite cute

Given a PNDV or Petri net PeTe can determine if a state satisfying a given formula is possible. This problem is very hard (EXPSPACE-hard), but we had a lot of fun writing different search strategies for exploring the state space of a PNDV. Most notably we found that even quite simple heuristics can provide a huge performance improvement by guiding a search in state space. We also had great success with over-approximation, by using state equation and trap testing to disprove the satisfyability of a formula.

The heuristics and methods implemented in PeTe is presented in the article we wrote, available for download below. This article also present some, in my opinion, rather shoehorned results, like translation from Discrete Timed Arc Petri Net to PNDV. I also can’t help but feel that the direction and goal in the article could have been more clear. But done is done, and I’m off to vacation when I’ve added some links

• Petri Nets With Discrete Variables (pdf, 0.7MiB)
• PeTe project page at github

This semester we did a project in machine intelligence, however, as I find probability calculus and Bayesian networks utterly boring I convinced my group to do a project about triangulation of Bayesian networks. A triangulation of an undirected graph G, is a set of edges called fill-ins, such that G with these fill-ins added is a chordal graph (a graph that doesn’t have a chord-less cycle of more than 3 node). Triangulation is of graphs is used for many purposes, and with difference optimality criteria, such as minimum fill-ins, minimum clique size (tree width) and minimum maximal clique sum (optimal table size), as is relevant for Bayesian networks.

The problem of finding an optimal triangulation is NP-Hard (with respect to mentioned optimality criteria). And since there’s many fairly good simple greedy heuristics, it can be argued that algorithms for optimal triangulation of Bayesian networks are uninteresting. However, to check of a greedy heuristic is good, optimal triangulations are needed. It’s also possible that optimal triangulation might be worthwhile if  computed offline, especially if the application needs to process a lot of data or work on an embedded platform. Or whatever, optimality is always slightly interesting, if not for anything useful, than for the fun of finding them…

In this project we implemented some simple greedy triangulation heuristics, compared their result to the optimal solutions. But most interesting is probably our work on search algorithms for optimal triangulations of Bayesian networks. We based our work on two articles by Thorsten J. Ottosen and Finn V. Jensen, who does a best or depth first search in the space of all elimination orders. As far as we’re aware these articles are the only ones that proposes algorithms for optimal triangulation of  Bayesian networks.

In this project we’ve created good improvements to the optimal triangulation algorithms. We reduce the search space by excluding elimination orders resulting in the same triangulation. Our improvements provides around 5x speedup on sparse graphs, and can be applied to regardless of the optimality criterion. I think this project was really cool, because I got to play with something that was new and fairly untouched. And the fact that I managed to propose a a few interesting improvements didn’t make it any less cool

Report and source code:

• Project report (0.7 MiB PDF)
• Source code for implementation (47.8 MiB tarball)

Hmm… Not the official title of my fourth semester project at Aalborg University. For which I just got an A… and have been thinking about publishing since I handed it in.

This semester my group have designed and implemented a small statically typed object oriented language slightly inspired by Python. We wrote our own lexer and parser generator in Python, and implemented the compiler in C++. And just for the record we implemented the DFA of the lexer and PDA of the parser using goto’s, inspired by re2c, this was quite fun and the result very fast.

The language is called groo (that was the best name we could come up with), it compiles into gril (groo intermediate language) which in turn run on VROOM (groo virtual machine) where memory is managed by MOM (Mark-sweep Object Manager). Whilst this isn’t the best project yet, and all the acronyms doesn’t make much sens, I really like to say that when we need to release memory we call MOM to clean up
(I appoligies for my crazy sens of humor).

I don’t think the project is of much use to anybody else… But if you want to play with simple, well documented compiler in C++, this might be it… Also the parser generator is AFAIK pretty unique, haven’t see anybody else implement a parser using goto’s… Anyway the project report and groo compiler source code is all in English and available here:

• Project report (1.5 MiB PDF)
• Compiler source code (16,5 MiB tarball)

Now I’m finally done with my second semester project at Aalborg University, and as usually I publish my things here. This project is about distributed realtime ray tracing. Which have been fun, because ray tracing is CPU bound and it have been a joy to play with all sorts of hacks and optimizations.

The report discusses what the demand for ray tracing is, what ray tracing is and how a ray tracer can be implemented, covering the basics of ray tracing and bounding volume hierarchies. It also discusses how distribution could be done, which is the only slightly new thing in it… It’s not a perfect report there’s still some areas where the English is kind of bad and some sections that could use a rewrite or two
Nevertheless, considering the circumstances I’m satified the result. And the group have worked fine…

Now the interesting part, TheMatrixDistributed, as a part of this project we implemented a distributed realtime ray tracer, with bounding volume hierarchies, spheres, planes and triangles that supports textures. We also did a small obj parser to import models exported from Blender. TheMatrixDistributed is implemented in C++ and it’s turned out to be quite fast, considering that the rest of my group have little to no programming experirence. When distribution to 6 dualcore laptops and a quadcore desktop we got around 8 FPS at best with 1024×768 screen and about 100,000 triangles in the scene, not filling the entire screen.

The frontpage image (original 1024×768) seen above has about 1,000,000 triangles it was render on 6 dualcore laptops and a quadcore desktop at about 0.6 FPS with 4x antialias.

Though the report and TheMatrixDistributed probably isn’t of much value to anybody it’s published here if anybody should be interested. The report is released under Creative Commons Attribution-Noncommercial-Share Alike 2.5 and TheMatrixDistributed is released under GNU GPL.

• Realtime ray tracing distributed (twoside)
• TheMatrixDistributed (source and binaries)