Разработка и исследование комплексного гибридного генетического алгоритма разбиения схем
Диссертация
Для повышения качества решений, были разработаны методы кодирования использующие знание о решаемой задачи, что позволило повысить качество получаемых решений на начальном этапе работы алгоритма. Созданы модифицированные процедуры, для генетических операторов, зависящие от динамических параметров, позволяющие повысить устойчивость генетического поиска и качество получаемых решений. Теоретически… Читать ещё >
Список литературы
- Конструирование аппаратуры на БИС и СБИС. Под ред. Высоцкого Б. Ф. и Стерепского В. П. М.: Радио и связь, 1989.
- Петренко А.И., Лошаков В. Н., Тетельбаум А. Я., Шрамченко Б. Л. Автоматизированное проектирование СБИС на базовых кристаллах. М.: Радио и связь, 1988. 160 е., ил.
- Савельев А.Я., Овчинников В. А. Конструирование ЭВМ и систем. Москва, Высшая школа, 1989.
- Dominic A. Antonelli, Danny Z. Chen, Timothy J. Dysart, Xiaobo S. Hundrew, B. Kahng Peter, M. Kogge Richard, C., Murphy Michael, T. Niemier, «Quantum-Dot Cellular Automata (QCA) Circuit Partitioning: Problem Modeling and Solutions», DAC, 2004 .
- Гладков Л.А., Курейчик В.В., Курейчик В.М. .Дискретная математика. Часть 2. Теория алгоритмов и алгебра логики: Учебное пособие. Под ред. В. М. Курейчика. Таганрог: Изд-во ТРТУ, 2006. -152 с.
- Норенков И.П. Основы автоматизированного проектирования. М.: Изд-во МГТУ имени Н. Э. Баумана, 2006.-360с.
- Schaller Robert R. MOORE IS LAW: past, present, and future. IEEE SPECTRUM JUNE, 1997, pp. 53−59.
- Деньдобренко Б.П., Малика А. С. Автоматизация проектирования радиоэлектронной аппаратуры. М., Высш. шк., 1980. 384 с.
- Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. Москва, Радио и связь, 1990. 352 е.: ил.
- Sherwani N.A. Algorithms for VLSI Physical Design Automation. Norweil, Kluwer Academic Publishers, 1995, 538 p.
- Горинштейи Л.Л. О разрезании графа. Известия АН СССР, Техническая кибернетика, 1969, № 1.
- Курейчик В.М., Курейчик В. В. Генетический алгоритм разбиения графа. Известия Академии наук. Теория и системы управления, № 4, 1999.
- Youssef G. Saab, Vasant В. Rao. «Fast Effective Heuristics for the Graph Bisectioning Problem», IEEE, vol.9 N1, January 1990, Transaction on computer-aided design.
- Y.C. Wei, C.K. Cheng. «A two-level two-way Partitioning Algorithm», Tech. report CH2924−9, University of California, San Diego, IEEE, 1990.
- Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. «A general purpose multiple way Partitioning Algorithm», 28th ACM/IEEE Design Automation Conference, paper 25/1, pp.421−425., 1991.
- C.J. Aipert, A.B. Kahng. «Geometric Embeddings for Faster and Better Multi-Way Netlist Partitioning», in 30th ACM/IEEE Design automation conference, 1993, pp. 743−748.
- Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж, 1995. 69 с.
- Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company Inc., Massachusetts, 1989.412 р.
- Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1992
- Kureichik V.M. et all. Some new features in Genetic Solution of the Traveling Salesman Problem. Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control, Plymouth, UK, 1996. pp. 294−296.
- Курейчик B.M. Генетические алгоритмы и их применение в САПР. Интеллектуальные САПР, меж. сб., Таганрог, 1995. стр. 7−11.
- Лебедев Б.К. Канальная трассировка на основе генетических процедур. Известия ТРТУ, № 3, Таганрог, 1997. 53−60 с.
- Лебедев Б.К. Планирование СБИС методом генетического поиска. Известия ТРТУ. Интеллектуальные САПР. Таганрог, Изд-во ТРТУ, 1999, № 3.119−126 с
- Schnecke V., Vornberger O. A Genetic Algorithms for VLSI Design Automation. Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control, Plymouth, UK, March 1996. pp. 53−58.
- Батищев Д.И., Власов C.E., Булгаков И. В. Плотное размещение разногабаритных объектов на плоскости с помощью генетических алгоритмов. XXIII International School and Conference on Computer Aided Design. Yalta-Gurzuff, 2001. 354 c.
- Rahmani, A.T. and Ono N. A Genetic Algorithm for Channel Routing Problem, in Proc. 5th Intl. Conf. on GAs, 1993. pp. 494−498.
- Lieng J., Thulasiraman K. A Genetic Algorithm for Channel Routing in VLSI Circuits. Evolutionary Computation, 1(4), MIT, 1994. pp. 293−311.
- Cohoon J.P. and Paris W.D. Genetic placement. IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.6, № 6, 1987. pp. 956−964.
- Мелихов A.H., Берштейн Л. С., Курейчик B.M. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. 3 04 с.
- Мелихов А.Н., Берштейн JI.C. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов-на-Дону: издательство Ростовского университета, 1981. 112 с.
- Харари Ф. Теория графов. М.: Мир, 1973. 300 е., ил.
- Уилсон Р. Введение в теорию графов. М.: Мир, 1977. 208 с.
- Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.432 с.
- Оре О. Теория графов. М.: Наука, 1980. 356 с.
- Гатчин Ю.А., Коробейников А. Г. Методы представления математических моделей в САПР при концептуальном и инфологическом моделировании. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 35−41.
- Марченко А. «Современные проблемы автоматизации проектирования топологии СБИС», МЭС 2006
- J. Cong, С. Wu, 'Global Clustering-Based Performance-Driven Circuit Partitioning', Proc. ISPD, 2002.
- W.E. Donath et al, 'Timing Driven Placement Using Complete Path Delays', Proc. ACM/IEEE DAC, 1990.
- J. Minami, T. Koide, S. Wakabayashi, 'An Iterative Improvement Circuit Partitioning Algorithm under Path Delay Constraints', IEICE Trans. Fundamentals, Dec. 2000.
- S.-L Ou, M. Pedram, 'Timing-driven Partitioning Using Iterative Quadratic Programming', at http://atrak.usc.edu/~massoud/, see «Coming Attractions!», 2001.
- P. Zarkesh-Ha, J.A. Davis, J.D. Meindl, 'Prediction of Net-Length Distribution for Global Interconnects in a Heterogeneous System-on-a-Chip', IEEE Trans. VLSI Systems, Dec. 2000.
- Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. Москва, Радио и связь, 1990. 352 е.: ил.
- Деньдобренко Б.П., Малика А. С. Автоматизация проектирования радиоэлектронной аппаратуры. М., Высш. шк., 2002. 384 с.
- Thang Nguyen Bui, Byung-Ro Moon. «GRCA: A Hybrid Genetic Algorithm for Circuit Ratio-Cut Partitioning». IEEE Transactions on computer-aided design of integrated circuits and systems, vol.17, No.3, March 1998, pp. 193−204.
- Shihliang Ou and Massoud Pedram, «Timing-Driven Bipartitioning with Replication Using Iterative Quadratic Programming», ASPDAC, 2001.
- Dominic A. Antonelli, Danny Z. Chen, Timothy J. Dysart, Xiaobo S. Hundrew, B. Kahng Peter, M. Kogge Richard, C., Murphy Michael, T. Niemier, «Quantum-Dot Cellular Automata (QCA) Circuit Partitioning: Problem Modeling and Solutions», DAC, 2004
- Курейчик В.М. Оптимизация в САПР: Учебное пособие. Таганрог, ТРТУ, 1998.
- Лебедев Б.К. Интеллектуальные процедуры синтеза топологии СБИС, Таганрог: Изд-во ТРТУ, 2003. 108 с.
- S. Kirkpatrick, C.D. Gelatt, and М.Р. Vecchi. Optimization by simulated annealing. Science, 220(4598):671 680, 1983
- Емельянов B. B, Курейчик В. М., Курейчик B.B. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.
- Курейчик В.М. Генетические алгоритмы и их применение: Монография. Таганрог: Изд-во ТРТУ, 2002.
- Гладков Л.А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. / под ред. В. М. Курейчика. Учебное пособие. Ростов на — Дону: Ростиздат, 2006.
- Букатова И.Л. Эволюционное моделирование: идеи, основы теории, приложения. Москва, Знание, выпуск 10, 1981
- Cristinel Ababei, Kia Bazargan, «Statistical Timing Driven Partitioning for VLSI Circuits», 2002
- C.M. Fiduccia, R.M. Mattheyses, 'A Linear-Time Heuristic for Improving Network Partitions', Proc. ACM/IEEE DAC, 1982.
- Yongseok Cheon, Seokjin Lee, Martin D. F. Wong, «Stable Multiway Circuit Partitioning for ECO», 2003
- C. J. Alpert and S.-Z. Yao, «Spectral Partitioning: The More Eigenvectors, The Better,» Proc. ACM/IEEE Design Automation Conf., 1995, pp. 195 200.
- P. K. Chan, M. D. F. Schlag and J. Zien, «Spectral K-Way Ratio Cut Partitioning and Clustering,» IEEE Trans, on CAD 13(9), 1997, pp. 10 881 096.
- L. Hagen and A. B. Kahng, «Fast Spectral Methods for Ratio Cut Partitioning and Clustering,» Proc. IEEE Intl. Conf. on Computer-Aided Design, 2001, pp. 10−13.
- Jan-Yang Chang, Yu-Chen Liu, and Ting-Chi Wang «Faster and Better Spectral Algorithms for Multi-Way Partitioning», ASPDAC 1999
- Y.C. Wei, C.K. Cheng. «A two-level two-way Partitioning Algorithm», Tech. report CH2924−9, University of California, San Diego, IEEE, 1990
- C.J. Alpert, A.B. Kahng. «Geometric Embeddings for Faster and Better Multi-Way Netlist Partitioning», in 30th ACM/IEEE Design automation conference, 1993, pp. 743−748.
- G. Karypis. Multilevel hypergraph partitioning. In J. Cong and J. Shinnerl, editors, Multilevel Optimization Methods for VLSI, chapter 6. Kluwer Academic Publishers, Boston, MA, 2002.
- С. Alpert and A. Kahng. A hybrid multilevel/genetic approach for circuit partitioning. In Proceedings of the Fifth ACM/SIGDA Physical Design Workshop, pages 100−105, 2002.
- G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Application in vlsi domain. IEEE Transactions on VLSI Systems, 20(1), 1999. A short ersion appears in the proceedings ofDAC1997.
- Youssef Saab. A new effected and efficient multi-level partitioning algorithm: DATE, 2000.
- G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Application in VLSI domain. Design Automation Conference, pages 526−529,1997
- Navaratnasothie Selvakkumaran and George Karypis, «Multi-Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization», ICCAD 2003
- Cristinel Ababei, Navaratnasothie Selvakkumaran, Kia Bazargan, George Karypis, «Multi-objective Circuit Partitioning for Cutsize and Path-Based Delay Minimization», ICCAD 2002
- Курейчик В.В., Курейчик В. М. Об управлении на основе генетического поиска. Автоматика и телемеханика. РАН, № 10, Москва, 2001,-с.174−187.
- Kureichik V.V., Kureichik V.M., Genetic Algorithms. HG Verlag, Konstans, 2004
- Курейчик B.M., Лебедев Б. К., Гладков Л. А. и др. Разработка интеллектуальных систем проектирования на основе эволюционной адаптации // Отчёт по НИР (промежуточный). Депонир. в ВНТИ № ГР 01.9.60 004 346, М: 1998,43 стр.
- Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. Таганрог: изд-во ТРТУ, 2000. 192 с.
- Дуккардт А.Н., Лебедев Б. К. «Подход к решению задачи разбиения на основе квантовых алгоритмов», XI МНПК студентов и молодых ученых «Современные техника и технологии СТТ'2005» г. Томск
- Лебедев Б.К., Дуккардт А. Н., «Разбиение на основе комбинированных генетических процедур», Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТРТУ, 2006. № 8(63). С. 46−51
- Дуккардт А.Н., «Решение задачи разбиения на основе процедуры „Выбивания“», Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТРТУ, 2006. № 6. С. 6366
- Дуккардт А.Н., Лебедев Б. К. «Гибридный генетический алгоритм с элементами антимонопольного развития», Известия ТРТУ.
- Тематический выпуск «Интеллектуальные САПР».
- Таганрог: Изд-во ТРТУ, 2007. № 1. С. 86−91
- Хедрик Ф. Генетика популяций. М.: Техносфера, 2003.
- Редько В.Г. Эволюционная кибернетика. М.: Наука, 2001.
- Practical Handbook of Genetic Algorithms. Editor I. Chambers. T. l, Washington, USA, CRC Press, 1995.
- Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.2, Washington, USA, CRC Press, 1995.
- Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.3, Washington, USA, CRC Press, 1999.
- Касьянов B.H., Евстигнеев B.A. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.
- Holland, John Н., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.
- Wolfe G., Wong J.L. and Potkonjak M. Watermarking Graph Partitioning Solutions. IEEE Transactions on CAD of Integrated Circuits and systems, V. 21, № 10, October 2002, pp. 1196 1204.
- Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. -М.: Мир, 1985. 512 с.
- Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учеб. пособие / Под общ. ред. Останина А. Н. -Минск: Вышэйшая школа., 1989. 218 е.: ил.
- Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий. М.: Наука, 1971. 283 е.: ил.
- Митропольский А.К. Техника статистических исследований. М., «Наука», 1971.576 е.: ил
- Navaratnasothie, Selvakkumaran, Kia Bazargan, George Karypis. Multi-objective Circuit Partitioning for Cutsize and Path-Based Delay Minimization. ICCAD 2002.
- Yongseok Cheon Seokjin Lee Martin D. F. Wong. Stable Multiway Circuit Partitioning for ECO. ICCAD 2003.
- Alpert C.J. et all. Hypergraph Partitioning with Fixed Vertices. //V.19, № 2, February 2002, pp. 267 271.
- Мищенко M. H. Операторы мутации в эволюционных алгоритмах размещения. Перспективные информационные технологии интеллектуальные системы, № 4 (16), 2003. с.130−135.
- Глушань В.М. Графовые модели представления вычислительных алгоритмов. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2. М.: Физматлит, 2003, с. 133 — 138.
- Мак W.K. Mic Cut Partitioning With Functional Replication for Technology — Mapped Circuits Using Minimum Area Over hed. //V.21, № 4, april 2002, — pp. 491 — 496
- Курейчик B.B. Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. Таганрог: Изд-во ТРТУ, 2001.
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.М.: МЦНМО, 2000.
- Батищев Д.И., Коган Д. И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород, Нижегородский госуниверситет, 1994.