Tag - proceedings

Study of the NP-completeness of the Compact Table

Saturday 26 April 2008

The problem of compact tables is to maximise the overlap when building a word that is to include permutations of every given words (all the words being the same length). This problem is shown to be NP-complete in the general case, and some specific restrictions are studied.

To show this on a small example (beyond what is in the article), imagine that in a game (like checkers) if blue takes red, on a result of 1, both are eliminated, on 2 or 3, red remains and blue remains in the other cases. If red takes blue, results 1 to 4 make red win and on 5 to 6, blue wins. The compact table in this case would be to keep the table as is in the blue versus red, add +2 if red versus blue, with results 7 and 8 letting red win.

Continue reading

Renpar 18

Monday 25 February 2008

I went to Renpar 18. Renpar is a periodic meeting of the French parallelism community meeting, with some long talks by guests and short talks, mainly for students and young researchers. It took place in Fribourg (Switzerland) this year. I especially enjoyed the two last invited talks (computer engineering in the fifties, and a presentation of economic models for free software by a senior manager of Mandriva).

Heithem Abbes, a Tunisian student with whom I work, made a talk. No surprises there. The organisation of the conference was very good, with unlimited access to the transportation network of the city of Fribourg.

Many contacts were taken for further research collaboration, with people usually too far to talk with. That is good.

The social event was a tour of the village of Gruyère, where the most famous cheese is produced. We saw the castle first, then a cheese factory. The evening took place in a restaurant, where we had a wonderful cheese fondue.

More pictures available on my personal blog.

Continue reading

Performance Analysis of Publish/Subscribe Systems

Tuesday 15 January 2008

The Desktop Grid offers solutions to overcome several challenges and to answer increasingly needs of scientific computing. This technology consists mainly in exploiting PC resources, geographically dispersed, to treat time consuming applications and/or important storage capacity requiring applications. However, as resources number increases, the need for scalability, self-organisation, dynamic reconfiguration, decentralization and performance becomes more and more essential. Since such properties are exhibited by P2P systems, the convergence of grid computing and P2P computing seems natural. In this context, this paper evaluates the scalability and performance of P2P tools for registering and discovering services (Publish/Subscribe systems). Three protocols are used in this purpose: Bonjour (définition), Avahi (définition) and Pastry (définition). We have studied the behaviour of these protocols related to two criteria: the elapsed time for registrations services and the needed time to discover new services. Our aim is to analyse these results in order to choose the most adequate protocol for creating a decentralized middleware for Desktop Grid.

Continue reading

Methods for Partitioning Data to Improve Parallel Execution Time for Sorting on Heterogeneous Clusters

Thursday 10 January 2008

The aim of the paper is to introduce general techniques in order to optimize the parallel execution time of sorting on a distributed architectures with processors of various speeds. Such an application requires a partitioning step. For uniformly related processors (processors speeds are related by a constant factor), we develop a constant time technique for mastering processor load and execution time in an heterogeneous environment and also a technique to deal with unknown cost functions. For non uniformly related processors, we use a technique based on dynamic programming. Most of the time, the solutions are in $\mathcal{O}(p)$ (p is the number of processors), independent of the problem size n. Consequently, there is a small overhead regarding the problem we deal with but it is inherently limited by the knowing of time complexity of the portion of code following the partitioning.

Continue reading

Signals for Cellular Automata in Dimension 2 or Higher

Wednesday 9 January 2008

In this article, co-written with Véronique Terrier for the Latin 2002 conference, we investigate how increasing the dimension of the array can help to draw signals on cellular automata. We show the existence of a gap of constructible signals in any dimension. We exhibit two cellular automata in dimension 2 to show that increasing the dimension allows to reduce the number of states required for some constructions.

Continue reading