Область наук:
  • Математика
  • Рік видавництва: 2005
    Журнал: Известия Південного федерального університету. Технічні науки

    Наукова стаття на тему 'Квантовий алгоритм компоновки схем еВ'

    Текст наукової роботи на тему «Квантовий алгоритм компоновки схем еВ»

    ?Розділ II. Генетичні і еволюційні алгоритми

    В.М. Курейчик КВАНТОВИЙ АЛГОРИТМ КОМПОНУВАННЯ СХЕМ ЕВА *

    .

    конструкцій (ПЕК) на основі НВІС і ССБІС найважливішими є завдання компонування. Завданнями компонування комутаційних схем (КС) вважають завдання об'єднання ПЕК нижчого рівня в ПЕК високого рівня (висхідний)

    (Спадний проектування) за заданими критеріями. [1-3]. Завдання компонування є класичними прикладами завдань багатокритеріальної оптимізації (змо). Ці завдання важко формалізуються. Вони відносяться до класу КР-повних проблем. Тому для компонування НВІС і ССБІС з п>106 ефективне застосування знайшли наближені алгоритми. Існує велика кількість алгоритмів компонування [1-4]. Останнім часом перспективними вважаються генетичні алгоритми, що дозволяють отримувати набір локально-оптимальних .

    ,

    ,

    більший розмір області допустимих рішень.

    1. Постановка завдання. Основна ідея запропонованого підходу заснована на факторіальною стисненні графовой або гіперграфовой моделі комутаційної схеми. Далі виконується дихотомічне ієрархічне розбиття графа. На останній стадії відбувається проектування дихотомічного розбиття на вихідну модель на основі послідовної або паралельної обробки розбиття [4,5].

    На етапі стиснення вихідна графовая модель в = (Х, І) перетвориться в послідовність графів в1 = (х1, ш), таких, що | Х1 | = | Х + 1 | . Згідно [4,5]. граф С1 = 1 будується з в1 на основі знаходження максимального паросполучення (МПС) МПС з И1 і об'єднання вершин, які інцидентні кожному ребру паросполучення. Вершини, які не інцидентні ребрам з МПС, перетинаються в графі С1 + 1.

    Згідно [4,5] метод знаходження МПС впливає на якість розбиття і вре-,. в = (Х, і), | Х | = п, | і | = т, X - безліч вершин, і - безліч ребер. Необхідно розбити (р ^ різати) безліч X на Х1, Х2, Х3, ..., Хк - підмножин таким обра-,

    Х: і Х2 і Х з І.І Х к = Х,

    Х! п Х 2 п Х 3п ... п Хк = 0 (1.1)

    і число вершин в кожному підмножині Х1 задовольняло нерівності

    | Х | / ск < | Х 1 | < з | Х | / к, (1.2)

    * Робота виконана за підтримки РФФД, грант № 03-01-00336

    де с - коефіцієнт, що задається конструктором, що задає допустиме відхилення ваги з > 1. Обмеження розбиття визначають кількість вершин всередині кожної підмножини Xi .

    ,

    цільову функцію

    K = Ki (X i) + K2 (X j), (1.3)

    X i і X j = X, X i n X j = 0, Ui і Ujc U,

    Ui і Uj = 0 і Ui n Uj = Uij | Uij | = Kij., Де K - сумарна кількість ребер, що лежать всередині подграфов Gi і Gj, a Ki j - число ребер, що потрапляють в розріз між Gi і Gj .

    Необхідна розробка евристик K ^ max або Kij ^ min.

    У пропонованому алгоритмі в стадії стиснення використовується новий алгоритм визначення МПС. Стадія розбиття виконується на основі робіт автора [3], а стадія розпакування на основі [4,5].

    2. Квантовий алгоритм визначення паросполучення в дводольному графі. У квантових комп'ютерах (КК) передбачається реалізація квантових обчислень шляхом перетворень над кубитами. Основні етапи роботи квантових комп'ютерів - це ініціалізація; виконання операцій над кубитами; зчитування результату обчислень [6,7]. Кубіт - це квантовий біт. Квантовий дворівневий елемент на відміну від класичного логічного елемента може знаходиться не тільки в одному з станів, але і в обох станах одночасно | ср > a | 0> + B | 1>, | A | 2 + | b | 2 = 1. Вектор станів може представляти довільну суперпозицію базисних станів. Наприклад, значенням кубіта може бути "1" з ймовірністю 20% і одночасно "0" з імовірністю 80%. Це означає, що при розшифровці значення кубіта в двадцяти випадках зі ста отримаємо "1", а у всіх інших - "0".

    Ідею і структуру квантового алгоритму запропонував Л.Гровер [6,7]. Згідно [7],

    - . -

    ритму, як би на мові обчислення кванта, ставить у відповідність кожному можливому індексу унікальний власний вектор. Спочатку готується простір

    --L Ур,

    -VN? *

    . . , -

    у суперпозиций, дорівнює кількості всіх N [6,7].

    Для реалізації пошуку це квантове простір повинен розвиватися в загальну суперпозицію, яка має амплітуду, сконцентровану в t векто-,. -гооборота U на L = 0 (log2N). Іншим і словами, якщо є відмінне від нуля збіг між стартовим простором S і цільовим И, т. Е. P | U | S ^ 0, тоді можна використовувати унітарну процедуру U для виконання класичного пошуку мети. Л.Гровс пропонує використовувати U і f (x), щоб побудувати збільшує амплітуду оператор Q, який змінює амплітуду ймовірності від ні - цілі

    векторів векторів S ^ И в ціль S = И [6,7].

    Поведінка "оракула" в алгоритмі квантового пошуку моделюється такої поворотної функцією f (x) = 0, для всіх x, t і f (x) = 1, для x = t.

    Наведемо модифіковану евристику побудови максимального паросполучення в дводольному графі [8]. Два ребра графа називаються незалежними, якщо вони не мають загальної вершини. Тоді паросочетание (ПС) - це безліч неза-. -ним (МПС) [8]. Вихідними даними є двочастковий граф, представлений у вигляді двох частин в = (Л, Б; І), і довільне побудова. Воно може полягати, зокрема, з одного ребра. Зробимо розбиття підмножини Л на дві частини. В першу включаються вершини, в які не входять ребра паросполучення. До другої частини включаються вершини, в які входять ребра паросполучення. Якщо перша частина порожня, то вихідне паросполучення є максимальним. Далі серед вершин другої частини вибирається вершина з найменшою локальної ступенем. Якщо таких вершин кілька, то вибирається будь-яка. З обраної вершини х1е Б. Маємо ребро (х1, х |), яке не є ребром паросполучення. Потім продовжуємо будувати ланцюг назад по ребру паросполучення. Отримуємо ланцюг (х1, х_0 (х_ |, хк). Далі продовжуємо аналогічно. Робота закінчується, коли нема вороття по ребру паросполучення. Далі з вихідного паросполучення видаляються ребра, наявні в , , .

    Наприклад, маємо граф в = (Л, Б; І), представлений в дводольному вигляді (рис. 1). Задано вихідне паросполучення ПС = {(1,7), (2,6)}. Розіб'ємо підмножина Л = {1,2,3,4} на дві частини: 1 = {1,2}, 2 = {3,4}. У другій частині все три вершини

    2. 5

    : 5 7 1 8 5. (5,8). -

    ходимо до вершини 4. Будуємо ланцюг 4>6 ^ 2>10. У цьому ланцюзі немає ребер, які

    . 3 10.

    Після аналізу отримуємо, що ребро (3,10) можна додати до ПС. В результаті побудовано

    = {(1,7), (2,6), (5,8), (3,10)}, показане жирними лініями на рис.1.

    Рис.1. Паросочетание в графі

    Розглянемо евристику побудови МПС на основі аналізу спеціальної матриці суміжності, і побудова в ній «парадлельних діагоналей» та ідей квантового пошуку [8]. Наприклад, нехай задано граф 0 = (Л, Б; і) (рис.2),

    Рис.2. Граф

    спеціальна матриця суміжності цього графа запишеться:

    7 8 9 10 11

    У матриці можна виділити сім «парадлельних» діагоналей:

    ПС1 = {(1,7)}, Пс5 = {(2,9), (3,10)},

    ПС2 = {(1,9)}, ПС6 = {(2,11)},

    3 = {(1,11)}, 7 = {(4,8), (6,10)}.

    4 = {(2,7), (3,8), (5,10)},

    Кожна з таких діагоналей є паросочетание досліджуваного графа.

    ,

    .

    (.3).

    Рис.3. амплітуда паросочетание

    Для подальших досліджень оракул вибере амплітуду ПС4 і на основі

    (1) -

    поєднання. Операції суперпозиції для об'єднання часткових рішень графових задач автор детально описав в роботі [8].

    Для отримання більшої кількості діагоналей з максимальним числом елементів зробимо розширення матриці:

    7 8 9 га 10 11? 7 8 9 10 11

    N. ч1 1ч 1 \ (1 1

    Ч \ 1 \ 1

    ч N. ч. \ \

    Ч Ч N.

    Ч га 1

    Як видно отримано нове паросочетание

    ПС8 = {(1,11), (2,7), (3,8), (5,10)},

    ПС8 = ПС7 УПС3, яке є максимальним.

    Зауважимо, що матрицю можна розширити справа, зліва, зверху і знизу. Наприклад, для графа в заданого матрицею

    5 6 7 8

    Побудуємо розширені матриці зверху і знизу. Це дає можливість отримати дві нових діагоналі з максимальним числом елементів.

    5 6 7 8

    N.

    До N

    З * \

    \ I4 V

    \ 1ч

    Таке розширення має відповідати таким операціям суперпозиції ПС1 = {(2,5), (3,6), (4,7)} Y {(1,8)}, | ПСХ | = 4; ПС2 = {(1,6), (2,7), (3,8)} Y {(4,5)}, | ПС2 = 4.

    1 2.

    Тоді, з урахуванням описаних вище евристик, сформулюємо композитний алгоритм визначення паросполучення в дводольному графі представимо у вигляді.

    Вихідні дані: двочастковий граф в = (Л, Б; І), | Л |, | Б |, матриця суміжності.

    1. .

    2. ,

    .

    3.

    .

    4.

    розширення спеціальної матриці зліва, справа, зверху і знизу.

    5. .

    6. .

    Час роботи алгоритму залежить від розміру аналізованої матриці: чим більше розмір матриці, тим більше може знадобитися часу. У завданнях на графах розмір входу часто вимірюється не одним числом, а двома (число вершин n і число ребер m графа). Для завдання визначення паросполучення в дводольному графі необхідно визначити час роботи алгоритму в гіршому випадку, середній час роботи алгоритму і час роботи алгоритму в кращому випадку.

    Час роботи пропонованого алгоритму в кращому випадку має порядок n. . (N).

    ,

    даному розмірі входу. Час роботи алгоритму в гіршому випадку має порядок зростання mn2, тобто O (mn2).

    Середній час роботи залежить від обраного розподілу ймовірностей, зміни числа ребер і при фіксованому числі вершин графа. На закінчення

    ,

    максимальних паросочетание в дводольних графах. Час роботи в найкращих випадках має порядок зростання O (n), де n - число вір шин графа. Використання алгоритму визначення паросполучення при компонуванні НВІС підвищує якість і ефективність конструкцій.

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Норенкав Н.П. Основи автоматизованого проектування - М .: Изд-во М'ГТУ ім. Н. Е. Баумана, 2000..

    2. Naveed Sherwani Algoritms for VLSI Physical Design Automation. KLUVER ACADEMIC PUBLISHER, Norwell, Massachusetts, 1995.

    3. Курейчик B.M. Математичне забезпечення конструкторського і технологічного проектування із застосуванням САПР. - М: Радіо і зв'язок, 1990..

    4. Karypis G., Kumar V. Analysis of Multilevel Graph Partitioning, Technicai Report 95-037, Minneapolis. March, 1998..

    5. Karypis G., Kumar V. Multilevel k-wey Hypergraph Partitioning, Technicai Report 98-019, Minneapolis. May, 1998..

    6. Grover L.K. A Fast Quantum Mechanical Algorithm for Data-base Search. Proc. 28 th Ann. ACM Press, New York, 1996..

    7. Grover L.K. Synthesis of Quantum Superpositions by Quantum Computation. Physical Rev. Letters, Vol 85. No.6, 2000..

    8. Курі йчік B.M. Квантовий алгоритм визна Оленою Гамільтона циклу // Теоретичний та науково-методичний журнал «Перспективні інформаційні технології та інтелектуальні системи», N 1 (21). - Таганрог, ТРТУ, 2005.

    В.В. Курейчик, М.Н. Міщенко біонічної АЛГОРИТМ РОЗМІЩЕННЯ ЕЛЕМЕНТІВ *

    У загальній проблемі САПР завдання розміщення типових елементів конструк- ()

    ,

    об'єкта заданого ступеня деталізації. Процес розміщення елементів ПЕК ЕВА зводиться до вибору стратегії проектування, тобто до пошуку і визначення послідовності операцій обираних ОПР для вирішення поставленого завдання.

    * Робота виконана за підтримки РФФД, грант № 03-01-00336


    Завантажити оригінал статті:

    Завантажити