SZTAKI Desktop Grid has been set up by the Computer and Automation Research Institute of the Hungarian Academy of Sciences (MTA). Desktop grids allow vast number of single PCs to be connected in a grid-like system, adding up their processing power. Desktop grid systems are currently serving several cutting edge research areas, like cancer research or climate change.
SZTAKI Desktop Grid project URL; http://szdg.lpds.sztaki.hu/szdg/
About SZTAKI Desktop Grid
SzDG is an online architecture, run by the Laboratory of Parallel and Distributed Systems. The staff of the laboratory maintains the system, which is open for any scientific research (see the section on DC-API to get an idea of the characteristics of suitable applications) seeking immense computing power. SzDG currently hosts one mathematical project.
Project BinSYS was established by the Department of Computer Algebra of Eötvös Loránd University. The aim of the project is to find all the generalized binary number systems up to dimension 11.
The program aims at finding many generalized binary number systems. An extensive search is performed in the finite set of matrices of given size fulfilling some necessary conditions. The difficulty is that the size of this finite set is an exponential function of the dimension. It now seems possible to attack the case of 11 × 11 matrices. To check further necessary conditions the program performs a lot of floating-point calculation. Thus, a lot of CPU time is needed. Luckily, parallelization is possible, so the project can benefit from running on multiple machines.
The program outputs a list of matrices (to be more precise, their characteristic polynomials) that are already likely to be number system bases. This list is processed by another program (which does not need so much CPU-time). The final result is then a (complete) list of binary number systems in a fixed dimension.
In beta phase, the project started by investigating the 10th dimension, which entailed the processing of ninety thousand matrices, of which a total of 383 pieces seemed to be worthy of further inspection.
The Distributed Computing API (DC-API) was created by the laboratory to help the developers of distributed applications to overcome the difficulties of program development. The API hides the idiosyncrasies of BOINC, allowing developers to focus on their own research tasks. The API comes prepacked in a Debian package, available freely from the official website indicated below.
The DC-API allows easy implementation and deployment of distributed applications on multiple grid environments.
In order to accommodate the needs of very different grid environments, the DC-API supports only a restricted master-worker programming model. The restrictions include:
Master-worker concept: there is a designated master process running somewhere on the grid infrastructure. The master process can submit worker processes called work units.
Every work unit is a sequential application.
There is support for limited messaging between the master and the running work units. It can be used to send status and control messages, but it is not suitable for parallel programming.
There can not be any direct communication between work units.
The aim of the project is to find all the generalized binary number systems up to dimension 11. Below we give a short description of the number system concept and mention a few possible applications.
Let n be an integer greater than one. When we speak of number systems in the original sense, we use the fact that each natural number z can be written uniquely in the finite form
We say that n is the base of the number system, the are called the digits. If n = 2 then we speak of a binary number system. These systems are too poor to represent negative numbers so we need a sign. If we allow the base to be a negative integer, a representation of all integers may become possible. Such, for example if we use the base -2, each integer has a form
This can be generalized for the algebraic integers of a finite extension of the rational number field. A simple example: all the Gaussian integers (complex numbers of the form x+yi, where x,y are integers) can be written uniquely in the base (-1+i) as follows
Using linear algebra we can define number systems in an even more general way. The base is now a matrix and the digits are vectors. We can reformulate the previous example. Each two-dimensional integer vector has a representation as a finite sum
We speak of a binary system if the determinant of M is ±2. In this case there are only two digits, one of them being the origin. This means that if we have a number system then every integer vector can be represented as a finite series of 0s and 1s.
Not every matrix M can be a number system base. Until now no characterisation of ”good” matrices have been given. There are sufficient conditions and there are necessary ones but the gap between them is too large. There is no known efficient method of dealing with matrices that fulfil necessary conditions but fail sufficient conditions. One thing to note is that if we fix the determinant and the dimension then roughly speaking there are only a finite number of possible matrices.
The program aims at finding many generalized binary number systems. An extensive search is performed in the finite set of matrices of given size fulfilling some necessary conditions. The difficulty is that the size of this finite set is an exponential function of the dimension. It now seems possible to attack the case of 11 ´ 11 matrices. To check further necessary conditions the program performs a lot of floating-point calculation. Thus, a lot of CPU time is needed. Luckily, parallelization is possible and we can benefit of running on several machines.
The program outputs a list of matrices (being more precise characteristic polynomials) that are already likely to be number system bases. This list is processed by another program (which does not need so much CPU). The final result is then a (complete) list of binary number systems in a fixed dimension.
Thereafter we perform information theoretical analysis. The number systems provide a binary representation of integer vectors. Using coordinates we have another (more standard) representation. The two representations usually differ in length. Besides, vectors close to each other in the space can have binary representations that look very different. These observations suggest that one could apply number systems in data compression, coding or cryptography.
Number systems are interesting from a geometrical point of view, too. If we allow negative powers of M to appear in the binary representation we get a possibly infinite representation of real vectors (we could say that we use a radix point). The boundary of the set of vectors with binary representation containing only negative powers of M (the set H of numbers with zero integer part) has mostly fractional dimension (it is a „fractal”). The output of the program can be used to analyze these sets. This means topologocal analysis, e.g. calculation of the dimension, connectedness etc. If we use the matrix M above, we get the following set.
Finally, knowing all matrices up to a given dimension could help us to a deeper understanding of the mathematics of generalized number systems.
Video about "The Grid" at CERN in Geneva
This video is not about the SZTAKI desktop grid, its about a much bigger computing grid being built by CERN in Geneva but this video is pretty cool and gives you and idea of what grid computing can be used for.
|< Prev||Next >|