Найти

Результаты поиска

• ПРЕОБРАЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНОГО ИНФОРМАЦИОННОГО ГРАФА МЕТОДА ПРОГОНКИ В ПАРАЛЛЕЛЬНУЮ ФОРМУ

  Д. В. Михайлов

  177-188

  2021-10-05

  Аннотация ▼

  Множество вычислительных задач может быть представлено в виде последова-тельного информационного графа. В общем случае такой информационный граф не может быть приведён к параллельному виду с целью ускорения выполнения его операций. Но в слу-чае если вершины этого графа обладают свойствами ассоциативности, дистрибутивно-сти и т.д., такой граф можно преобразовать в параллельно-конвейерную форму. Эти пре-образования могут быть произведены не только над графами, содержащими элементар-ные операции – сложение, умножение, логическое И и т.д. – но и над графами, содержа-щими макрооперации. Одним из примеров таких графов является информационный граф решения СЛАУ методом прогонки (методом Томаса). В статье рассмотрено решение для трёхдиагональных СЛАУ. Информационный граф метода прогонки состоит из двух час-тей: прямого хода, в котором выполняется переход от трёхдиагональной формы к двух-диагональной, и обратного хода, в котором непосредственно вычисляются значения неиз-вестных. Несмотря на то, что операции, составляющие базовую макрооперацию метода прогонки, обладают свойством ассоциативности, простое преобразование графа к пира-мидальному виду не даст необходимого результата. Необходимо преобразовать базовые макрооперации особым образом и изменить то, какие данные на них поступают. После этого возможно будет привести граф к пирамидальному виду. Для обратного хода приме-няется аналогичное преобразование графа и составляющих его базовых подграфов. По-скольку для того, чтобы начать вычисления в обратном ходе, нам необходимо полное за-вершение вычислений прямого хода, следует перейти от двух специализированных типов вычислительных блоков к одному универсальному, и построить на его основе универсаль-ную вычислительную структуру.

• МЕТОД РЕШЕНИЯ ГРАФОВЫХ NP-ПОЛНЫХ ЗАДАЧ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ ПРИНЦИПА РАСПАРАЛЛЕЛИВАНИЯ ПО ИТЕРАЦИЯМ

  А. В. Касаркин

  2021-02-25

  Аннотация ▼

  При решении графовых NP-полных задач на многопроцессорных системах рост обо-
  рудования не приводит к пропорциональному росту производительности системы, поэто-
  му не всегда удается решить задачу за приемлемое время. Целью работы, описанной в
  статье, является минимизация времени решения задачи поиска максимальных клик графа с
  использованием реконфигурируемых вычислительных систем (РВС). При решении задачи
  на РВС методом распараллеливания по слоям рост производительности также замедля-
  ется, несмотря на лучшую степень масштабируемости по сравнению с многопроцессор-
  ными реализациями. В статье предложен метод создания параллельно-конвейерных про-
  грамм для реконфигурируемых вычислительных систем на основе распараллеливания по
  итерациям для решения графовых NP-полных задач. Рассмотрено, что использовать би-
  товый способ представления множеств (как в методе распараллеливания по слоям) для
  метода распараллеливания по итерациям не является эффективным. Новый метод отли-
  чается организацией вычислений, а именно – обработкой неупорядоченных множеств,
  доступ к элементам которых осуществляется не по адресам (как в массивах), а по значе-
  ниям (именам вершин и именам дуг графа). Показано, что новый метод на основе распа-
  раллеливания по итерациям, несмотря на более низкую удельную производительность, свя-
  занную с тем, что вычислительным подструктурам из-за символьного представления
  множеств необходимо обработать большее число промежуточных данных, обеспечивает
  практически линейный рост реальной производительности РВС при значительно большем
  количестве вычислительного ресурса по сравнению с методом распараллеливания по слоям.