LINUX.ORG.RU

4
Всего сообщений: 29

асинхронная дефрагментация массива

Например, имеются массивы data[N], hole[M], N≥M. В data хранятся данные, а в hole — в порядке возрастания, индексы, отмечающие пустые точки. Нужно дефрагментировать этот массив, т.е. обменять элементы так что бы данные лежали непрерывно. При этом, порядок в котором они они пишутся не важен. Что-то вроде:

8 holes:
	3 5 6 16 22 23 25 26
in:
	00 01 02 -- 04 -- -- 07 08 09 10 11 12 13 14 15 -- 17 18 19 20 21 -- -- 24 -- -- 27 28 29
out:
	00 01 02 29 04 28 27 07 08 09 10 11 12 13 14 15 24 17 18 19 20 21 -- -- -- -- -- -- -- --
Как называется этот алгоритм и как реализовать его параллельный вариант для произвольного количества тредов?

В наивной последовательной реализации (набросал на python)

id_hole = len(hole)-1
id_tail = len(data)-1
for j in range(0,len(hole)):
	dst = hole[j]
	while(id_hole>=j):
		if hole[id_hole] >= id_tail:
			#skip
			id_tail = id_tail-1 #atomic
			id_hole = id_hole-1 #atomic
		else:
			#move
			data[dst],data[id_tail] = data[id_tail],data[dst]
			id_tail = id_tail-1 #atomic
			break
получается две шаренные переменные, т.е. если параллелить цикл по j, то на каждый шаг будет не менее двух атомарных операций, что нехорошо. Как тут можно переделать?

Предполагается, что с этим будет работать код на CUDA, в пределах одного блока тредов.

 , , , ,

thunar ()

Паралельный доступ к памяти

Имеем два ядра и массив структур. Этот массив хочется обрабатывать параллельно и без блокировок и синхронизаций. Данные меньше размера кеш линии поэтому если передать как есть две структуры будут лежать в одной кеш линии и попадут вместе в L1 каждого из ядер и даже если запись происходит в разные места то будет взаимоблокировка с синхронизацией. Поэтому я увеличиваю размер структур до размера кеш линии теперь каждое ядро загружает в L1 независимые данные и могут их обработать без блокировок. Также и то и то лежит в одном массиве размером со страницу памяти. Что исключает работы ядер с двумя таблицами адресации и переключениями между ними.

Помимо этого я ещё передаю в оба потока указатель на одну и туже структуру но эту структуру потоки будут только читать.

Вопрос - всегда ли данные которые лежат в 1 кеш линии попав в L1 отдельных ядер вызывают процесс синхронизации? Или это происходит только тогда когда данные изменяются? Ну тоесть память помечается как неактуальная и L1 другого ядра вынуждено перезагрузить данные снова. Хотя они уже были.

Я сейчас не говорю про атомарность, мутексы и прочее. Тут дело в том что всё должно быть без этого.

 , , , ,

LINUX-ORG-RU ()

Гонка данных - тонкие тонкости?

Вот есть переменная типа uint64_t в которой лежит какая то чиселка а. Первый поток в нее пишет чиселку b, а второй поток ее этот момент читает. Вопрос - какие именно чиселки может получить второй поток при чтении? Только чиселки a, b или вообще что угодно?

 ,

AntonI ()

параллельная дефрагментация массива?

Пусть есть массив с данными data[n], часть данных помечена как пустые в отсортированном массиве ihole[m], m<n. Например data=[x0,x1,x2,x3], holes[1,3] — т.е. на месте x1 и x3 хранится мусор.

Необходимо дефрагментировать массив data, что бы на место мусора перемещались полезные данные из конца массива, а n-=m. Последовательный алгоритм тривиален:

for i in range(m):
	src = n-i-1
	dst = ihole[m-i-1]
	if src>dst: data[dst] = data[src]
Как проделать это параллельно? Собственно, хочу сделать аналогично функции «gpuppord2l» из https://github.com/UCLA-Plasma-Simulation-Group/PIC-skeleton-codes/blob/962a7..., но в силу своеобразного стиля написания этого кода никак не могу понять как оно работает...

 ,

thunar ()

Cuda(Cudafy)

Задание такое: Нужно реализовать решение ДУ вида a(t)*x'+b(t)*x+c(t) = 0, x(t) = x0 на gpu. Почитав методички, пришла к выводу, что можно использовать метод Рунге-Кутты 4 порядка, но меня смущает тот факт, что этот метод итерационный, соответственно, каждый следующий шаг вычисляется с учетом предыдущего. Может кто-то встречался с подобной задачкой и есть решение или кто-то может что-то подсказать? Help me, please!

 , , , ,

lera ()

Распараллеливание с помощью openmp

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <omp.h>
int fact(int c);
double taylor(double x, int n);
 
int main(int argc, char *argv[]) {
  double x=0;
  int n=0;
  int n_max = 32;
  if (argc != 3) {
  printf("Input three parametrs!\n");
  return 1;
}
  sscanf(argv[1], "%lf", &x);
  sscanf(argv[2], "%d", &n);

 if((n>n_max)||(n<0)) {
 printf("Invalid parameter n, enter n from 0..10\n");
 return 1;
 }
    
 int i; 
 double sum=0 ;
 double t = omp_get_wtime();
 
  #pragma omp parallel for private(i) reduction(+: sum)
   for (i=1; i<=n; i++) {
	  double taylor = pow(x,i)/fact(i);
	  sum+=taylor;
  }
  
  double diff = omp_get_wtime() - t; 
  printf("e^x = %lf\n Time: \t %lf\n", ++sum, diff);
  return 0;
}

int fact(int c) {
   int fact=1;
   int i;
   for (i = 1; i <= c; i++ ) {
      fact *=i;
   }
   return fact;
}

 , , , ,

shonny ()

Как это правильно называется?

есть вполне четкое разграничение между 2-мя противоположными моделями: 1) один процесс выполняется на множестве процессоров и 2) множество процессов выполняется на одном процессоре.

Есть ли четкая устоявшаяся терминология на этот счет?

 ,

filequest ()

OpenMPI: группы, коммуникаторы, широковещание

Задача состоит в широковещательной передаче от чётных процессов своих номеров нечётным процессам. Как я задумал реализацию:

  • Создаю группы вида 1 чётный + все нечётные (0,1,3,5), (2,1,3,5);
  • Создаю для них коммуникаторы;
  • Использую Broadcast в коммуникаторах.

Первые два пункта сделал, вроде бы. На бродкасте застрял. Похоже ранги созданных коммуникаторов не перебираются (rank_in_comm). Да и Invalid root в MPI_Bcast.

#include "mpi.h" 
#include <stdio.h> 
#include <stdlib.h>

int main(int argc, char *argv[]) 
{ 
  int rank, rank_in_comm, size, odd_count, *ranks, msg, i, j; 
  MPI_Status status; 
  MPI_Group world_group, *groups, group;
  MPI_Comm *comms, empty_comm;

  MPI_Init(&argc, &argv); 
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);
  MPI_Comm_group(MPI_COMM_WORLD, &world_group);

  // Odd array for making a group
  for (i = 0; i < size; i++)
    if (i % 2 != 0) odd_count++;
  ranks = (int*)calloc(odd_count + 1, sizeof(int));
  for (i = 1, j = 0; i < size; i += 2, j++) 
  {
    ranks[i - j] = i;
//    printf("%d ", ranks[i - j]);
  }
//  printf("\n");
  
  // Allocating memory for groups & communicators
  groups = (MPI_Group*)calloc(size - odd_count, sizeof(MPI_Group));
  comms = (MPI_Comm*)calloc(size - odd_count + 1, sizeof(MPI_Comm));

  if (rank % 2 == 0)
  {
    ranks[0] = rank;
    printf("Group %d: ", rank);
    for (i = 0; i <= odd_count; i++) 
      printf("%d ", ranks[i]);
    printf("\n");
  
    MPI_Group_incl(world_group, odd_count + 1, ranks, &groups[rank]);
//    if (groups[rank]) printf("+ group\n");
    MPI_Comm_create(MPI_COMM_WORLD, groups[rank], &comms[rank]);
  }
  else MPI_Comm_create(MPI_COMM_WORLD, MPI_GROUP_EMPTY, &empty_comm);
//  if (empty_comm) printf("+ comm\n");
  if (comms[rank])
  {
    MPI_Comm_rank(comms[rank], &rank_in_comm);
    if (rank_in_comm % 2 == 0)
    {
//      printf("%d ",rank_in_comm);
//      printf("%d ",rank);
      msg = rank;
      MPI_Bcast(&msg, 1, MPI_INT, rank, comms[rank]);
      printf("%d sended its rank\n", rank); 
    } 
    else 
    {
      MPI_Bcast(&msg, 1, MPI_INT, msg, comms[rank]); 
      printf("%d received %d\n", rank, msg); 
    }
  }
  //MPI_Comm_free(comms[]);
  //MPI_Group_free(groups[]);
  free(ranks);
  MPI_Finalize(); 
  return 0; 
}

Потом переделал:

  • Создаю группу с нечётными номерами;
  • Добавляю её в коммуникатор;
  • Создаю группу для 1 чётного номера;
  • Объединяю обе группы;
  • Шлю бродкаст внутри коммуникатора.

Но и тут тоже что-то неверно. Invalid communicator в MPI_Bcast.

#include "mpi.h" 
#include <stdio.h> 
#include <stdlib.h>

int main(int argc, char *argv[]) 
{ 
  int rank, rank_in_comm, size, odd_count, *ranks, msg, i, j, single_p[1]; 
  MPI_Group world_group, group, s_group;
  MPI_Comm comm;

  MPI_Init(&argc, &argv); 
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);
  MPI_Comm_group(MPI_COMM_WORLD, &world_group);

  // Odd array for making a group
  for (i = 0; i < size; i++)
    if (i % 2 != 0) odd_count++;
  ranks = (int*)calloc(odd_count, sizeof(int));
  for (i = 1, j = 1; i < size; i += 2, j++) 
  {
    ranks[i - j] = i;
//    printf("%d ", ranks[i - j]);
  }
//  printf("\n");
  

  printf("Process %d odd group: ", rank);
  for (i = 0; i < odd_count; i++) 
    printf("%d ", ranks[i]);
  printf("\n");

  MPI_Group_incl(world_group, odd_count, ranks, &group);
  MPI_Comm_create(MPI_COMM_WORLD, group, &comm);
  if (rank % 2 == 0)
  {
    single_p[1] = rank;
    MPI_Group_incl(world_group, 1, &single_p[1], &s_group);
    MPI_Group_union(s_group, group, &group);
    MPI_Group_size(group, &size);
    printf("Group size: %d\n", size);
    MPI_Group_rank(group, &rank_in_comm);
    int root = rank; printf("Root: %d, Rank in comm: %d\n", root, rank_in_comm);
      if (rank_in_comm % 2 == 0)
      {
        msg = rank;
        MPI_Bcast(&msg, 1, MPI_INT, root, comm);
        printf("%d sended its rank\n", rank_in_comm);
      }
      else
      {
        MPI_Bcast(&msg, 1, MPI_INT, root, comm);
        printf("%d received %d\n", rank_in_comm, msg);
      }
//    MPI_Group_excl(group, 1, &single_p[1], &group);
//    MPI_Comm_free(&comm);
//    MPI_Group_free(&group);
  }
  free(ranks);
  MPI_Finalize(); 
  return 0; 
}

Кто-нибудь может помочь разобраться?

 , , , ,

t0n ()

Ищу литературу по параллельным вычислениям

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

 , ,

IceWindDale ()

Реально ли объединить несколько VPS/VDS в кластер?

Интересует именно объединение вычислительных ресурсов. Или, например, задачу разбивать на потоки и распределять между VPS - насколько это реально?

 ,

letni ()

Выбор задачи для дипломной работы с использованием CUDA

Всем доброго времени суток. Я студент 5 курса (специальность информатика) и следовательно подошло время написания дипломной работы. В качестве области исследований выбрал параллелизм с использованием технологии CUDA. Опыт работы с CUDA был (работал с прямым ходом метода Гаусса). Проблема, собственно, с выбором задачи. Ясное дело, что метод Гаусса для дипломной не катит. Хотелось бы услышать предложения на этот счёт. Нужна актуальная, но не заезжанная тема.

 , ,

maxfirecheetah ()

Вопрос про потоковые редакторы UNIX

Читаю щас про sed учебник здешнего юзера, кстати, emulek'a встретил подозрительный кусок.

Далее sed последовательно читает все три файла, применяя к каждой строке в них sed-скрипт (пустой в данном случае). Результат выводится в выходной поток. Вот тут действие sed заканчивается, и опять начинает работать оболочка, последовательно записывая весь вывод в файл all.html. Потому код cat примитивен (пара строк на C), она просто читает входные файлы и выводит их в выходной поток, без всякой обработки, поисков и слияний. (Правда cat ещё и может нумеровать строки с ключом -n)

http://emulek.github.io/sed/ch01s02.html

Я, почему-то всегда думал, что выполнение происходит параллельно, или, как минимум, построчно. Типа, каждая строка передается по конвейру, а не буферы, куски etc. Может автор чуток ошибся? Или я что-то путаю?

 , , ,

quest2017 ()

элементы конструкции, время и распараллеливание

Есть некоторое объемное тело, составленное из некоторого количества частей (т.е. присутствуют поверхности по которым эти части соединяются), на которое действует динамическая нагрузка по некоторому сложному закону, зависящему от предыдущего состояния всей системы. Задача стоит в вычислении величины деформации тела с учетом резонансных частот всех его частей и жесткости соединений. Как параллелить будем если каждая единица объема зависит от смежных по множеству динамических параметров?

Мне не очень ясно, в чем проблема с распараллеливанием таких вычислений. Делаем так:
1) берем состояние в момент времени T1
2) вычисляем (параллельно для каждой части) состояние в момент времени T2 (основываясь на параметрах соседних частей в момент времени T1)
3) повторяем процесс, уменьшаем T2-T1 для увеличения точности

 ,

BarCat ()

Что полезно почитать новичку по параллелеизму?

Хотелось бы что-то в духе теории акторов, но с простым изложением. Карл Хьюит крут, но, непосредственно его, читать пока трудновато, не дорос еще видимо:) (Хотя пытаюсь):)

 

terminator-101 ()

Вопрос по архитектуре: одопоточность vs треды vs another_stuff

Асинхронность JS, имхо, являтся половинчатым решнием. Если я правильно понимаю, она избавляет нас только от одного — от бесполезного простоя машины: машина не ждет, когда закончится блокирующая операция, она все время занята. Однако, это не избавляет от ожидания самого пользователя: если машина занята, она блокирует единственный поток, и не реагирует на события своевременно (ставит их в очередь).

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

Такая архитктура, мне кажется, самоочевидна. Это напоминает модель акторов, вроде. Однако, я не вижу, чтобы это активно применялось. Почему?

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

Собственно вопрос: почему так называемые «архитекторы» не пошли по простому и очевидному пути? Тут снова мы сталкивамся с математикой головного мозга компьютер-сайентологов, которые думали, что волшебные лямбды избавят их от проблем масштабируемости, или это просто тупость?

 

anonimous ()

Вопрос про многопоточность

Лисп тут собственно, не при чем, просто пример на лиспе, а в вопросе важна реализация. Я не уверен, что в других ЯП также все реализовано.

Я не знаю низкий уровень, к сожалению, поэтому возникает путаница, по вопросам реализации.

Допустим, есть вот такой вот кодик

(define function (lambda() 'some-code))
(define foo function)
(define bar function)
В данном коде все 3 имени указывают на одну и ту же структуру в памяти. Собственно, при вызове любого имени, function, foo или bar, будет выполняться один и тот же код, физически.

Вопрос следующий. Допустим у нас 2 потока на 2-х разных процессорах. Можно ли, чисто физически, одновременно из этих 2-х процессов одновременно дернуть функцию function, например, через разные имена, допустим,из одного потока по foo, а из другого по bar? Чтобы оба вызова были действительно одновременны в реальном времени. Если у нас конкурентность, понятно, что это можно сделать, поскольку, у нас в риал-тайм происходит либо один либо другой вызов. А вот если будет реальная параллельность? Это же невозможно, или как?

 , ,

phill ()

Ъ-параллелизм vs конкурентность

Я тут неоднократно слышал от лоровских экспертов, что нельзя разделять эти два понятия, надо абстрагироваться от этого различия. Я вот только одной вещи не пойму. Допустим, есть некий a&&b. Если у нас Ъ, может ли данное выражение быть признано корректным? Ведь к моменту выполнения b, а может уже быть переопределено из другого потока? Я так понимаю, при конкурентности такого быть не может?

 

phill ()

Вздумалось взглянуть, как xz жмёт на восьми ядрах.

В качестве жертвы выбран профиль огнелиса. Размер ниже, содержимое - в основном scrapbook. В нижнем блоке, для сравнения, та же операция в один поток.

> /home/cache> sz .mozilla/
5,5G	.mozilla/
> /usr/bin/time tar cSf - .mozilla | xz -z9c -T8 > mozilla-20121214.txz
1.78user 7.67system 7:06.35elapsed 2%CPU (0avgtext+0avgdata 6560maxresident)k
7159736inputs+0outputs (0major+25774minor)pagefaults 0swaps
> /usr/bin/time tar cSf - .mozilla | xz -z9c -T1 > mozilla-20121214_.txz
6.86user 23.54system 39:37.56elapsed 1%CPU (0avgtext+0avgdata 6560maxresident)k
4794360inputs+0outputs (3major+25781minor)pagefaults 0swaps

 , ,

cache ()

Асинхронный фреймворк по типу AnyEvent для PHP

Нужно помочь товарищу переделать сервер-сайд утилиту работающию с сетью с блокируемого(непараллельного режима) на асинхронный(параллельный ) режим.
Очень неплохой фреймворк AnyEvent, который мог бы решить эту задачу не подходит в виду того, что там проект очень завязан на php.

Так что подскажите рабочие фреймворки под это дело на php ?

P.S Господа об решение проблемы с помощью форков,осведомлен,но хочется именно по нормальному сделать

 , ,

pinachet ()

Нужны кружки, экскурсии или что-то вроде.

Есть брат, хочется организовать ему какое-то мероприятие, чтобы посмотрел на перспективное направление и послушал умных людей. Тут есть люди, которые иногда предлагают сходить и чему-то поучиться, например, tazhate.

Вопрос: существует ли тут пересечение моих интересов и существующих предложений?

Линукс при том, что на кластеры нормальные люди другое не ставят.

 ,

pianolender ()