713 Тем для обсуждения

6,530 Открытых обсуждений

Китайское искусство программирования

yuryserdyuk (10 пост(а)) 29.07.2009 15:23

Те, кто интересовался Intel Threading Challenge 2007-2008 и Intel Threading Challenge 2009 , наверно, заметили активное участие в них и, самое главное, отличные результаты программистов из Китая. Регулярно борются они за первые места и на чемпионатах мира по программированию (ACM ICPC). Причем, теперь уже по моим личным наблюдениям, с ними совершенно невозможно соперничать в классических задачах программирования, таких как, например, сортировки, поиск и др. Однако, кроме великолепного знания методов решения стандартных задач, не откажешь им и в креативности. Вот показательный пример на эту тему …

Наверняка, всем хорошо известна задача о расстановке ферзей на шахматной доске таким образом, чтобы они взаимно не били друг друга. Суть задачи, а точнее, ее обобщения состоит в том, чтобы подсчитать количество всех возможных таких расстановок на доске размером N x N (NQueens Problem). Удивительно то, что хотя самой задаче уже около 150 лет, но существенный прорыв в ее решении произошел совсем недавно, в 2002 г. (а еще один прорыв состоялся в июле 2009г., но об этом позже).

(Прежде чем читать дальше, тем, кто никогда не пробовал самостоятельно запрограммировать решение этой задачи, настоятельно рекомендуется попытаться сделать собственную реализацию.)

И автором этого прорыва, как вы уже, наверно, догадались, стал человек из Китая по имени Qiu Zongyan из Пекинского университета (его статья помещена в журнале ACM SIGPLAN Notices).

Поскольку алгоритм решения задачи представляет собой, в сущности, полный перебор, то, чтобы сделать его максимально быстрым, нужно эффективным образом организовать структуры данных, отображающие текущую конфигурацию ферзей на доске с тем, чтобы потратить минимальное число операций на переход к следующей конфигурации.

Суть гениального по своей простоте приема, предложенного Qiu Zongyan, проиллюстрируем на примере.

Предположим, что в алгоритме ферзи выставляются на доску по порядку, начиная с самой верхней горизонтали. Например, после расстановки двух первых ферзей мы можем иметь следующую конфигурацию на двух первых горизонталях доски 8 x 8:

	0	0	Ф	0	0	0	0	0
	0	0	0	0	0	Ф	0	0

Теперь, чтобы вычислить допустимые позиции на третьей горизонтали, нам нужно определить какие из позиций на этой горизонтали находятся под боем ранее выставленных ферзей; а именно, какие позиции принадлежат

1) диагоналям, по которым выставленные ферзи бьют справа-налево,

2) вертикалям, по которым ферзи бьют сверху-вниз,

3) диагоналям, по которым ферзи бьют слева-направо.

Представим эти позиции, находящиеся под боем (отметив их единичками) в виде соответствующих трех битовых векторов:

left:	1	0	0	0	1	0	0	0
down:	0	0	1	0	0	1	0	0
right:	0	0	0	0	1	0	1	0

Поэлементно складываем все эти вектора логически по ИЛИ и получаем занятые/свободные позиции на третьей горизонтали:

1

0

1

0

1

1

1

0

Итак, у нас имеется 3 возможных способа поставить очередного ферзя. Выбираем, например, вторую позицию слева и ставим туда третьего ферзя.

А теперь – внимание ! – ключевой момент алгоритма. Как нам получить новую конфигурацию доски, а именно, занятые позиции теперь уже на четвертой горизонтали? А делаем всего лишь вот что − ставим единицу во вторую позицию (т.е., позицию, куда мы поставили нового ферзя) каждого из векторов left, down и right, и

a) сдвигаем вектор left влево на 1 бит (вычисляем позиции под боем на диагоналях, идущих от уже поставленных ферзей справа-налево),

б) ничего не делаем с down,

в) сдвигаем вектор right вправо на 1 бит (аналогично пункту а, но для диагоналей слева-направо).

Суммируем чего мы добились − мы представили конфигурации ферзей на доске в виде битовых векторов, а их модификацию выразили исключительно через битовые операции.

Остальная часть алгоритма − это обычный бектрекинг с целью получения всех возможных расстановок. Полное решение этой задачи на языке C# представлено ниже.

using System;
public class NQueens   {
 public static int Backtrack(int y, int left, int down,
 int right, int N, int MASK)
 {
     int  bitmap, bit;
     int  count = 0;
     if (y == N) {
         return ( 1 );
     } else {
         bitmap = MASK & ~(left | down | right);
         while (bitmap != 0) {
             bit = -bitmap & bitmap;
             bitmap ^= bit;
             count += Backtrack(y+1,(left | bit)<<1, down | bit,
             (right | bit)>>1, N, MASK);
         }
         return ( count );
     }
 }
 public static void Main(String[] args )
 {
     int N    = Convert.ToInt32 ( args [ 0 ] );
     int MASK = (1 << N) - 1;
     int result = Backtrack(0, 0, 0, 0, N, MASK);
     Console.WriteLine ("N=" + N + " -> " + result);
 }
}

Схема параллелизации этого алгоритма не так интересна − она очевидна, и, похоже, единственна. О ней и о сопутствующих результатах, я надеюсь, мы поговорим в планирующемся продолжении этого поста. А пока лишь упомяну, что детальное описание приведенного выше алгоритма вместе со схемой параллелизации на языке MC# можно будет вскоре найти в учебном курсе “Параллельное программирование для многоядерных процессоров”, который будет размещен на сайте Интернет-университета информационных технологий и на сайте Microsoft MSDN Academic Alliance . Варианты решения этой же задачи с использованием OpenMP и Intel TBB можно найти в документе “Parallelizing N-Queens with the Intel Parallel Composer” , а с использованием Cilk++ - здесь.

В заключении, по традиции две загадки − как вы думаете, что это такое?

1)

  int t(int a, int b, int c){
     int d=0, e=a&~b&~c, f=1;
     if (a)
       for (f=0; d=(e-=d)&-e;)
         f+=t(a-d,(b+d)*2,(c+d)/2);
     return f;
  }
  int main( int argc, char *argv[]) {
    int q = atoi ( argv [ 1 ] );
    printf("%d\n",t(~(~0<<q),0,0));
  }
  

2)

Ответы − в следующем посте.

Категории: Intel Software Network, Параллельное программирование, Разработка софта

Пожалуйста, обратитесь к странице Уведомление об оптимизации для более подробной информации относительно производительности и оптимизации в программных продуктах компании Intel.

Комментарии (13)

Обратная ссылка (2)

• Блоги Intel® Software Network » Китайское искусство программирования 2, или 9,58 vs 22,317,699,616,364,044
  05.09.2009 02:57
• Блоги Intel® Software Network » Суров закон параллелизма, или «что за #@%&^ этот ваш параллелизм?»
  11.12.2009 04:31

Оставить комментарий  

Имя (обязательно)*

Электронная почта (обязательно; не будет отображено на этой странице)*

Ваш URL-адрес (необязательно)


Комментарий*