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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
1. Verfasser:	Иванов, Д.Е.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2011
Schriftenreihe:	Управляющие системы и машины
Schlagworte:	Новые методы в информатике
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/82907
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем / Д.Е. Иванов // Управляющие системы и машины. — 2011. — № 1. — С. 25-32. — Бібліогр.: 16 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-82907
record_format	dspace
spelling	irk-123456789-829072015-06-12T03:02:08Z Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем Иванов, Д.Е. Новые методы в информатике Рассмотрена задача построения параллельных генетических алгоритмов генерации идентифицирующих последовательностей для цифровых устройств по схеме «мастер–рабочий». Исследована их масштабируемость на системах с большим числом вычислительных ядер. The task of constructing the parallel genetic algorithms for generating the identifying sequences for synchronous sequential circuits based on the «master-slave» scheme is considered. The problem of their scalability on systems with a great number of cores is investigated. Розглянуто задачу побудови паралельних генетичних алгоритмів генерації ідентифікуючих послідовностей цифрових пристроїв за схемою «майстер–робітник». Досліджено їх масштабованість на системах з великою кількістю обчислювальних ядер. 2011 Article Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем / Д.Е. Иванов // Управляющие системы и машины. — 2011. — № 1. — С. 25-32. — Бібліогр.: 16 назв. — рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/82907 681.518 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Новые методы в информатике Новые методы в информатике
spellingShingle	Новые методы в информатике Новые методы в информатике Иванов, Д.Е. Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем Управляющие системы и машины
description	Рассмотрена задача построения параллельных генетических алгоритмов генерации идентифицирующих последовательностей для цифровых устройств по схеме «мастер–рабочий». Исследована их масштабируемость на системах с большим числом вычислительных ядер.
format	Article
author	Иванов, Д.Е.
author_facet	Иванов, Д.Е.
author_sort	Иванов, Д.Е.
title	Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем
title_short	Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем
title_full	Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем
title_fullStr	Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем
title_full_unstemmed	Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем
title_sort	масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2011
topic_facet	Новые методы в информатике
url	http://dspace.nbuv.gov.ua/handle/123456789/82907
citation_txt	Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем / Д.Е. Иванов // Управляющие системы и машины. — 2011. — № 1. — С. 25-32. — Бібліогр.: 16 назв. — рос.
series	Управляющие системы и машины
work_keys_str_mv	AT ivanovde masštabiruemyjparallelʹnyjgenetičeskijalgoritmpostroeniâidentificiruûŝihposledovatelʹnostejdlâsovremennyhmnogoâdernyhvyčislitelʹnyhsistem
first_indexed	2025-07-06T09:34:37Z
last_indexed	2025-07-06T09:34:37Z
_version_	1836889646208909312
fulltext	УСиМ, 2011, № 1 25 УДК 681.518 Д.Е. Иванов Масштабируемый параллельный генетический алгоритм построения идентифицирующих последовательностей для современных многоядерных вычислительных систем Рассмотрена задача построения параллельных генетических алгоритмов генерации идентифицирующих последовательностей для цифровых устройств по схеме «мастер–рабочий». Исследована их масштабируемость на системах с большим числом вы- числительных ядер. The task of constructing the parallel genetic algorithms for generating the identifying sequences for synchronous sequential circuits based on the «master-slave» scheme is considered. The problem of their scalability on systems with a great number of cores is investigated. Розглянуто задачу побудови паралельних генетичних алгоритмів генерації ідентифікуючих послідовностей цифрових пристроїв за схемою «майстер–робітник». Досліджено їх масштабованість на системах з великою кількістю обчислюва- льних ядер. Введение. Генетические алгоритмы (ГА) [1–2] заняли прочное место в инструментарии раз- работчиков цифровых схем. Диапазон их при- менения очень широк: от оптимального кодиро- вания состояний последовательностных схем [3] до построения идентифицирующих после- довательностей [4–5]. Их популярность связа- на как с прозрачностью стратегии, так и с тем, что они позволяют обрабатывать схемы боль- шой размерности, для которых структурные ме- тоды не дают результата. Генетические алгоритмы построения вход- ных идентифицирующих последовательностей основаны на моделировании работы цифровой схемы. Для оценки потенциальных решений задачи и в зависимости от требуемой точно- сти/скорости работы они могут использовать исправное моделирование и моделирование с неисправностями. В некотором смысле такое построение решений – замена задачи синтеза на итеративную задачу анализа. Процедуры мо- делирования сами по себе требуют значитель- ных вычислительных ресурсов, в частности времени. Итеративный многократный вызов таких процедур приводит к тому, что ГА по- строения идентифицирующих последователь- ностей достаточно медленные, что есть основ- ным их недостатком. Ключевые слова: генетический алгоритм, последова- тельностная схема, многоядерные вычислительные сис- темы, параллельные вычисления. Для решения данной проблемы предложено несколько подходов. В работе [6] разработан па- раллельный генетический алгоритм (ПГА) по- строения тестов, основанный на схеме остро- вов. В нем происходит развитие нескольких независимых популяций с немного измененны- ми генетическими параметрами. Такое постро- ение алгоритма позволяет не только повысить скорость работы, но и качество получаемых решений. К недостаткам подхода следует от- нести довольно сложную программную реали- зацию, которая, помимо использования специ- альных средств параллельного программиро- вания, требует создания протокола взаимодей- ствия компонент, что само по себе нетриви- альная задача. Возможен также подход разра- ботки параллельных версий процедур модели- рования. Так, в [7] предложена параллельная версия хорошо известного алгоритма модели- рования цифровых схем с неисправностями PROOFS. Его свойства, в том числе и способ- ность к масштабированию, изучены для раз- личных аппаратных платформ. Недостаток ука- занных подходов – они разработаны для доро- гостоящих вычислительных систем. В настоящее время стандартом «де-факто» рабочих станций становится применение мно- гоядерных процессоров [8]. В коммерческих образцах процессоров уже сегодня число ядер достигает 4–6. При этом в компании Intel ве- дутся разработки чипов с числом вычисли- тельных ядер до 80-ти, что привлекло интерес 26 УСиМ, 2011, № 1 к разработке параллельных алгоритмов для та- ких рабочих станций. Авторы уже предлагали параллельные версии ГА для работы на многоядерных рабочих стан- циях. В отличие от упомянутых выше ПГА они строятся по схеме «мастер–рабочий». В част- ности для алгоритма построения последователь- ностей верификации эквивалентности заданных схем [9] предложена параллельная версия [10] и исследованы его характеристики по распа- раллеливанию на 4-ядерной рабочей станции. Цель данной статьи – дальнейшее изучение свойства масштабируемости параллельных вер- сий ГА на рабочей станции с большим числом вычислительных ядер. Под масштабируемостью программного обеспечения понимают способ- ность к пропорциональному увеличению про- изводительности при увеличении аппаратных средств. В свою очередь под увеличением ап- паратных средств следует понимать увеличе- ние числа вычислительных ядер в инструмен- тальной системе. Основной вопрос проведен- ного исследования: являются ли предлагаемые параллельные версии ГА масштабируемыми, т.е. будет ли дальнейшее увеличение числа ядер в инструментальной системе подтвержде- но адекватным ростом скорости работы ПГА? ГА построения идентифицирующих по- следовательностей Напомним кратко схему генетического ал- горитма. Структурно ГА представляют собой итеративный процесс построения новых попу- ляций из текущей (рис. 1), цель которого – по- иск субоптимального решения некоторой оп- тимизационной задачи. Критерий качества по- тенциальных решений обычно задается конст- руктивно в виде оценочной функции. Каждая популяция состоит из некоторого числа потен- циальных решений – особей. Алгоритм закан- чивает работу либо когда найдено решение, либо достигнуто максимальное число итера- ций. В ГА построения входных идентифици- рующих последовательностей каждая особь представляет собой входную двоичную после- довательность. При построении новых особей используются генетические операции: селек- ция, скрещивание и мутация. Не будем оста- навливаться подробно на данных моментах, поскольку они неоднократно подробно описы- вались, например в [11]. Для оценки качества последовательностей используется моделиро- вание работы цифровой схемы на данной по- следовательности. Используется как исправное моделирование, так и моделирование с неис- правностями. Именно эти процедуры опреде- ляют большую временную сложность данного класса ГА. ГА построения входных идентифицирую- щих последовательностей условно делятся на два класса.  Одноуровневые ГА. В алгоритмах данного класса имеется одна глобальная цель, и, следо- вательно, строится одна входная последователь- ность, а цикл построения популяций ГА вызы- вается только один раз. К алгоритмам данного класса, например, относятся задача построения инициализирующих последовательностей и за- дача проверки эквивалентности двух заданных последовательностных схем. Построение начальной популяции Оценка особей в популяции Достигнут критерий остановки? Построение промежуточной популяции : селекция , скрещивание , мутация Оценка особей в промежуточной популяции Добавление новых особей в популяцию Построение новой популяции : редукция Решение = выбор лучшей особи Да Нет Рис. 1. Укрупненная схема генетического алгоритма  Двухуровневые ГА. В данных алгоритмах итеративно происходит выбор промежуточных целей, для достижения которых вызывается основной цикл ГА. К такому классу относятся УСиМ, 2011, № 1 27 алгоритмы построения тестовых и диагности- ческих последовательностей. В качестве про- межуточных целей в данных алгоритмах вы- ступают задача тестирования одной неисправ- ности из полного списка неисправностей (ГА построения тестов) или задача построения ди- агностической последовательности для вы- бранного класса неразличимых неисправно- стей (ГА построения диагностических после- довательностей). Для изучения свойств параллелизации из всех ранее разработанных алгоритмов выберем одноуровневый ГА построения последователь- ностей, которые проверяют эквивалентность двух заданных последовательностных схем [9]. На его основе в следующем разделе предста- вим параллельную версию алгоритма. Отме- тим также, выбор данного алгоритма означает, что будут исследоваться свойства параллельно- сти генетических алгоритмов, которые вклю- чают процедуры исправного моделирования ци- фровых схем. Изучение аналогичных свойств ПГА, включающих процедуры моделирования схем с неисправностями, требует отдельного ис- следования. Параллельные версии ГА Схемы построения параллельных ГА Они делятся на два больших класса: «остро- вов» и «мастер–рабочий». Схема «островов» предполагает развитие не- скольких относительно независимых популя- ций. Они проводят обмен лучшими особями через некоторое число поколений. Данная схе- ма наиболее часто применяется в кластерных архитектурах с разделяемой памятью. Эффек- тивность схемы «островов» зависит от очень большого числа параметров, среди которых:  топология, определяющая, какие подпопу- ляции будут считаться соседними и, соответ- ственно, между какими островами будет воз- можен обмен особями;  время изоляции, определяющее, сколько эпох ГА не будет проводиться миграция;  степень миграции, которая определяет ко- личество особей, участвующих в миграции;  стратегия отбора особей для миграции;  стратегия удаления особей из подпопуля- ции при проведении миграции;  стратегия репликации мигрирующих особей. Отметим, что хотя популяции развиваются независимо и равноправно, в реализациях та- кого вида алгоритмов выделяется сервер, ко- торый инициализирует работу и реализует то- пологию обмена данными. Более того, синхро- низация работы копий ГА на островах требует описания способа их взаимодействия. Точная и корректная реализация такого взаимодействия различных копий ГА в модели островов – слож- ная задача [11]. Для этого реализуются прото- колы, в которых фиксируются точки обмена информацией между островами и сервером. Схема «мастер–рабочий» построения ПГА реализует только один цикл развития популя- ций, осуществляемый на процессоре, который называется «мастер». На «рабочие» процессо- ры передается вычислительная нагрузка, свя- занная с оценкой особей. Эта работа как раз и может быть выполнена параллельно. Хотя ор- ганизация параллельности по данной схеме требует некоторых ресурсов, выигрыш может оказаться весьма существенным. Особенно это заметно, если оценка вычисляется по сложным формулам либо, как в нашем случае, на осно- вании моделирования. Данная схема более прос- та и потому выбрана для реализации Построение параллельного ГА по схеме «мастер–рабочий» Из описания структуры ГА видно, что он носит итеративный характер. При этом рабо- та на текущей итерации существенно зависит от результатов, полученных в итоге работы предыдущей итерации. Такая последователь- ностная схема работы не позволяет напрямую построить параллельную версию алгоритма. Однако в ГА построения идентифицирующих последовательностей все-таки можно выделить достаточно крупные фрагменты, которые яв- ляются независимыми и позволяют параллель- ную реализацию. Это процедуры вычисления оценочных функций. В рассматриваемых алго- ритмах эти процедуры есть процедуры моде- лирования работы цифровых схем, что пред- 28 УСиМ, 2011, № 1 полагает достаточно высокую вычислительную нагрузку. Благодаря этому, при работе алгорит- ма большая часть вычислительной нагрузки приходится именно на данные процедуры мо- делирования, и лишь небольшая их часть – на процедуры построения новых популяций, ко- торые в принципе не распараллеливаются. Ос- новываясь на этом можно предположить, что распараллеливания процедур вычисления оце- нок особей позволит достичь приемлемого мас- штабирования алгоритма. Для иллюстрации механизма распараллели- вания, применяемого в ГА данного типа, рас- смотрим подробно построение процедуры вы- числения оценок особей. Вначале рассмотрим последовательную реализацию данной проце- дуры. Ее псевдокод приведен ниже. ОценитьПопуляцию(Популяция, ЧислоОсобей) { for( i=0 ; i<ЧислоОсобей ; i++ ) { ОценитьОсобь(Популяция[i]); } } Процедура «ОценитьОсобь», вложенная во внешний цикл, в непараллельной модели вы- числений для особи i выполняется только после завершения предыдущей итерации i – 1. Если условно принять за один модельный такт вре- мя, необходимое для вычисления оценки одной особи в популяции, то схематично порядок вы- числения при такой организации процесса можно изобразить так (рис. 2,а). Оценка особи 1 Оценка особи 2 Оценка особи n Оценка особи 1 Оценка особи n В ре м я 1 2 … n ... ... а б Рис. 2. Способы вычисления оценок особей в популяции: а – последовательный; б – параллельный Очевидно, что для последовательной модели данный порядок вычислений естественен. Легко видеть также, что любые две последователь- ные процедуры «ОценитьОсобь» являются не- зависимыми по данным, поскольку моделиро- вание выполняется для разных входных после- довательностей, и, следовательно, представляют собой независимые ветви программы. Поэтому можно организовать параллельное выполнение нескольких таких функций. Основным средством организации параллель- ных вычислений в многопроцессорных систе- мах с общей памятью есть потоки (threads). Данную парадигму поддерживают все совре- менные среды программирования. Методами работы с потоками являются: создание, удале- ние, приостановка, запуск на выполнение. Ес- ли оформить процедуру оценки особи в виде потокового класса, то приведенный ранее фраг- мент будет выглядеть так: ОценитьПопуляцию(Популяция, ЧислоОсобей { for( i=0 ; i<ЧислоОсобей ; i++ ) { ОценитьОсобь->СоздатьПоток(Популя- ция[i]); 4 ОценитьОсобь->Выполнить(); ОценитьОсобь->ЖдатьЗавершения(); ОценитьОсобь->УдалитьПоток(); } } Схематически параллельное вычисление оце- нок особей в популяции представлено на рис. 2,б. Организация такого процесса состоит в том, что- бы создать одновременно несколько экземпля- ров потокового класса «ОценитьОсобь», запус- тить их на выполнение, передав индивидуаль- ные входные параметры, и далее ожидать окон- чания выполнения для каждого экземпляра клас- са. Число особей в таких реализациях ПГА обычно гораздо больше числа вычислительных процессоров в системе (4–6 – в текущих мар- кетинговых процессорах Intel, до 64 – в специа- лизированных системах). Поскольку предполо- жительно один вычислительный поток будет за- гружать один процессор (одно ядро) в системе, то необходимо одновременно выполнять такое число потоков, которое равно числу процессо- ров. Таким образом, в коде появится дополни- тельный вложенный цикл. Приведем псевдокод параллельной реализации в терминах потоков. ОценитьПопуляцию(Популяция, ЧислоОсобей) { for( int i=0 ; i<ЧислоОсобей/ЧислоПо- токов ; i++ ) УСиМ, 2011, № 1 29 { j=i*ЧислоПотоков; выполнять_параллельно_для j, j+1, … …, j+ЧислоПотоков-1 { ОценитьОсобь->СоздатьПоток(Попу- ляция[j]); ОценитьОсобь->Выполнить(); } ЖдатьОкончанияПотоков j, j+1, … …, j+ЧислоПотоков-1; УдалитьПотоки(); } } Переменная «ЧислоПотоков» показывает, сколько вычислительных потоков будет вы- полняться одновременно. Обычно для много- ядерных систем рекомендуется выбирать чис- ло потоков, равное числу вычислительных ядер системы [13], однако покажем, что в нашем случае это не так. Эксперименты и результаты Благодаря компании Intel, авторам предо- ставили доступ к лаборатории MTL (Manycore Testing Lab). Дистанционно была организована работа с рабочей станцией под управлением опе- рационной системы MS Windows Server 2008 R2. Многоядерная ВС содержала два процессора Intel(R) Xeon CPU X5650 с частотой 2.67 Ггц (каждый по шесть вычислительных ядер), тех- нология HyperThreading – выключена, объем оперативной памяти 16 Гб. Функция GetSystem- Info() также показывала наличие 12 вычисли- тельных ядер в системе. В таких условиях проведены машинные экс- перименты, которые дадут ответ на следующие вопросы:  является ли предложенная структура па- раллельного алгоритма масштабируемой;  каков предел масштабируемости данной версии алгоритма;  сколько вычислительных потоков необхо- димо запускать для наилучшей загрузки сис- темы, и как это число связано с числом вычис- лительных ядер. При проведении экспериментов использо- вались контрольные схемы ISCAS–89 [14], из которых сразу были исключены схемы малой размерности ввиду того, что для них время моделирования составляет порядка нескольких секунд и построение параллельных версий ал- горитмов не актуально. Первые же эксперименты показали, что нет необходимости привязывать вычислительные потоки к ядрам. Это в несколько раз уменьша- ло производительность параллельной версии алгоритма. Данный факт согласуется с выво- дами [15]: в параллельной вычислительной сре- де наибольшее ускорение получается в случае такой привязки потоков, которая допускает их миграцию между ядрами внутри одного сокета либо вычислительного узла. Поскольку наш вы- числительный сервер фактически представляет собой один вычислительный узел с 12 ядрами, то наибольшее ускорение должно быть полу- чено без привязки потоков к ядрам. Одиночный запуск ПГА эмулировал работу генетического алгоритма на фиксированном чис- ле итераций (число поколений = 50), что по- зволяло измерять ускорение работы ГА. При проведении машинных экспериментов для выбранного множества схем выполнялись многократные запуски параллельной версии ГА с различным числом одновременных вычисли- тельных потоков (переменная «ЧислоПотоков» в коде выше). Условно разделим эксперименты на две серии. В первой серии число потоков изменялось от одного до 12, где верхняя гра- ница определялась числом физических вычис- лительных ядер. Во второй серии эксперимен- тов число потоков изменялось от одного до 128. Данная серия экспериментов проводилась с целью выяснения максимально возможного ус- корения ПГА. В качестве последовательной вер- сии алгоритма выбран ПГА, в котором запускал- ся один вычислительный поток оценки особи. Скорость работы такой реализации, вообще го- воря, отличается от истинно последовательной версии алгоритма [7] и уменьшается на один– четыре процента, что связано с накладными расходами на организацию параллельных вы- числений. Однако такую погрешность вполне можно считать приемлемой, поскольку авторы не имели возможности в инструментальной 30 УСиМ, 2011, № 1 системе отключить от работы 11 ядер для по- лучения абсолютно точных цифровых данных. Объем числовых результатов, полученных при проведении экспериментов, очень велик. Приведем значения для ускорения работы ПГА. На основе данной информации и известных фор- мул можно вычислить остальные характерис- тики параллельной версии алгоритма: эффек- тивность использования ядер и долю последо- вательного кода [16]. Числовые результаты пер- вой серии экспериментов приведены в табл. 1. Высокие числовые значения превосходят дан- ные, приведенные в [7]. Однако необходимо отметить, что в указанной работе приводятся данные по ускорению для параллельной вер- сии программы моделирования с неисправно- стями. Авторам в настоящее время не извест- ны аналогичные результаты для параллельных генетических алгоритмов. Графики ускорения работы ПГА для первой серии экспериментов показаны на рис. 3. 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 12 число вычислительных потоков ус ко ре ни е, р аз в среднем лучшчее (s3271) худшее (s13207) Рис. 3. Ускорение работы ПГА в зависимости от числа вычис- лительных потоков. Серия 1 экспериментов Анализ результатов первой серии экспери- ментов (табл. 2, колонка «серия 1») показыва- ет, что почти для всех схем максимальное ус- корение работы ПГА достигнуто в правом кон- це диапазона изменений числа потоков. Это привело к предположению, что последующее наращивание числа потоков позволит и далее расти параметру ускорения работы. С этой целью проведена вторая серия экс- периментов, в которой число потоков изменя- лось от одного до 128. Большой объем полу- ченных цифровых данных не позволяет при- вести их в данной статье. На рис. 4 показан график ускорения работы ПГА в трех случаях данной серии экспериментов. Сравнение с гра- Т а б л и ц а 2. Максимальное достигнутое ускорение для кон- трольных схем Серия 1, 12 потоков максимум Серия 2, 128 потоков максимум Схема Макс. достигнутое ускорение Минимальное число пото- ков для дос- тигнутого ускорения Макс. достигнутое ускорение Минимальное число пото- ков для дос- тигнутого ускорения s3271 9.00 12 13.50 105 s3330 5.64 12 9.54 115 s3384 6.22 12 11.00 100 s4863 9.50 12 13.15 119 s5378 3.96 12 4.12 18 s6669 7.81 12 12.30 128 s9234 2.27 7 2.33 17 s13207 2.18 12 2.18 12 s15850 3.23 10 3.23 12 s35932 8.39 12 10.51 125 s38584 6.53 12 7.11 25 средн. 5.88 11.36 8.09 80 Т а б л и ц а 1. Ускорение работы ПГА в зависимости от числа потоков Ускорение для заданной схемы, раз (для строки 1 приведено абсолютное время работы в сек.) Число потоков s3271 s3330 s3384 s4863 s5378 s6669 s9234 s13207 s15850 s35932 s38584 средн. 1 162 124 143 342 107 406 84 124 197 914 633 1,00 2 1,78 1,80 1,72 1,77 1,65 1,77 1,47 1,43 1,56 1,79 1,70 1,68 3 2,49 2,48 2,42 2,59 2,18 2,53 1,79 1,75 2,07 3,14 2,78 2,38 4 3,60 3,26 3,11 4,38 2,82 3,44 2,00 1,94 2,53 4,57 4,28 3,27 5 4,15 3,76 3,67 4,75 3,24 4,10 2,21 2,07 2,94 5,25 5,10 3,75 6 5,59 4,43 4,21 6,71 3,45 5,21 2,27 2,10 3,13 6,05 5,36 4,41 7 5,59 4,43 4,47 6,58 3,57 5,41 2,27 2,10 3,13 6,35 5,65 4,50 8 7,36 4,77 4,77 7,60 3,69 6,44 2,27 2,14 3,18 6,67 5,92 4,98 9 6,32 4,96 5,11 6,98 3,69 6,44 2,27 2,10 3,13 6,87 5,70 4,86 10 8,53 5,17 5,96 9,00 3,82 7,66 2,27 2,14 3,23 7,95 6,46 5,65 11 6,75 5,17 5,50 7,60 3,82 7,12 2,21 2,14 3,13 7,55 6,09 5,19 12 9,00 5,64 6,22 9,50 3,96 7,81 2,27 2,18 3,18 8,39 6,53 5,88 УСиМ, 2011, № 1 31 фиком на рис. 3 показывает, что максимальное достигнутое ускорение существенно выросло. Таблица 2 содержит некоторые числовые дан- ные для сравнения двух серий экспериментов, из которых видно, что максимально достигну- тое ускорение увеличилось с девяти до 13,5 раз. Причем для трех схем из одиннадцати (s3271, s4863, s6669) это ускорение было вы- ше, чем число вычислительных ядер в системе. Для одной из схем (s3384) дальнейшее увели- чение числа потоков позволило увеличить по- лученное в серии 1 значение ускорения еще в 1,77 раза: с 6.22 до 11 раз. Только для одной из схем (s6669) во второй серии экспериментов максимальное ускорение достигнуто при макси- мальном числе потоков 128. Это говорит о том, что для набора схем в целом нет необходимости далее увеличивать число параллельных вычис- лительных потоков. Для схем с низким значени- ем параметра ускорения в первой серии экспе- риментов дальнейший рост числа потоков прак- тически не улучшает ситуацию. А для двух схем (s13207, s15850) лучшие значения ускорения относятся к первой серии экспериментов. 0 2 4 6 8 10 12 14 16 1 9 17 25 33 41 49 57 65 73 81 89 97 10 5 11 3 12 1 число вычислительных потоков ус ко ре ни е, р аз в среднем худшее (s13207) лучшее (s3271) 1 10 19 28 37 46 55 64 73 82 91 10 0 10 9 11 8 12 7 13 6 Рис. 4. Ускорение работы ПГА в зависимости от числа вычис- лительных потоков. Серия 2 экспериментов Таким образом, приведенные числовые ре- зультаты показывают, что для максимальной утилизации вычислительных ядер в системе, число одновременно запущенных потоков долж- но быть существенно больше, чем число ядер. Однако точное определение данного числа все еще не представляется возможным. Заключение. В статье изучаются свойства распараллеливания генетических алгоритмов построения входных идентифицирующих по- следовательностей. Для предложенной парал- лельной версии алгоритма верификации экви- валентности схем проведены машинные экспе- рименты на параллельной рабочей станции с общей памятью, содержащей 12 вычислитель- ных ядер. Данные эксперименты показали от- личную масштабируемость для некоторых контрольных схем, тогда как для других она оказалась крайне низкой, причины чего, оче- видно, кроются во внутренней структуре дан- ных схем. В среднем достигнуто ускорение ра- боты алгоритма в 8.09 раза. Причины ограни- ченности этого показателя требуют дальней- шего изучения. Для достижения максимально- го ускорения необходимо выбирать число па- раллельных потоков существенно больше, чем число вычислительных ядер в системе. Авторы благодарят компанию Intel, а так- же ее подразделение Intel Software Network за предоставленную возможность доступа к 12- ядерной рабочей станции лаборатории Many- core Testing Lab. Выражаем личную благодар- ность Майку Пирсу (Mike Pearce), а также Пи- теру Гинсбику (Peter Hinsbeeck) за оказанную техническую поддержку во время сессии дос- тупа и после нее. 1. Goldberg D.E. Genetic Algorithm in Search, Optimi- zation, and Machine Learning. – Addison-Wesley, 1989. – 432 p. 2. Скобцов Ю.А. Основы эволюционных вычисле- ний. – Донецк: ДонНТУ, 2008. – 326 с. 3. Wu X., Pedram М. Low power sequential circuit design by using priority encoding and clock gating // Proc. of the 2000 Intern. Symp. on Low power electronics and design, Rapallo, Italy. – 2000. – P. 143–148. 4. GATTO: a Genetic Algorithm for Automatic Test Pat- tern Generation for Large Synchronous Sequential Cir- cuits / F. Corno, P. Prinetto, M. Rebaudengo et al. // IEEE Transactions on Computer-Aided Design, August 1996. – 15, № 8. – P. 943–951. 5. Evolutionary approach to the functional test generation for digital circuits / Yu.A. Skobtsov, D.E. Ivanov, V.Y. Skobtsov et al. // Proc. of 9th Biennial Baltic Elec- tronics Conf., BEC 2004, Tallinn, October 2004. – Tallinn Univ. of Techn. – 2004. – P. 229–232. 6. А Parallel Genetic Algorithm for Automatic Genera- tion of Test Sequences for Digital Circuits / F. Corno, P. Prinetto, M. Rebaudengo et al. // Intern. Conf. on High-Performance Computing and Networking, Brus- 32 УСиМ, 2011, № 1 sels (Belgium), April // Lecture Notes In Comp. Sci. – 1996. – 1067. – P. 454–459. 7. A parallel algorithm for fault simulation based on PROOFS / S. Parker, P. Banerjee, J. Patel // Proc. IEEE Int. Conf. Comp. Design. – 1995. – P. 616–621. 8. Wirt R. Intel® Software Insight. Multi-core Capability / USA: Intel Corporation, 2005, July. – 11 p. 9. Иванов Д.Е. Генетический подход проверки эквива- лентности последовательностных схем // Радіоелект- роніка. Інформатика. Управління. – 2009. – № 1(20). – С. 118–123. 10. Иванов Д.Е. Алгоритм параллельного вычисления оценок особей при верификации эквивалентности последовательностных схем // Проблемы информа- ционных технологий. – 2009.– № 1(005). – С. 105– 112. 11. Иванов Д.Е. Генетические алгоритмы построения идентифицирующих последовательностей для циф- ровых схем с памятью // Наук. пр. Донецького нац. техн. ун-ту. Сер.: Обчислювальна техніка та авто- матизація. – 2008. – 14(129). – С. 97–106. 12. Иванов Д.Е. Взаимодействие компонент в распре- деленных генетических алгоритмах генерации тес- тов // Там же. – 2009. –16(147). – С. 121–127. 13. Gillespie M. Масштабирование программных архи- тектур для многоядерных вычислительных систем будущего. – http://software.intel.com/ru-ru/articles/sca- ling-software-architectures-for-the-future-of-multi-core- computing/ 14. Combinational profiles of sequential benchmark circuits / F. Brgles, D. Bryan, K. Kozminski // Intern. Symp. of circuits and syst., ISCAS–89. – 1989. – P. 1929–1934. 15. Методы привязки параллельных процессов и по- токов к многоядерным узлам вычислительных систем / С.П. Копысов, А.К. Новиков, Л.Е. Тонков и др. // Вест. Удмурт. ун-та. – 2010. – № 1. – С. 123–132. 16. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислитель- ных систем. Учебн. пособие. – Н. Новгород: Изд-во ННГУ им. Н.И. Лобачевского. – 2003. – 184 с. Поступила 20.10.2010 Тел. для справок: (062) 311-6795 (Донецк) E-mail: ivanov@iamm.ac.donetsk.ua, http://www.iamm.ac.donetsk.ua/ru/employees/e15/ © Д.Е. Иванов, 2011  << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice

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

Institution

Ähnliche Einträge