Beginning parallel programming contest Threading Challenge
A colleague of Boomburum already showed a screenshot of a task manager of a similar monster. Four sockets, each with an Intel® Xeon® E7-4860 processor with 24MB of cache, and 64 gigabytes of RAM on top. What to do with all this wealth? I have a couple of ideas!
We are starting a parallel programming contest, the Threading Challenge 2011. Participants will have access to this machine, and the winners will go to the IDF in San Francisco, where, I hope, we will not see such pictures. The task of the competition is to download all available kernels 100%, take a screenshot and put it on Habré! Joke Not so simple.
')
The Threading Challenge is held for the fourth year in a row. For a long time I tried to translate this name beautifully into Russian, but ... If you have ideas, share, but for now I apologize for the Anglicisms. The competition is international, but the victory of Russian programmers in it has become a good tradition. For example, last year, the main prize was taken by Dmitry Vyukov, and in 2008 - Peter Trifonov. Needless to say, the victories of compatriots are very, very pleasant to us! To maintain a good tradition and facilitate the participation of those who are not very strong in English, this year we make decisions in Russian.
The rules of the competition are: there are two categories of complexity, "beginner level" and "advanced level". In each category there will be three serious algorithmic tasks. Each task is given 22 days, points are awarded for decisions. Of course, mainly for the speed, measured on the same machine, but there are all sorts of bonus. Those three who have scored more points in their category will receive small prizes (from $ 150 to $ 500).
As soon as the judges finish the assessment of the last, third task, we will calculate the total amount by participants and announce the two winners - one in the “initial” category and one - in the “advanced” category. They will go to IDF 2011 in California.
Tasks. I admit honestly, in the process of preparing the competition there was no time to sit down and estimate the algorithms. They are not very complex, but ... Let's think together?
I hope everyone knows about the game "life"? For those who do not know - there is a certain surface, divided into cells. A cell can be in two states: be alive or dead. The cell has eight neighbors. The task of "life" is to model future generations of cells according to the following rules: a dead cell, next to which exactly three living cells, comes to life. A living cell with two or three living neighbors continues to live. If there are less than two neighbors or more than three, then the cell dies, respectively, from loneliness or overpopulation. About the algorithms of modeling "life" can be read, for example, on rsdn.ru. There is a lot of room for optimization, both in terms of data storage and in terms of parallelization.
So, the task of the competition a little more difficult. It is called the " labyrinth of life ." Take the space of the game "life" and put in it the "smart" cell. This "smart" cell can move into the next cell when generations change. Her task is to survive, and at the same time reach a given cell of the playing field. The winner is the one who quickly calculates the shortest path of a smart cell from point to point.
Solve a very large puzzle " Masyu ". The essence of the puzzle: white and black circles are located in the cells of a rectangular field, it is necessary to connect the circles with vertical and horizontal lines so that a closed line is obtained. The line should not cross itself, branch or go through one cell twice. There are two additional conditions: the line passing through the cell with a black circle should rotate 90 degrees in it, and the next and previous cells should go straight, you cannot rotate. In the cells with a white circle, on the contrary, it is necessary to go straight through the cell, without changing directions, and rotate 90 degrees in the next OR in the previous cell (that is, at least on one side). The picture below is an example of solving a small Masyu puzzle. Test datasets for obvious reasons will be significantly more. The winner is the one who quickly solves the puzzle.
A detailed description of the competition tasks with examples of source data and requirements for results files, as well as detailed rules and a list of prizes are available on the competition website .
Questions (comments, suggestions) can be asked right here, or in a special forum . Reception of entries ends on a significant day on May 9th .
UPD : corrected picture.
All successful algorithmic finds! And please, don't plan anything important for September - maybe one of you will go to the Intel® Developers Forum.
We are starting a parallel programming contest, the Threading Challenge 2011. Participants will have access to this machine, and the winners will go to the IDF in San Francisco, where, I hope, we will not see such pictures. The task of the competition is to download all available kernels 100%, take a screenshot and put it on Habré! Joke Not so simple.
')
So, about the competition
The Threading Challenge is held for the fourth year in a row. For a long time I tried to translate this name beautifully into Russian, but ... If you have ideas, share, but for now I apologize for the Anglicisms. The competition is international, but the victory of Russian programmers in it has become a good tradition. For example, last year, the main prize was taken by Dmitry Vyukov, and in 2008 - Peter Trifonov. Needless to say, the victories of compatriots are very, very pleasant to us! To maintain a good tradition and facilitate the participation of those who are not very strong in English, this year we make decisions in Russian.
The rules of the competition are: there are two categories of complexity, "beginner level" and "advanced level". In each category there will be three serious algorithmic tasks. Each task is given 22 days, points are awarded for decisions. Of course, mainly for the speed, measured on the same machine, but there are all sorts of bonus. Those three who have scored more points in their category will receive small prizes (from $ 150 to $ 500).
As soon as the judges finish the assessment of the last, third task, we will calculate the total amount by participants and announce the two winners - one in the “initial” category and one - in the “advanced” category. They will go to IDF 2011 in California.
Tasks. I admit honestly, in the process of preparing the competition there was no time to sit down and estimate the algorithms. They are not very complex, but ... Let's think together?
The first task in the category of "initial level"
I hope everyone knows about the game "life"? For those who do not know - there is a certain surface, divided into cells. A cell can be in two states: be alive or dead. The cell has eight neighbors. The task of "life" is to model future generations of cells according to the following rules: a dead cell, next to which exactly three living cells, comes to life. A living cell with two or three living neighbors continues to live. If there are less than two neighbors or more than three, then the cell dies, respectively, from loneliness or overpopulation. About the algorithms of modeling "life" can be read, for example, on rsdn.ru. There is a lot of room for optimization, both in terms of data storage and in terms of parallelization.
So, the task of the competition a little more difficult. It is called the " labyrinth of life ." Take the space of the game "life" and put in it the "smart" cell. This "smart" cell can move into the next cell when generations change. Her task is to survive, and at the same time reach a given cell of the playing field. The winner is the one who quickly calculates the shortest path of a smart cell from point to point.
The first task in the category of "advanced level"
Solve a very large puzzle " Masyu ". The essence of the puzzle: white and black circles are located in the cells of a rectangular field, it is necessary to connect the circles with vertical and horizontal lines so that a closed line is obtained. The line should not cross itself, branch or go through one cell twice. There are two additional conditions: the line passing through the cell with a black circle should rotate 90 degrees in it, and the next and previous cells should go straight, you cannot rotate. In the cells with a white circle, on the contrary, it is necessary to go straight through the cell, without changing directions, and rotate 90 degrees in the next OR in the previous cell (that is, at least on one side). The picture below is an example of solving a small Masyu puzzle. Test datasets for obvious reasons will be significantly more. The winner is the one who quickly solves the puzzle.
A detailed description of the competition tasks with examples of source data and requirements for results files, as well as detailed rules and a list of prizes are available on the competition website .
Questions (comments, suggestions) can be asked right here, or in a special forum . Reception of entries ends on a significant day on May 9th .
UPD : corrected picture.
All successful algorithmic finds! And please, don't plan anything important for September - maybe one of you will go to the Intel® Developers Forum.
Source: https://habr.com/ru/post/117998/
All Articles