Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 22
Текст из файла (страница 22)
ЗаключениеПогрешность прогнозирования времени выполнения модельныхпрограмм для кластерных систем построенных на базе различныхплатформ и использующих различные коммуникационные подсистемы, не превышала 10%, время прогноза – нескольких минут. Это по108зволяет говорить о применимости подхода.В настоящее время среда ParJava используется: в Тамбовском государственном университете для разработки пакета символьночисленного решения задач линейной алгебры; в отделе систем моделирования ИСП РАН для разработки генетических алгоритмов для автономных адаптивных систем управления; в Институте физики ЗемлиРАН для моделирования процесса зарождения торнадо.
Разработкаэтих пакетов позволит получить более точные оценки и уточнить направление развития среды.Дальнейшее развитие среды ParJava связано с расширением области применения моделей. Будут разработаны новые инструменты: анализаторы параллельных трасс с целью выявления узких мест, взаимоблокировок и др.; анализаторы параллельной структуры программы сцелью выявления скрытого параллелизма как в циклах, так и в ациклических участках программы; преобразователи последовательных циклов в параллельные и др.
Все эти инструменты будут выполняться наинструментальном компьютере, используя подходящие модели.Литература1. Report of the President’s Information Technology Advisory Committee(PITAC) to the President on Computational Science: Ensuring America's Competitiveness. http://www.nitrd.gov/pitac/reports/.2. Национальная целевая программа DARPA.
High Productivity Computing Systems (HPCS), http://www.highproductivity.org/.3. Ivannikov V., Gaissaryan S., Avetisyan A., Padaryan V. Improving properties of a parallel program in ParJava Environment // EuroPVM/MPI, 2003,LNCS. V. 2840. P. 491–494.4. Culler David E., Liu Lok T., Martin Richard P., Yoshikaw Chad. LogPPerformance Assessment of Fast Network Interfaces. // IEEE Micro, February,1996.ОБ ОДНОМ МЕТОДЕ ПОИСКА БАЗИСНОГО МИНОРАМАТРИЦЫГ.Г. Исламов, Ю.В.
Коган, Д.А. Сивков,О.В. Бабич, С.А. Мельчуков, М.А. КлочковУдмуртский государственный университетВ пособии [1] при формировании новой симплекс-таблицы былииспользованы некоторые формулы преобразования элементов текущейсимплекс-таблицы. Важность этих формул состоит в том, что на их109основе удается сформулировать и обосновать метод поиска базисногоминора матрицы, который позволяет одновременно вычислить рангматрицы, значение базисного минора, обратную матрицу для матрицыбазисного минора, координаты небазисных строк и столбцов, крайниеточки и экстремальные направления многогранных множеств, а такжеответить на вопросы совместности системы линейных неравенств, положительной определенности симметрических матриц, устойчивостимногочленов с вещественными коэффициентами и др.Метод заключается в построении последовательности матрицA0 = A, …, Ak, Ak+1, …, Ar,(1)где Ak+1 получается пут ем простого преобразования элементов предыдущей матрицы Ak = (aij( k ) ) im=1.
j =1. В текущей матрице Ak есть запрещенные строки и запрещенные столбцы, остальные строки и столбцыэтой матрицы называются разрешtнными. В матрице A0 = A все строкии столбцы разрешенные. Для перехода от Ak к следующей матрице Ak+1последовательности (1) в разрешенных строках и столбцах матрицы Akвозьмем произвольный ненулевой элемент aµ( kk ν) k (называемый разрешающим элементом шага k). Если такого элемента нет, то есть нет разрешенных строк и столбцов, либо все элементы в разреш енных строках и столбцах матрицы Ak – нули, то последовательность (1) завершается матрицей Ak : r = k . Пусть строка µk и столбец νk – разрешенные,то формируем элементы матрицы Ak+1 по следующему простому правилуесли i = µ k , j = ν k ;⎧ 1,⎪ a (k ) ,если i = µ k , j ≠ ν k ;⎪ ijaij( k ) = a( k1) ⎨(k )если i ≠ µ k , j = ν k ;µk νk⎪ − aij ,(k )(k )(k )(k )⎪ aij ⋅ aµ ν − aµ j ⋅ aiν , если i ≠ µ k , j ≠ ν k .k kkk⎩Список запрещенных строк и столбцов матрицы Ak+1 получается изсписка запрещ енных строк и столбцов матрицы Ak путем добавленияномеров µk и νk разрешающего элемента aµ( kk )ν k ≠ 0 .Теорема.
Пусть Ar - последняя матрица построенной выше последовательности (1). Тогда1) Минор матрицы A, составленный из запрещенных строк и110столбцовматрицыAr,базисныйиравенпроизведениюr −1(−1) p + q ∏ aµ( kk ) ν k , где p и q – число инверсий соответственно в переk =0становке строк (µ0, …, µr−1) и (ν0, …, νr−1) столбцов разрешающихэлементов;С точностью до перестановки строк и столбцов, определяемыхперестановками строк и столбцов разрешающих элементов,2) подматрица, составленная из запрещенных строк и столбцовматрицы Ar, является обратной матрицей к матрице указанного взаключении 1) теоремы базисного минора;3) в базисе столбцов (строк) матрицы Ar, отвечающих найденному базисному минору, координаты тех столбцов (строк) матрицы,которые не входят в базисный минор, находятся в соответствующихстолбцах (строках, взятых со знаком минус) матрицы Ar.Следствие 1.
Все угловые миноры вещественной квадратнойматрицы A порядка n положительны тогда и только тогда, когдауказанный выше алгоритм для µk = vk = k = 1 дает положительнуюпоследовательности r = n разрешающих элементов последовательно( k −1)сти (1): akk> 0, k = 1, ..., r.Следствие 2. Число положительных и число отрицательных собственных значений вещественной симметрической матрицы A порядка n совпадают с соответствующими числами положительных и отрицательных разрешающих элементов в последовательности (1).Замечание 1.
Если применить алгоритм (1) к расширенной матрице A0 = (A, b), где b = (b1, …, bm)T, предполагая, что начальный список запрещ енных столбцов содержит последний столбец b, то неотрицательность координат в разреш енных строках (если они есть)позволяет заключить о совместности системы линейных неравенствAx ≤ b относительно вектора x = (x1, …, xm)T (сравнение векторовпокоординатное).
Если же для всех возможных последовательностей(1) указанные выше координаты содержат отрицательные числа, тосистема неравенств Ax ≤ b несовместна.Этот результат вытекает из теоремы 1.5 монографии [2] о совместности системы линейных неравенств и утверждения 1) нашей теоремыо факторизации определителя через разрешающие элементы.Замечание 2. Утверждения 2) и 3) теоремы позволяют получитьвсе крайние точки и экстремальные направления многогранного мно-111жества Ax = b, x ≥ 0 для матрицы A ранга m, если воспользоватьсяалгебраической характеристикой крайней точки и экстремальногонаправления, приведенных в монографии [3].Возможна реализация описанного выше метода на основе легковесных процессов (PThreads), параллельной виртуальной машины(PVM), интерфейса обмена сообщениями (MPI) и процессоров с общейпамятью (OpenMP) применительно к задачам большой размерностиобращения аффинного отображения, поиска образующих конуса неотрицательных решений однородной системы линейных алгебраическихуравнений, установления положительной определ енности симметрических матриц и устойчивости многочленов с вещественными коэффициентами и включение его в стандартные пакеты.Литература1.
Исламов Г.Г. Принципы оптимальности. Ижевск, Изд-во УдГУ,1988. – 124 с.2. Черников С.Н. Линейные неравенства. М.: Наука, 1968. – 488 с.3. Базара М., Шетти Л. Нелинейное программирование. Теория иалгоритмы. М.: Мир, 1982. – 583 с.СТРАТЕГИЧЕСКОЕ НАПРАВЛЕНИЕ УДМУРТСКОГОГОСУНИВЕРСИТЕТАГ.Г. Исламов, Д.А. СивковУдмуртский государственный университет, ИжевскОбразование, наука и бизнес – это три мощных процесса в обществе, которые определяют вектор его развития. Каждый из этих процессов обладает внутренними движущими силами, которые формируютсябольшими группами людей с принципиально различными интересами.Ускорение развития одного процесса без ускорения развития остальных процессов не имеет особого смысла, т.
к. общество нуждается всинхронизированной работе этих процессов. Поэтому материальныесредства, брошенные на ускорение одного процесса, не обязательновызовут его прогресс, скорее всего они будут использованы на поддержание застоя. Главная цель образования – подготовка высококвалифицированных кадров, науки – получение принципиально новыхчастных и общих методов и фактов, бизнеса – поиск и использованиеновых форм извлечения прибыли.
В образовательном процессе главный мотив – получение оригинальных знаний, умений и навыков, в112научном процессе – достижение престижа, в бизнесе – умножение денежного капитала.Поэтому только в образовании и науке возможно скачкообразноедвижение вперед. Производство и бизнес могут развиваться толькоэволюционно, т. к. за деньги можно выполнить только тривиальнуюработу. От людей, занятых в сфере образования и науки, часто требуются такие усилия для поступательного движения вперед, которые невозможно оценить никакими денежными выплатами. Они настольковелики, что таких денег просто никто не даст.В настоящее время востребованы специалисты, которые могут выдвинуть общие цели указанных трех процессов развития образования,науки и бизнеса.
Они могут возникнуть только из образовательной инаучной среды специалистов в области новых информационных технологий.Удмуртский госуниверситет имеет все необходимое для того, чтобы начать подготовку таких специалистов на создаваемом факультете«Информационных технологий» по следующим направлениям: «Нанотехнологии», «Высокопроизводительные параллельные вычисления» и«Управление бизнес-процессами». Определенные успехи достигнуты вкаждом из этих направлений, так в области изучения наноструктурдостижения специалистов УдГУ и академических институтов ИПМ иФТИ г. Ижевска отмечались доцентом Ю.С. Митрохиным в заметке«Нанотехнологии в ХХI веке» газеты «Удмуртский университет» за 26апреля 2005 г.Учебно-научная лаборатория «Параллельных вычислительныхсистем и траспьютеров», возглавляемая профессором Г.Г.
Исламовым,с 2000 г. проводит исследования в области кластерных технологий иорганизаций параллельных и распределенных вычислений с применением известных технологий MPI, OpenMP, DVM и др. Некоторые достижения в этой области описаны Г.Г. Исламовым в заметке «Высокопроизводительные вычисления и технологии» октябрьского номерагазеты «Удмуртский университет» за 2003 г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
