Síntesis booleana con programación genética paralela en CPU y GPU
La síntesis booleana o combinacional es un proceso mediante el cual se optimiza una red de puertas lógicas, con el fin de reducir su consumo, minimizar costos, minimizar área y aumentar el rendimiento a la hora de ser implementada. Por otra parte la programación genética es una alternativa important...
- Autores:
-
Pedraza, Cesar
Oyaga, Jaime
Gómez, Ricardo
- Tipo de recurso:
- Article of journal
- Fecha de publicación:
- 2013
- Institución:
- Universidad de San Buenaventura
- Repositorio:
- Repositorio USB
- Idioma:
- spa
- OAI Identifier:
- oai:bibliotecadigital.usb.edu.co:10819/28642
- Acceso en línea:
- https://hdl.handle.net/10819/28642
https://doi.org/10.21500/01247492.1325
- Palabra clave:
- Programación paralela
síntesis booleana
GPU
algoritmo evolutivo
- Rights
- openAccess
- License
- Ingenium - 2015
| id |
SANBUENAV2_8e922a7f888df35a3a2c7bf3ae1a8017 |
|---|---|
| oai_identifier_str |
oai:bibliotecadigital.usb.edu.co:10819/28642 |
| network_acronym_str |
SANBUENAV2 |
| network_name_str |
Repositorio USB |
| repository_id_str |
|
| dc.title.spa.fl_str_mv |
Síntesis booleana con programación genética paralela en CPU y GPU |
| dc.title.translated.eng.fl_str_mv |
Síntesis booleana con programación genética paralela en CPU y GPU |
| title |
Síntesis booleana con programación genética paralela en CPU y GPU |
| spellingShingle |
Síntesis booleana con programación genética paralela en CPU y GPU Programación paralela síntesis booleana GPU algoritmo evolutivo |
| title_short |
Síntesis booleana con programación genética paralela en CPU y GPU |
| title_full |
Síntesis booleana con programación genética paralela en CPU y GPU |
| title_fullStr |
Síntesis booleana con programación genética paralela en CPU y GPU |
| title_full_unstemmed |
Síntesis booleana con programación genética paralela en CPU y GPU |
| title_sort |
Síntesis booleana con programación genética paralela en CPU y GPU |
| dc.creator.fl_str_mv |
Pedraza, Cesar Oyaga, Jaime Gómez, Ricardo |
| dc.contributor.author.spa.fl_str_mv |
Pedraza, Cesar Oyaga, Jaime Gómez, Ricardo |
| dc.subject.spa.fl_str_mv |
Programación paralela síntesis booleana GPU algoritmo evolutivo |
| topic |
Programación paralela síntesis booleana GPU algoritmo evolutivo |
| description |
La síntesis booleana o combinacional es un proceso mediante el cual se optimiza una red de puertas lógicas, con el fin de reducir su consumo, minimizar costos, minimizar área y aumentar el rendimiento a la hora de ser implementada. Por otra parte la programación genética es una alternativa importante para generar estructuras de hardware interesantes y eficientes. Se ha demostrado que los algoritmos evolutivos (AE) tienen mejor rendimiento si se implementan en sistemas paralelos. Este artículo presenta la implementación de un algoritmo genético paralelo (PGP) para realizar síntesis booleana en una plataforma basada en CPU-GPU. Esta implementación emplea el modelo de islas, el cual permite la evolución paralela e independiente del PGP a través de las múltiples unidades de procesamiento de la GPU y los múltiples núcleos de un procesador de última generación. Se probaron diferentes alternativas de mapeo del PGP en la plataforma en orden de optimizar el tiempo de respuesta. Como resultado se muestra una aceleración superiora41. |
| publishDate |
2013 |
| dc.date.accessioned.none.fl_str_mv |
2013-01-28T00:00:00Z 2025-08-22T14:06:21Z |
| dc.date.available.none.fl_str_mv |
2013-01-28T00:00:00Z 2025-08-22T14:06:21Z |
| dc.date.issued.none.fl_str_mv |
2013-01-28 |
| dc.type.spa.fl_str_mv |
Artículo de revista |
| dc.type.coar.fl_str_mv |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| dc.type.coar.spa.fl_str_mv |
http://purl.org/coar/resource_type/c_6501 |
| dc.type.coarversion.spa.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| dc.type.content.spa.fl_str_mv |
Text |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/article |
| dc.type.local.eng.fl_str_mv |
Journal article |
| dc.type.version.spa.fl_str_mv |
info:eu-repo/semantics/publishedVersion |
| format |
http://purl.org/coar/resource_type/c_6501 |
| status_str |
publishedVersion |
| dc.identifier.doi.none.fl_str_mv |
10.21500/01247492.1325 |
| dc.identifier.issn.none.fl_str_mv |
0124-7492 |
| dc.identifier.uri.none.fl_str_mv |
https://hdl.handle.net/10819/28642 |
| dc.identifier.url.none.fl_str_mv |
https://doi.org/10.21500/01247492.1325 |
| identifier_str_mv |
10.21500/01247492.1325 0124-7492 |
| url |
https://hdl.handle.net/10819/28642 https://doi.org/10.21500/01247492.1325 |
| dc.language.iso.spa.fl_str_mv |
spa |
| language |
spa |
| dc.relation.bitstream.none.fl_str_mv |
https://revistas.usb.edu.co/index.php/Ingenium/article/download/1325/1116 |
| dc.relation.citationedition.spa.fl_str_mv |
Núm. 27 , Año 2013 : INGENIUM |
| dc.relation.citationendpage.none.fl_str_mv |
130 |
| dc.relation.citationissue.spa.fl_str_mv |
27 |
| dc.relation.citationstartpage.none.fl_str_mv |
117 |
| dc.relation.citationvolume.spa.fl_str_mv |
14 |
| dc.relation.ispartofjournal.spa.fl_str_mv |
Ingenium |
| dc.relation.references.spa.fl_str_mv |
Ch. Darwin, On the origin of species by means of natural selection, or the preservation of favoured races in the struggle for life. New York: D. Appleton, 1859. E. Cantú-Paz, Efficient and accurate parallel genetic algorithms. Estados Unidos, 2001. S. M. Cheang, K. H. Lee, y K. S. Leung, «Applying Genetic Parallel Programming to Synthesize Combinational Logic Circuits». Evolutionary Computation, IEEE Transactions on, Volumen 11. pp. 503 – 520, 2007. L. Jozwiak, N. Ederveen, y A. Postula, «Solving synthesis problems with genetic algorithms». Euromicro Conference, Volumen 1, pp.10001, 1998. N. Nadia, A. Ajith, y L. M. de Macedo, Genetic Systems Programming, ed. Springer, 2006. A. Stoica, «Evolvable hardware: from on-chip circuit synthesis to evolvable space systems». Multiple-Valued Logic, (ISMVL 2000) Proceedings. 30th IEEE International Symposium on, 2000: p. 161 - 169, 2000 A. Stoica, Evolvable Hardware for Autonomous Systems. CEC Tutorial, 2004. [8] A. Thompson, «An Evolved Circuit, Intrinsic in Silicon, Entwined with Physics». Lecture notes in computer science, pp. 390- 405, 1997. T. Kalganova, «An Extrinsic Function-Level Evolvable Hardware Approach», Lecture notes in computer science, Berlín:Springer, pp.60-75, 2000. T. Higuchi, T. Niwa, T. Tanaka, H. H. Iba, H. de Garis, y F. Tatsumi, «Evolving hardware with genetic learning: a first step towards building a Darwin machine» Proceedings of the second international conference, pp. 417-424, 1993. S-J. Chang, H-S. Hou, y Y-K. Su, «Automated synthesis of passive filter circuits including parasitic effects by genetic programming ». Microelectronics Journal, volumen 37, pp. 792 – 799, 2006. D. Ashlock, Evolutionary Computation for Modeling and Optimization. Guelp, Ontario: Springer, 2005, 571p. L. Sekanina, Evolvable components, from theory to hardware implementations, Natural computing series, República Checa: Springer, 1998. M. Mitchell, An introduction to genetic algorithms. Massachusetts: The MIT Press, 1998. D. Goldberg, y J. Holland, Genetic Algorithms and Machine Learning. Machine Learning, Paises bajos: Springer, 1988. 130 J. Koza, F. Bennett, D. Andre, y M. Keane, Genetic programming III: darwinian invention and problem solving [Book Review]. Evolutionary Computation, 1999. F. Rothlauf, Representations for Genetic and Evolutionary Algorithms, ed. Springer, 2006. J. C. Pedraz, y C. Córdoba, «Implementación de un algoritmo genético paralelo sobre hardware gráfico de última generación». recolecta.net. 2005. A. Hernández, C. Coello, y B. Buckles, «A genetic programming approach to logic function synthesis by means of multiplexers». Proceedings of the First NASA/DoD Workshop on Evolvable, pp. 46-53, 1999. T. Higuchi, y B. Manderick, «Hardware realizations of evolutionary algorithms». Evolutionary Computation 2. (Noviembre), pp. 253 -263, 2000. J. F. Miller, y S. Harding, «Cartesian genetic programming». Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference, pp. 3489-3512, 2009. J. Alander, «On optimal population size of genetic algorithms». CompEuro’92. Computer Systems and Software Engineering’ proccedings, pp 65-70, 1992. [23] S. Kirkpatrick, C. Gelatt,. y M. Vecchi, «Optimization by Simulated Annealing». Science, Volumen 220, Número 4598, pp. 671-680, 1983. R. Krohling, Y. Zhou, y A. Tyrrell, «Evolving FPGA-based robot controllers using an evolutionary algorithm» 1st International Conference on Artificial Immune Systems, 2002. J. Miller, y P. Thomson, «Aspects of Digital Evolution: Geometry and Learning». Lecture notes in computer science, 1998. C. Di Chio, S. Cagnoni, C. Cotta, M. Ebner, A. Ekárt, A. Esparcia-Alcazar, et al. Applications of Evolutionary Computation. Berlin, Heidelberg: Springer, Volumen 6024, 2010, pp. 442-451. T. V. Luong, N. Melab, y E. G. Talbi, «GPU-based island model for evolutionary algorithms». Proceedings of the 12th anual conference on Genetic and evolutionary computation - GECCO ’10. New York, USA: ACM Press, p. 1089, 2010. M. Sussman, W. Crutchfield, y M. Papakipos, «Pseudorandom number generation on the GPU». Proceedings of the 21st ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, pp. 87-94, 2006. J. Charles, P. Jassi, N.S. Ananth, A. Sadat, y A. Fedorova, Evaluation of the Intel Core i7 Turbo Boost feature. In: 2009 IEEE International Simposium on Workload Characterization (IISWC), pp. 188-197. IEEE (2009). DOI 10.1109 C. Pedraza, E. Castillo, J. Castillo, C. Camarero, J. Bosque, J. Martinez, y R. Menendez, «Cluster architecture based on low cost reconfigurable hardware». International conference on field programmable logic and applications, FPL. Heidelberg, Alemania, pp. 595 – 598, 2008. |
| dc.rights.spa.fl_str_mv |
Ingenium - 2015 |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.coar.spa.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| dc.rights.uri.spa.fl_str_mv |
https://creativecommons.org/licenses/by-nc-sa/4.0/ |
| rights_invalid_str_mv |
Ingenium - 2015 http://purl.org/coar/access_right/c_abf2 https://creativecommons.org/licenses/by-nc-sa/4.0/ |
| eu_rights_str_mv |
openAccess |
| dc.format.mimetype.spa.fl_str_mv |
application/pdf |
| dc.publisher.spa.fl_str_mv |
Universidad San Buenaventura - USB (Colombia) |
| dc.source.spa.fl_str_mv |
https://revistas.usb.edu.co/index.php/Ingenium/article/view/1325 |
| institution |
Universidad de San Buenaventura |
| bitstream.url.fl_str_mv |
https://bibliotecadigital.usb.edu.co/bitstreams/ea71b150-9211-439c-81d5-2af1c6f9505d/download |
| bitstream.checksum.fl_str_mv |
41671b94ef1d49e74518034ebf544410 |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 |
| repository.name.fl_str_mv |
Repositorio Institucional Universidad de San Buenaventura Colombia |
| repository.mail.fl_str_mv |
bdigital@metabiblioteca.com |
| _version_ |
1851053631452741632 |
| spelling |
Pedraza, CesarOyaga, JaimeGómez, Ricardo2013-01-28T00:00:00Z2025-08-22T14:06:21Z2013-01-28T00:00:00Z2025-08-22T14:06:21Z2013-01-28La síntesis booleana o combinacional es un proceso mediante el cual se optimiza una red de puertas lógicas, con el fin de reducir su consumo, minimizar costos, minimizar área y aumentar el rendimiento a la hora de ser implementada. Por otra parte la programación genética es una alternativa importante para generar estructuras de hardware interesantes y eficientes. Se ha demostrado que los algoritmos evolutivos (AE) tienen mejor rendimiento si se implementan en sistemas paralelos. Este artículo presenta la implementación de un algoritmo genético paralelo (PGP) para realizar síntesis booleana en una plataforma basada en CPU-GPU. Esta implementación emplea el modelo de islas, el cual permite la evolución paralela e independiente del PGP a través de las múltiples unidades de procesamiento de la GPU y los múltiples núcleos de un procesador de última generación. Se probaron diferentes alternativas de mapeo del PGP en la plataforma en orden de optimizar el tiempo de respuesta. Como resultado se muestra una aceleración superiora41.application/pdf10.21500/01247492.13250124-7492https://hdl.handle.net/10819/28642https://doi.org/10.21500/01247492.1325spaUniversidad San Buenaventura - USB (Colombia)https://revistas.usb.edu.co/index.php/Ingenium/article/download/1325/1116Núm. 27 , Año 2013 : INGENIUM1302711714IngeniumCh. Darwin, On the origin of species by means of natural selection, or the preservation of favoured races in the struggle for life. New York: D. Appleton, 1859.E. Cantú-Paz, Efficient and accurate parallel genetic algorithms. Estados Unidos, 2001.S. M. Cheang, K. H. Lee, y K. S. Leung, «Applying Genetic Parallel Programming to Synthesize Combinational Logic Circuits». Evolutionary Computation, IEEE Transactions on, Volumen 11. pp. 503 – 520, 2007.L. Jozwiak, N. Ederveen, y A. Postula, «Solving synthesis problems with genetic algorithms». Euromicro Conference, Volumen 1, pp.10001, 1998.N. Nadia, A. Ajith, y L. M. de Macedo, Genetic Systems Programming, ed. Springer, 2006.A. Stoica, «Evolvable hardware: from on-chip circuit synthesis to evolvable space systems». Multiple-Valued Logic, (ISMVL 2000) Proceedings. 30th IEEE International Symposium on, 2000: p. 161 - 169, 2000A. Stoica, Evolvable Hardware for Autonomous Systems. CEC Tutorial, 2004. [8] A. Thompson, «An Evolved Circuit, Intrinsic in Silicon, Entwined with Physics». Lecture notes in computer science, pp. 390- 405, 1997.T. Kalganova, «An Extrinsic Function-Level Evolvable Hardware Approach», Lecture notes in computer science, Berlín:Springer, pp.60-75, 2000.T. Higuchi, T. Niwa, T. Tanaka, H. H. Iba, H. de Garis, y F. Tatsumi, «Evolving hardware with genetic learning: a first step towards building a Darwin machine» Proceedings of the second international conference, pp. 417-424, 1993.S-J. Chang, H-S. Hou, y Y-K. Su, «Automated synthesis of passive filter circuits including parasitic effects by genetic programming ». Microelectronics Journal, volumen 37, pp. 792 – 799, 2006.D. Ashlock, Evolutionary Computation for Modeling and Optimization. Guelp, Ontario: Springer, 2005, 571p.L. Sekanina, Evolvable components, from theory to hardware implementations, Natural computing series, República Checa: Springer, 1998.M. Mitchell, An introduction to genetic algorithms. Massachusetts: The MIT Press, 1998.D. Goldberg, y J. Holland, Genetic Algorithms and Machine Learning. Machine Learning, Paises bajos: Springer, 1988. 130J. Koza, F. Bennett, D. Andre, y M. Keane, Genetic programming III: darwinian invention and problem solving [Book Review]. Evolutionary Computation, 1999.F. Rothlauf, Representations for Genetic and Evolutionary Algorithms, ed. Springer, 2006.J. C. Pedraz, y C. Córdoba, «Implementación de un algoritmo genético paralelo sobre hardware gráfico de última generación». recolecta.net. 2005.A. Hernández, C. Coello, y B. Buckles, «A genetic programming approach to logic function synthesis by means of multiplexers». Proceedings of the First NASA/DoD Workshop on Evolvable, pp. 46-53, 1999.T. Higuchi, y B. Manderick, «Hardware realizations of evolutionary algorithms». Evolutionary Computation 2. (Noviembre), pp. 253 -263, 2000.J. F. Miller, y S. Harding, «Cartesian genetic programming». Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference, pp. 3489-3512, 2009.J. Alander, «On optimal population size of genetic algorithms». CompEuro’92. Computer Systems and Software Engineering’ proccedings, pp 65-70, 1992. [23] S. Kirkpatrick, C. Gelatt,. y M. Vecchi, «Optimization by Simulated Annealing». Science, Volumen 220, Número 4598, pp. 671-680, 1983.R. Krohling, Y. Zhou, y A. Tyrrell, «Evolving FPGA-based robot controllers using an evolutionary algorithm» 1st International Conference on Artificial Immune Systems, 2002.J. Miller, y P. Thomson, «Aspects of Digital Evolution: Geometry and Learning». Lecture notes in computer science, 1998.C. Di Chio, S. Cagnoni, C. Cotta, M. Ebner, A. Ekárt, A. Esparcia-Alcazar, et al. Applications of Evolutionary Computation. Berlin, Heidelberg: Springer, Volumen 6024, 2010, pp. 442-451.T. V. Luong, N. Melab, y E. G. Talbi, «GPU-based island model for evolutionary algorithms». Proceedings of the 12th anual conference on Genetic and evolutionary computation - GECCO ’10. New York, USA: ACM Press, p. 1089, 2010.M. Sussman, W. Crutchfield, y M. Papakipos, «Pseudorandom number generation on the GPU». Proceedings of the 21st ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, pp. 87-94, 2006.J. Charles, P. Jassi, N.S. Ananth, A. Sadat, y A. Fedorova, Evaluation of the Intel Core i7 Turbo Boost feature. In: 2009 IEEE International Simposium on Workload Characterization (IISWC), pp. 188-197. IEEE (2009). DOI 10.1109C. Pedraza, E. Castillo, J. Castillo, C. Camarero, J. Bosque, J. Martinez, y R. Menendez, «Cluster architecture based on low cost reconfigurable hardware». International conference on field programmable logic and applications, FPL. Heidelberg, Alemania, pp. 595 – 598, 2008.Ingenium - 2015info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2https://creativecommons.org/licenses/by-nc-sa/4.0/https://revistas.usb.edu.co/index.php/Ingenium/article/view/1325Programación paralelasíntesis booleanaGPUalgoritmo evolutivoSíntesis booleana con programación genética paralela en CPU y GPUSíntesis booleana con programación genética paralela en CPU y GPUArtículo de revistahttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1http://purl.org/coar/version/c_970fb48d4fbd8a85Textinfo:eu-repo/semantics/articleJournal articleinfo:eu-repo/semantics/publishedVersionPublicationOREORE.xmltext/xml2605https://bibliotecadigital.usb.edu.co/bitstreams/ea71b150-9211-439c-81d5-2af1c6f9505d/download41671b94ef1d49e74518034ebf544410MD5110819/28642oai:bibliotecadigital.usb.edu.co:10819/286422025-08-22 09:06:21.951https://creativecommons.org/licenses/by-nc-sa/4.0/https://bibliotecadigital.usb.edu.coRepositorio Institucional Universidad de San Buenaventura Colombiabdigital@metabiblioteca.com |