Информационная система "Конференции"


Международная конференция молодых ученых по математическому моделированию и информационным технологиям

29-31 октября 2002 года, Новосибирск, Академгородок

Тезисы докладов

Вычислительная математика и математическое моделирование

Распараллеливание по потоку данных задачи с полиномиальной алгоритмической сложностью решения

Нефедов В.С.

Новосибирский государственный технический университет (Новосибирск)

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

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

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

Формализовав задачу и применив методы математического анализа и аддитивной теории чисел, было найдено оптимальное решение поставленной задачи.

В результате проведенного исследования:

  1. найдено решение поставленной задачи;
  2. введена терминология;
  3. определены ограничения на размер секции и количество потоков;
  4. получена схема распределения точек входного массива между потоками.

    Литература

    1. Нефедов В.С. Разработка алгоритма распараллеливания задачи восстановления акустической жесткости среды. Труды конференции "Молодых специалистов". Сборник докладов.

    2. Нефедов В.С. Разработка параллельного алгоритма расчета акустической жесткости среды. Труды конференции "Информационные системы и технологии". Сборник докладов.

    Примечание. Тезисы докладов публикуются в авторской редакции

    Ваши комментарии
    Обратная связь
    		[ICT SBRAS]
    [Головная страница]
    [Конференции]

    © 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
    © 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
        Дата последней модификации: 06-Jul-2012 (11:47:01)