WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 24 |

Литература 1. Деменев А.Г. Параллельные вычислительные системы: основы программирования и компьютерного моделирования. Учебное пособие к спецкурсу. Пермь: ПГПУ, 2001. 59 с.+Прил. (6 с.) 2. Lester Bruce P., The Art of Parallel Programming/ Prentice Hall, Englewood Cliffs, NJ 07632, 1993.

3. Программирование на параллельных вычислительных системах/ Пер. с англ. под ред. Р. Бэбба. М.: Мир, 1991. 320 с.

МОДЕЛИРОВАНИЕ ДИНАМИКИ СЛОЖНЫХ КВАНТОВЫХ СИСТЕМ В.Я. Демиховский, А.И. Малышев Нижегородский государственный университет им. Н.И. Лобачевского В последнее время внимание физиков и математиков обращено на исследование сложных (многомерных) квантовых систем. Этот интерес связан, в частности, с изучением эволюции состояний большого числа кубитов, составляющих основу квантового компьютера.

Как известно, при описании динамики N классических частиц объем вычислений (число дифференциальных уравнений первого порядка) растет пропорционально их числу. В то же время, как отмечено в известной работе Р.Фейнмана [1], объем вычислений при расчете совместной эволюции ансамбля N квантовых частиц растет экспоненциально с ростом N. Так, для моделирования поведения N двухуровневых квантовых систем (кубитов) необходимо решать одновременно 2N дифференциальных уравнений. Определение стационарных квантовых состояний в такой системе требует диагонализации матрицы размером 2N2N. Ясно, что в такой ситуации возможности классических алгоритмов вычислений жестко ограничены.

Аналогичные проблемы возникают уже при исследовании динамики одной квантовой частицы, находящейся во внешнем поле, зависящем от нескольких переменных (например, U(x, y, z, t)). Если представить волновую функцию такой системы в виде ряда по M функциям невозмущенного базиса n (x), m (y), l (z), то число коэффициентов этого разложения Cn, l, m(t), очевидно, составит M3. При разумном выборе M (порядка 100), число решаемых уравнений стремится к миллиону.

Приведены конкретные примеры расчетов динамики квантовых систем:

а) квантовая диффузия Арнольда на примере двух взаимодействующих нелинейных осцилляторов, находящихся во внешнем периодическом поле [2];

б) эволюция двухуровневых взаимодействующих квантовых систем (кубитов) [3].

Литература 1. R.P. Feynman // Int. J. Theor. Phys., 21, 467, 1982.

2. V.Ya. Demikhovskii, F.M. Izrailev and A.I. Malyshev // Int. Conf.

«Progress In Nonlinear Science», N. Novgorod, 2001.

3. G.P. Berman et.al., quant-ph/0110069 v1. (To be published in Phys.

Rev. E), 2001.

РЕАЛИЗАЦИЯ АЛГОРИТМОВ МОДУЛЬНОЙ АРИФМЕТИКИ В КЛАСТЕРНЫХ СИСТЕМАХ М.С. Дрейбанд Нижегородский государственный технический университет, Институт прикладной физики РАН Введение В связи с использованием вычислительных кластеров возникает большое число вопросов, связанных с оптимальным использованием их ресурсов. При создании параллельных программ возникают следующие проблемы:

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

• Сложность создания и отладки параллельных алгоритмов.

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

• Далеко не все программные и аппаратные платформы, обеспечивающие параллельные вычисления, совместимы друг с другом.

Снять эти проблемы позволяют библиотеки, реализующие «скрытый» параллелизм вычислений базовых арифметических операций.

При создании такой библиотеки был использован следующий подход: все операции над числами выполняются в «модульном представлении». Целое число представляют вычетами по модулям из множества взаимно-простых чисел pi. Если p1,… pk-1 – попарно взаимно простые числа и p=p1*…* pk-1, то любое целое число u от 0 до p можно однозначно представить множеством его вычетов u1,… uk-1, где ui=u(mod pi). Сложение, вычитание и умножение легко выполняются, если эти вычисления рассматривать как операции, определенные в поле классов вычетов по модулям pi.

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

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

Реализация библиотеки Библиотека, реализующая модульные вычисления, написана на языке C с использованием функций библиотеки MPI.

Все числа представляются в виде переменных типа long, т.е. 64 бита на платформе Intel. Модульное представление чисел записывается в виде массива с элементами типа long.

Все библиотечные функции можно условно разбить на несколько групп:

• Функции преобразования чисел – переводят число из полиномиального (десятичного) представления в модульное, и наоборот.

Необходимо обратить внимание, что функция преобразования числа из модельного представления в десятичное требует «синхронизации» всех компьютеров, т.е. перехода независимо выполняющихся программ в одну точку алгоритма.

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

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



Показатели эффективности и ускорения Тестирование программ, написанных с использованием библиотеки модульной арифметики, проводилось в двух системах: вычислительном кластере на базе серверов Compaq, принадлежащем ИПФ РАН (5 узлов Compaq Server DS E20, по 2 процессора Alpha 21264 667MHz), и в учебном классе НГТУ (10 компьютеров Pentium 166).

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

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ИДЕНТИФИКАЦИИ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ НА РЕШЕТКЕ Н.Ю. Золотых Нижегородский государственный университет им. Н.И.Лобачевского Рассматриваются параллельные алгоритмы идентификации геометрических объектов, заданных на целочисленной решетке. Произвольное подмножество c точек n-мерного k-значного гиперкуба Ekn={0,1,..., k - 1}n, где n 2, k 2, назовем объектом. Произвольное семейство C таких подмножеств назовем классом объектов. Одна из задач точного машинного обучения (machine learning) заключается в идентификации объекта c из заданного класса C с помощью вопросов оракулу вида `x c', где x – точка, произвольно выбираемая из Ekn.

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

Для идентификации используется машина UPRAM с p процессорами [2]. За один шаг на такой машине возможно параллельное обращение к оракулу в p точках.

Обозначим через HALFSPACEkn множество объектов c, для каждого из которых найдутся действительные числа a0, a1,..., an, такие, что n n c = {x Ek : a x a0}. (1) j j j=Теорема 1 [3, 4] Существует алгоритм A1, который по произвольному объекту c HALFSPACEk2, используя не более 6 log (k–1)+обращений к оракулу и O(log k) арифметических операций, на машине UPRAM с одним процессором определяет коэффициенты неравенства, при которых выполняется (1).

Теорема 2 Существует алгоритм A2, который по произвольному объекту c HALFSPACEk2, используя не более 3 log (k-1)+2 обращений к оракулу и O(log k) арифметических операций, на машине UPRAM с 2 процессорами определяет коэффициенты неравенства, при которых выполняется (1).

Теорема 3 Существует алгоритм A3, который по произвольному объекту c HALFSPACEk2, используя не более log (k-1)+1 обращений к оракулу и O(log k) арифметических операций, на машине UPRAM с процессорами определяет коэффициенты неравенства, при которых выполняется (1).

Теорема 4 Существует алгоритм A4, который по произвольному объекту c HALFSPACEk2, используя не более 6 log (k-1)+4 обращений к оракулу и O(log k) арифметических операций, на машине UPRAM с k процессорами определяет коэффициенты неравенства, при которых выполняется (1).

Результаты, относящиеся к идентификации объектов из класса HALFSPACEkn для n > 2, см. в [5, 6, 7].

Обозначим через m-HALFSPACEk2 множество объектов c Ek2, для каждого из которых найдутся действительные числа a10, a11, a12,..., am0, am1, am2, такие, что c = {x Ekn: a11x1 + a12 x2 a10,..., am1 x1 + am2 x2 am0}. (2) Теорема 5 [8] Существует алгоритм A5, который по произвольному объекту c m-HALFSPACEk2 и произвольной тройке неколлинеарных точек из c, используя не более (10m + 1) log (k-1) + 34 вопросов и O(log k) арифметических операций, на машине UPRAM с 1 процессором определяет коэффициенты a10, a11, a12,..., am0, am1, am2, при которых выполняется равенство (2).

Теорема 6 Существует алгоритм A6, который по произвольному объекту c m-HALFSPACEk2 и произвольной тройке неколлинеарных точек из c, используя не более (11m+1) log (k-1)+12 вопросов и O(log k) арифметических операций, на машине UPRAM с m процессорами определяет коэффициенты a10, a11, a12,..., am0, am1, am2, при которых выполняется равенство (2).

Обозначим через BOXkn множество объектов c Ekn, для каждого из которых найдутся числа a1,..., an и b1,..., bn, такие, что c = {x Ekn: a1 x1 b1,..., an xn bn }. (3) Теорема 7 Существует алгоритм A7, который по произвольному объекту c BOXkn и произвольной точке x c, используя не более 2n log (k-1) вопросов и O(n log k) арифметических операций, на машине UPRAM с 1 процессором находит числа a1,..., an и b1,..., bn, при которых выполняется равенство (3).

Теорема 8 Существует алгоритм A8, который по произвольному объекту c BOXkn и произвольной точке x c, используя не более log (k-1) вопросов и O(n log k) арифметических операций, на машине UPRAM с 2n процессорами находит числа a1,..., an и b1,..., bn, при которых выполняется равенство (3).

Обозначим через BALLkn множество объектов c Ekn, для каждого из которых найдутся точка y Ekn и целое число r, такие, что n n c = {x Ek : (x - y )2 r}.. (3) j j j=Теорема 9 [8] Существует алгоритм A9, который по произвольному объекту c BALLkn и произвольной точке x c, используя O(n log k) вопросов, находит y и r, при которых выполняется равенство (4).

Часть результатов для случая n = 2 сведем в таблицу:

Число проКласс Сложность алгоритма цессоров 1 6 log(k-1) + 2 3 log(k-1) + 4 2 log(k-1) + HALFPLANEk k log(k-1) + k k2 1 (10m + 1) log (k-1)+m-HALFPLANEkm 11 log(k-1)+1 4 log(k-1) - 2 2 log(k-1) - BOXk4 log(k-1) - k BALLkn 1 O(log k) Литература 1. Шевченко В. Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. 192 с.





2. Bshouty N.H., Cleve R. On the exact learning of formulas in parallel // Proc. of the 33rd Symposium on the Foundations of Comp. Sci. IEEE Computer Society Press, Los Alamitos, CA, 1992. P. 513–522.

3. Золотых Н. Ю. Пороговые функции, зависящие от двух переменных: сложность расшифровки и мощность разрешающего множества // Материалы четвертой молодежной научной школы по дискретной математике и ее приложениям. М.: Изд-во механикоматематического факультета МГУ, 2000. С. 48–54.

4. Веселов С. И. Расшифровка одного класса функций // Материалы XI Межгосударственной школы-семинара ``Синтез и сложность управляющих систем''. Часть I. М.: Изд-во центра прикладных исследований при механико-математическом факультета МГУ, 2001.

С. 39–40.

5. Шевченко В.Н., Золотых Н.Ю. О сложности расшифровки пороговых функций k-значной логики // Доклады Академии наук. 1998.

Т. 362, 5. C. 606–608.

6. Золотых Н.Ю., Шевченко В.Н. О нижней оценке сложности расшифровки пороговых функций k-значной логики // Журнал вычислительной математики и математической физики. 1999. Т. 39, 2.

С. 346–352.

7. Shevchenko V.N., Zolotykh N.Y. Lower bounds for the complexity of learning half-spaces with membership queries // Proc. of the 9th International Conference on Algorithmic Learning Theory – ALT'98. V.

1501 Lecture Notes in Artificial Intelligence, Springer-Verlag, 1998, P.

61–71.

8. Веселов С. И., Золотых Н. Ю. Идентификация геометрических образов на целочисленной решетке // Материалы 7-ой международной конференции по дискретной математике и ее приложениям. В печати.

ОРГАНИЗАЦИЯ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА КЛАСТЕРЕ PARC УДМУРТСКОГО ГОСУНИВЕРСИТЕТА Г.Г. Исламов, С.А. Мельчуков, М.А. Клочков, О.В. Бабич, Д.А. Сивков Удмуртский государственный университет, г.Ижевск С момента появления в 1971 году первого микропроцессора iфирмы Intel и создания на его основе микропроцессорных вычислительных устройств развитие вычислительной техники сделало гигантский скачок. Основной прирост вычислительной мощности компьютеров достигался как за счет улучшения технологических норм производства (и, как следствие, тактовых частот), так и за счет улучшения архитектурной организации микропроцессоров и периферийных устройств. При этом, начиная с начальных тактовых частот порядка КГц микропроцессора i4004, микропроцессоры достигли тактовых частот в 1700–2000 МГц. Однако, дальнейшее увеличение производительности за счет повышения тактовых частот становится несколько затруднительным, так как практически достигнуты минимальные размеры транзисторов на кристалле и появились другие сдерживающие факторы. Поэтому современная вычислительная техника все более отходит от традиционной архитектуры и создаются новые направления повышения производительности вычислительных систем.

Достигнутый уровень технологии производства надежных высокоскоростных шин и мощных процессоров, сетевого оборудования и развитое программное обеспечение распределенных и параллельных вычислений позволяют создавать кластеры высокопроизводительных компьютеров, способные обеспечить эффективные расчеты широкого класса научных и технических задач, а также планомерную подготовку специалистов в области высокопроизводительных вычислений. В ноябре 2000 г. по инициативе ректора Удмуртского госуниверситета профессора В. А. Журавлева был создан кластер PARC, состоящий из пяти двухпроцессорных компьютеров. Общая характеристика этому кластеру дана в учебно-методическом пособии [1], описывающем основные особенности и правила работы на кластере PARC.

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

Рассмотрим в течение времени T процесс изменения температуры u(x,t) в тонком стержне длины l с коэффициентом теплопроводности k(x) при воздействии на него тепловыми источниками и стоками плотности F(x,t)=b(x)v(t) в точке x [0,l] в момент t[0,T]. Известно, что температура u(x,t) должна удовлетворять дифференциальному уравнению теплопроводности u(x,t) u(x,t) k(x) c(x) = + b(x)v(t), (x,t) (0,l) (0,T ). (1) t x x Здесь c – удельная теплоемкость, (x) – функция плотности распределения массы стержня.

С помощью двух функций (x,t) и (x,t) ( (x,t) (x,t)) зададим диапазон изменения температуры (x,t) u(x,t) (x,t). (2) Задачу управления поставим следующим образом. Требуется построить такое кусочно-постоянное управление v=v(t) (|v(t)| 1, t [0,T ]), при котором уравнение (1) имеет гладкое решение u(x,t), удовлетворяющее граничным условиям u(0,t) = µ(t), u(l,t) = v(t) и дополнительному ограничению (2) в каждый фиксированный момент времени t = ti (0 t1 < t2 <...

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

u(x1,t) 1 u(x2,t) - u(x1,t) u(x1,t) - u(0,t) a c(x1) = - a1 + b(x1)v(t), t h h h u(xi, t) u(xi+1, t) - u(xi, t) u(xi, t) - u(xi-1, t) c(xi ) = ai+1 - ai + t h h h + b(xi )v(t), i = 2,....N - 2, u(xN -1, t) c(xN -1) = t u(l, t) - u(xN -1, t) u(xN -1, t) - u(xN -2, t) aN - aN -1 + b(xN -1)v(t), h h h граничные условия для которой имеют следующий вид:

(xi, tj) u(xi, tj) (xi, tj), j = 1,…m, i = 1,…N–Для описания свойств требуемого управления данной конечномерной задачи сформулирован принцип максимума, позволяющий определить точки переключения.

Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 24 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.