June 20th, 2009
The 5th problem of the Intel Threading Challenge 2009 Contest is a bounded knapsack problem with real numbers instead of integers. You can get more information about knapsack problems in “Knapsack Problems: Algorithms and Computer Implementations”, Silvano Martello and Paolo Tooth, which is a free book. I implemented a classical dynamic programming algorithm using Intel Threading Build Blocks to parallelize it. More information on dynamic programming in “Introduction to Algorithms, Second Edition” .
The approach I took to solve the problem is really naive due time constraints. The problems I found were:
- Convert a bounded knapsack problem to a 0-1 knapsack problem.
- Convert real number weights and benefits to integers.
- Parallelization of the serial algorithm.
- Memory efficiency.
The serial algorithm is really naive:
- Convert the weights and values to integer numbers.
- Convert the problem to a 0-1 knapsack problem repeating bounded limit times the items.
- Solve 0-1 knapsack problems with a dynamic programming algorithm.
- Trace back the items.
As you see this approach is the classical example of dynamic programming you can find in textbooks. Although it has big problems when you try to solve big data. Repeating the items bounded limit times its a really easy way to convert the problem but needs tons of memory. Multiplying by 100 makes the deal, but it can lead to rounding precision problems. The parallel algorithm is the same but using a “parallel_for” to replace the second for loop of the algorithm.
Well, the solution proposed is very naive, so I don’t expect good results in the contest. Anyway, I enjoyed the problem and I’m already thinking about the next one: “Segment intersection”.
Posted in Codepixel, Contests | No Comments »
June 8th, 2009
Intel Threading Challenge 2009 is an intel contest where you have to implement a multi-threaded solution for a given set of problems using any tech you want (not necessarily from intel) but taking into account the test machine specs. The problems are spawned every two weeks with 19 days to complete the task. There are two phases with six problems to solve. The score in a phase will be the sum of your three best scored submitted solutions. The solution should include a kind of report and of course the source code. You can find here an example of the report and more information about the rules, prizes, etc… here. The contest is managed, or at least it seems so, by Dr. Clay Breshears. As his bio shows, he is a really experienced engineer. Recently, he published a book on parallel programming “The Art of Concurrency: A Thread Monkey’s Guide to Writing Parallel Applications“, which I’m going to buy after I read “Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism“and “The Art of Multiprocessor Programming“. By the way, he made a hell of a fun video about concurrent programming: “A visual guide to key concepts in threaded programming – Common problems and how to solve them”
I really don’t have much time but I could enjoy participating in this contest and well, it’s a nice excuse to get my hands on Threading Building Blocks. I’m going to give a try for the next couple of weeks to the first problem (bounded knapsack problem) and I will see if I have fun. Don’t expect any graphics related tests/tech demos in the meantime although I want to show something of the entry development. For the moment, I don’t know exactly what I’m going to show but I will.
Posted in Blog Things, Codepixel | No Comments »
June 4th, 2009
Features
- Opengl based application showing quadratic curve rendered on the gpu with GLSL shaders using Charles Loop and Jim Blinn technique.
Downloads:
Read the rest of this entry »
Posted in Codepixel, Tests | No Comments »
May 27th, 2009
Features
- Opengl based application showing constrained delaunay triangulation of a given string by the user, using Triangle library and Freetype library.
Downloads:
Read the rest of this entry »
Posted in Codepixel, Tests | No Comments »
May 20th, 2009
Posted in Codepixel, Tests | No Comments »
May 20th, 2009
Six months ago I published my last tech demo and with it, my last blog entry. I would like to say that this break time was something I chose, but I didn’t. I didn’t even know what was happening. Six months later I can say I know it, I’m working on it and I’m very happy with the results I’m getting.
Read the rest of this entry »
Posted in Blog Things, Codepixel | 1 Comment »
November 3rd, 2008
Posted in Codepixel, Tech Demos | 7 Comments »
October 31st, 2008

On May the 30th I gave a talk called “How to get the graphics job of your dreams” (presentation in spanish) to the people of the Graphics,Games and Virtual Reality Master at URJC University in Madrid. Yes, you are right, that was the talk´s name! Thanks to David Miraut for it. I really couldn´t think of any other name that fits as nice as this one within the core idea I tried to transmit: ILLUSION.
CG people are the kind of people that spend every moment they can doing CG. Its a dream, a passion. Simply enough, it drives our lives. It leads you to learn as much as you can, to work hard to get a new demo or not to give it up when hard times come. Most of the people attending to the talk had no professional experience. They were right in the moment when you are trying to break into the industry, just trying to make their dream comes true: get the first graphics job.
However, all that passion needs control, a path to follow that can lead you to your first CG job. That was the content of my talk. I walked every step needed to get a graphics job. Of course this way isnt necessarily the only one. Its based on my experience and the experience of other industry colleagues.
Posted in Blog Things, Codepixel | 2 Comments »
October 22nd, 2008
Siggraph is the most important Computer Graphics conference in the world and, luckily enough for us, it is all about volunteering too. If you are serious about Computer Graphics you should apply for a Siggraph Volunteer Program. There are three different programs:
There are three volunteer programs:
- Student volunteer (2009)
- Ex-Student volunteer (2009)
- Conference volunteer (2009)
Read the rest of this entry »
Posted in Blog Things, Codepixel | No Comments »
October 16th, 2008

A month after my (first) Siggraph experience, I already have some thoughtful conclusions. The experience has been awesome! I will just give you a brief idea of what it meant to me and what my role was there: I have been an Ex-Student Volunteer working inside GraphicsNet Team. Basically, the GraphicsNet team is in charge of giving network support to the whole conference center. So, we provided service between the conference center network team and Siggraph conference. That included running cables through the whole conference center to connect every venue and every room that required it.
Working with the GraphicsNet guys has been great. They are very talented, they have a lot of experience (a member of the team has been at Siggraph since the 80´s!), they really know how to do their job and, well, I was learning something new every moment. They have been doing this forever, so they have a robust and clear network design. What I had to do was easy, but trust me if I said that it was a huge amount of work! I have never run so much cable in my whole life. But honestly, I didn´t care. I was in heaven! I have seen the entire process of Siggraph, from the very beginning (guys setting up all the furniture), to the end (same guys removing all the furniture).
Read the rest of this entry »
Posted in Blog Things, Codepixel | 1 Comment »