GPGPU using CUDA Thrust

Long time no see!

I just want to share the presentation that I gave during our weekly meeting in the CGV group in Delft. Usually we do two kind of presentations, the first one is related to our current project, while the second one is more technical and aims at teaching something useful to the other members of the group.

This presentation is of the second type. It aims at showing how CUDA Thrust can be used to implement GPGPU solutions without too much effort.

I think that CUDA is a great platform and I did a lot of work using it. 

However it is difficult to master and, without any high level interface, CUDA code is slow to implement.  I gave a couple of examples in my presentation:

1. Preparing a CUDA kernel launch is somehow an annoying task. More than that the problem is related to the handling of the memory in the Device. I like how the OpenCV wrapped all the handling in the GpuMat class, however it is something that must be careful planned ahead and well designed with clear specifications.
2. Memory access influences the performance: This is a key point! It is not so easy to implement an efficient algorithm in the GPU. You can find some details about all the challenges related to memory access at this link.

CUDA Thrust is a parallel algorithms library which resembles the C++ Standard Template Library (STL) and implements many common algorithms that can be used during your daily work.

So if you are already using STL's algorithms and data structures in your code, and you are tackling big problems by decomposing it to small and well known algorithms, CUDA Thrust can be very useful and easy to pick.

GPGPU using CUDA Thrust from Nicola Pezzotti

std::async, std::future and lambda functions to keep GUIs responsive

It has been quite some time since my last post :)

This week I submitted my first paper as a PhD student in TU Delft and I had to shot some video to show my work. I had to show some analytic routine that require some time to be computed but I wanted to keep my GUI responsive, so that the video would results nice.

Imagine that you have a class that is similar to the following one:
You may want to call a method of the class that it is slow to compute. If you do that in the following way the the (Not Responding) problem in your GUI will occur.
The easiest way to solve this problem is to use some cool features of C++11, std::future, std::async and the lambda functions. I use std::async to launch a thread where a lambda function is used to isolate the slow computation. A std::future is used to check if the asynchronous thread has completed the computation and meanwhile the application is refreshed.
there you go :)

PhD: Visual Analysis in Population Imaging Research (VAnPIRe)

It's been a long time since I posted something on the blog!
I've been quite busy in the last three months because I applied for a PhD position at the Delft university of technology

This is the description of the position which I applied for:

The PhD/PostDoc position will be part of the Population Imaging Genetics project (stw-imagene) that involves linking observations on the human genome to observations in imaging data. Novel, genome-wide sequencing approaches combined with large-scale population imaging studies open up unprecedented possibilities for discovering the cause of a disease and relating it to its anatomical and functional consequences.
The exact nature of the features (markers) that have the highest correlation with the clinical outcomes under study is by definition hard to predict. Due to the magnitude and heterogeneity of the data, as well as the nonspecific nature of the features that are being sought, this is a complex and laborious process.
We envision a new class of visual analysis techniques that enable the structured and interactive visual exploration of population imaging data. With these techniques, patterns and high-potential hypotheses can be flexibly derived from population imaging data, aiding both the derivation of insight and the search for predictive data features.
The main aim of this project is to develop and evaluate a new, interactive visual analysis approach that enables the extraction of patterns and high-potential hypotheses from the irregular and complex population imaging research data.
New insights into the mechanisms behind the clinical outcome of a population can be extracted by augmenting the human visual system with interactive visualization and coupled feature extraction techniques.

After some Skype interview and a visit to Delft they have chosen me for the job! :)
I'm really excited and I'm looking forward for the opportunity to work in the computer graphics and visualization group of one of the best university in Europe!

OpenWorm: A Digital Organism In Your Browser

The kickstarter founding campaing is coming to an end for the OpenWorm project.

You may ask, "what is OpenWorm?".
"OpenWorm is an open science project aimed at building the first digital organism, a microscopic worm called C. elegans. With this KickStarter we want you to join us in contributing to the creation of the first digital organism and we want to give you your own WormSim to play with on your web browser. Your WormSim will improve over time and will get smarter as our model gets better and closer to the real one."

"Science still does not understand the human brain to the level needed to cure diseases such as Alzheimer’s and Parkinson’s. Believe it or not, science doesn’t even fully understand the brain of a simple worm! If we cannot build a computer model of a worm, the most studied organism in all of biology, we don’t stand a chance to understand something as complex as the human brain."

I found this project really interesting and all the code is available on GitHub! (I'm actually planning to contribute to it). It's a very cool mix of different technologies and programming languages, from OpenCL for the GPGPU to OpenGL, WebGL and ThreeJS for the visualization with a lot of C++/Java/Python in the middle.

With less than a week left for the founding campaign and more than 80k$ to be pledged we have to spread the word as widely as possible!

New book on my shelves: "Data Visualization - Principles and Practice"

I have bought the book "Data Visualization: Principles and Practice" in order to improve my knowledge in scientific data visualization

The book has not many reviews on Amazon website. Despite that, they are quite good and the table of contents seems interesting to me.

In particular these are the topics that I find stimulating:

• Vector visualization
• Tensor visualization
• Multivariate data visualization

Unfortunately, neither networks nor graph visualization technique are described in the book. I could find a lot of material on this particular topic (maybe too much) and it will be the subject for my next blog post.

An Artificial Intelligence for the 2048 game

Lately the 2048 game reached a good notoriety on the internet.

A discussion about possible algorithms which solve the 2048 game arose on StackOverflow.

The main discussed algorithms are:

• https://github.com/ov3y/2048-AI (ovolve)- A minimax approach which take into account several heuristic functions - I tested it out and it turned out to have some problems in reaching the 4098 tile in a reliable way
• https://github.com/nneonneo/2048-ai (nneonneo)- A very efficient implementation of an Expectiminimax approach with a quite simple heuristic - AFAIK he has reached the highest score of 173364 but I have not tried it yet

The solution I propose is very simple and easy to implement. Although, it has reached the score of 131040. Several benchmarks of the algorithm performances are presented.

Algorithm

Heuristic scoring algorithm

The assumption on which my algorithm is based is rather simple: if you want to achieve higher score, the board must be kept as tidy as possible. In particular, the optimal setup is given by a linear and monotonic decreasing order of the tile values.

This intuition will give you also the upper bound for a tile value: $2^{n} \rightarrow 2^{16} = 65536$ where $n$ is the number of tile on the board. (There's a possibility to reach the 131072 tile if the 4-tile is randomly generated instead of the 2-tile when needed)

Two possible ways of organizing the board are shown in the following images

To enforce the ordination of the tiles in a monotonic decreasing order, the score si computed as the sum of the linearized values on the board multiplied by the values of a geometric sequence with common ratio $r<1$ .

$p_n \in Path_{0 \cdots N-1}$

$score = \sum_{n=0}^{N-1} value(p_n) * r^n$

Several linear path could be evaluated at once, the final score will be the maximum score of any path.

Decision rule

The decision rule implemented is not quite smart, the code in Python is presented here:

An implementation of the minmax or the Expectiminimax will surely improve the algorithm. Obviously a more
sophisticated decision rule will slow down the algorithm and it will require some time to be implemented.I will try a minimax implementation in the near future. (stay tuned)

Benchmark

• T1 - 121 tests - 8 different paths - $r = 0.125$ 
• T2 - 122 tests - 8-different paths - $r = 0.25$ 
• T3 - 132 tests - 8-different paths - $r = 0.5$
• T4 - 211 tests - 2-different paths - $r = 0.125$
• T5 - 274 tests - 2-different paths - $r = 0.25$
• T6 - 211 tests - 2-different paths - $r = 0.5$

In case of T2, four tests in ten generate the 4096 tile with an average score of $\sim 42000$

Code

The code can be found on GiHub at the following link: https://github.com/Nicola17/term2048-AI
It is based on term2048 and it's written in Python. I will implement a more efficient version in C++ as soon as possible.

StackOverflow

You can upvote my answer on StackOverflow here :)

Polygon mesh data structure

My first tests with OpenGL use a triangle soup which is basically a collection of triangles with no relationship whatsoever. In order to implement a more complex shader I need to work on a more complex and powerful data structure: the polygon mesh

A polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling. The faces usually consist of triangles, quadrilaterals or other simple convex polygons, since this simplifies rendering, but may also be composed of more general concave polygons, or polygons with holes.

[Wiki Polygon Mesh]

There's a variety of ways to represent a polygon mesh and they basically differ in how the vertex and topology information are stored. One of the most used representation in the filed computer graphics and geometry processing is the halfedge data structure.

Polygonal meshes consist of geometry (vertices) and topology (edges, faces). Data structure for polygonal meshes mainly differ in the way they store the topology information. While face-based structures lack the explicit representation of edges, and edge-based structures loose efficiency because of their missing orientation of edges, halfedge-based structures overcome this disadvantages. The halfedges (that result in splitting the edges in two oriented parts) store the main connectivity information:

Intuitively, this provides a natural and simple way to represent vertices, edges and faces, as well as arbitrary polygons. 

[OpenMesh]

Many operations and queries are very natural on the halfedge data structure, in particular the circulation on the neighbors of vertices and faces.

Traversal of one-ring neighbors of a center vertex. From left to right: 

1. Start from center vertex. 
2. Select outgoing halfedge (and access its target vertex). 
3. Move to previous halfedge. 
4. Move to opposite halfedge (access its target vertex)

[SB11]

As far as i know the high-quality publicly C++ libraries available are:

1. CGAL
2. OpenMesh
3. SurfaceMesh



CGAL Logo

4. Mesquite

I have never used Mesquite. This is mainly focused on the mesh optimization [BFKLM03]. Although the CGAL is a very powerful library for the compuational geometry, its polygonal mesh implementation has a major drawback: all the custom properties associated with a mesh entity must be declared at compile time.

Aachen University
Computer GraphicsLogo

OpenMesh and SurfaceMesh are more flexible and much easier to use than CGAL. OpenMesh was originally developed at the Aachen University [BSBK02] and the version 3.0 was recently released. On the other hand SurfaceMesh is more recent [SB11] and it was developed at the Bielefeld university.

They have very much in common, starting with one of their developers, Mario Botsch who is also the head of the Computer Graphics & Geometry Processing Group at Bielefeld.

Based on our experience in academic research and teaching as well as in industrial cooperations, our primary design goal [of the SurfaceMesh] is ease of use. An easy-to-use data structure is learned faster, allows to focus on the main problem (instead of on the details of the data structure), and fosters code exchange between academic or industrial research partners. The data structure should therefore be just as flexible and generic as needed, but should otherwise be free of unnecessary switches and parameters. At the same time, however, we have to make sure not to compromise computational performance and memory consumption. Otherwise the data structure would be easy to use, but not useful, and hence would probably not be used at all.
[SB11]

The SurfaceMesh primary design goal is the ease of use, therefore it satisfy the requirements for the OpenGL-Sandbox very well, therefore I will adopt it as a polygonal mesh data structure in my program.

In the end I'll show you an example of the SurfaceMesh which computes the mean valence of the mesh vertices

References

[SB11] Design, Implementation, and Evaluation of the Surface_mesh Data Structure
[BFKLM03] The Mesquite mesh quality improvement toolkit

[BSBK02] OpenMesh – a generic and efficient polygon mesh data structure
[OpenMesh]
[Wiki Polygon Mesh]
[CGAL]
[Mesquite]