4488
правок
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
Строка 342: | Строка 342: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Алгоритм FBB был внедрен в SIS/MISII [1] и протестирован на наборе больших тестовых схем ISCAS и MCNC на рабочей станции SPARC 10 с процессором с тактовой частотой 36 МГц и 32 МБ памяти. | Алгоритм FBB был внедрен в SIS/MISII [1] и протестирован на наборе больших тестовых схем ISCAS и MCNC на рабочей станции SPARC 10 с процессором с тактовой частотой 36 МГц и 32 МБ памяти. | ||
В таблице 1 приводится сравнение средних результатов алгоритма FBB в процессе биразбиения с результатами Дасдана и Эйканата из [3]. SN основан на применении эвристического алгоритма K&L в работе Санчиса [14]. PFM3 основан на применении эвристического алгоритма K&L со свободными перемещениями, как описано в [3]. На каждой схеме SN выполнялся 20 раз, а PFM3 – 10 раз с различными изначальными разбиениями, сгенерированными случайным образом. FBB исполнялся 10 раз с различными случайным образом выбранными s и t. За единственным исключением FBB показал себя лучше SN и PFM3 на пяти схемах. В среднем FBB удалось найти биразбиение с количеством пересечений сеток на 24,5% и 19,0% меньше, чем SN и PFM3, соответственно. Время исполнения алгоритмов SN, PFM3 и FBB не сравнивалось, поскольку они исполнялись на разных рабочих станциях. | В таблице 1 приводится сравнение средних результатов алгоритма FBB в процессе биразбиения с результатами Дасдана и Эйканата из [3]. SN основан на применении эвристического алгоритма K&L в работе Санчиса [14]. PFM3 основан на применении эвристического алгоритма K&L со свободными перемещениями, как описано в [3]. На каждой схеме SN выполнялся 20 раз, а PFM3 – 10 раз с различными изначальными разбиениями, сгенерированными случайным образом. FBB исполнялся 10 раз с различными случайным образом выбранными s и t. За единственным исключением FBB показал себя лучше SN и PFM3 на пяти схемах. В среднем FBB удалось найти биразбиение с количеством пересечений сеток на 24,5% и 19,0% меньше, чем SN и PFM3, соответственно. Время исполнения алгоритмов SN, PFM3 и FBB не сравнивалось, поскольку они исполнялись на разных рабочих станциях. |
правок