Arquitetura Paralela Reconfigurável em FPGA para Implementação de Operadores Elementares da Aritmética Intervalar
Resumo
Diversas áreas do conhecimento necessitam de meios para tornar os sistemas de computação mais eficientes em termos de diminuição de tempo de resposta. De modo particular, os programas que empregam rotinas baseadas em aritmética intervalar carecem de redução do tempo no processamento dos cálculos, pois as operações matemáticas nestes algoritmos levam em conta os limites dos custo intervalos de computacional. Diferentes aplicações deixam de usar algoritmos intervalares porque o compromisso do sistema com o tempo de execução é fator determinante ao problema. Desta forma, para favorecer o desempenho de aplicações que utilizam a aritmética intervalar, este trabalho apresenta a utilização de um dispositivo eletrônico com arquitetura reconfigurável para paralelizar o cômputo de operações aritméticas elementares. Foram analisados o uso do paralelismo em conjunto com a computação reconfigurável, com o objetivo de acelerar algoritmos da aritmética intervalar. Os diferentes ganhos de desempenho e os respectivos consumos de recursos produzidos pela de flexibilidade reconfiguração da arquitetura proposta comprovam que o uso de um Field Programmable Gate Array seria uma possível solução, visto que o mesmo associa a flexibilidade do software com o desempenho hardware.
Palavras-chave:
aritmética intervalar, arquitetura reconfigurável, FPGA
Referências
PITAC Computational Science: Ensuring America's Competitivene. National Coordination Office for Information Tecnology Research & Development. 4201 Wilson Boulevard, Suite II - 405. Arlington. 2005.
R. H. Landau, R. Wangberg, K. Augustson, M.J. Páez, C. C. Bordeianu, C. Barnes. A First Course in Scientific Computing. Copyright c 2005 by Princeton University Press. Princeton and Oxford. 41 William Street, Princeton, New Jersey 08540 3 Market Place, Woodstock, Oxfordshire OX20 1SY.
R. M. P Trindade. Uma Fundação Matemática para Processamento Digital de Sinais Intervalares. Natal, RN. Universidade Federal do rio Grande do Norte: Centro de Tecnologia Programa de Pós Graduação em Engenharia Elétrica e de Computação. Tese de Doutorado, 2009
R. Moore. Dimensional Analysis. E. Cliffs, Ed. New Jersey: Prentice Hall, 1966.
L. A. Zadeh. Fuzzy sets. Information and Control, Prentice Hall PTR Upper Saddle River, NJ, USA, v. 8, n. 3, p. 338{353, 1965. ISSN 00199958.
L. A. Zadeh. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems, v. 100, p. 9{34, 1999. ISSN 01650114.
Systems, v. 100, p. 9{34, 1999. ISSN 01650114.Silveira, M. M. M. T. Teoria Fuzzy Intervalar: Uma Proposta de Integração da Teoria Fuzzy à Computação Intervalar. Master’s thesis, UFRN, Natal - RN, 2002.
R.E. Moore. Interval Arithmetic and Automatic Error Analysis in Digital Computing. Tese de Doutado, Department of Mathematics, Stanford University, Stanford California. 1962. NR – 0440211.
C. P. Callender, C. F. N. Cowan. Implementation of Numerically Robust Fast Recursive Leat Squares Adaptive Filters Using Interval Arithmetic. ELECTRONICS LETTERS 26th March 1992 Vol. 28 No. 7.
Garrozi. A Aritmética Intervalar como Ferramenta para a Solução de Problemas de Computação Científica. In: Revista Eletrônica de Iniciação Científica - Sociedade Brasileira de Computação, Artigos de pesquisa e Desenvolvimento, ano II, 2002, n 1, Março.
A. W. Lodwick. A Comparison of Interval Analysis Using Constraint Interval Arithmetic and Fuzzy Interval Analysis Using Gradual Numbers. Fuzzy Information Processing Society, 2008. NAFIPS 2008. IEEE. Annual Meeting of the North American Digital Object Identifier: 10.1109/NAFIPS.2008.4531302 Publication Year: 2008, Page(s): 1 – 6.
C. A. Holbig. Ambiente de Alto Desempenho com Alta Exatidão para a Resolução de Problemas. 2005. Tese (Instituto de Informática/Programa de PósGraduação em Computação) – Universidade Federal do Rio Grande do Sul, Porto Alegre.
A. Amaricai, M. Vladutiu, L. Prodan, M. Udrescu. Design of Addition and Multiplication Units for High Performance Interval Arithmetic Processor. Advanced Computing Systems and Architectures (ACSA) Research Group, Computer Science and Engineering Department, “Politehnica” University of Timisoara.IEEE, 2007. DDECS '07. IEEE DOI: 10.1109/DDECS.2007.4295285.
R. B. Kearfott. Interval Computations: Introduction, Uses, and Resources. Department of Mathematics University of Southwestern Louisiana U.S.L. 1996. Box 4-1010, Lafayette, LA 70504-1010 USA email: rbk@usl.edu.
R. E. Moore, R. B Kearfott, M. J Cloud. Introduction to Interval Analysis. SIAM (Society for Industrial and Applied Mathematics Philadelphia). 2009. ISBN 978-0-898716-69-6.Page(s): 19-28 and 157-170.
G. Shan, Y. Baoming, Y. Qiang. Interval Analysis and Its Applications to Control Problems. Education and Information Technology, 2010 International Conference. Vol. 1. IEEE Conference Publication. Page(s): V1-213 - V1-218. DOI 10.1109/ICEIT.2010.5607749.
J. Ninin, F. Messine, P. Hansen. A Reliable Affine Relaxation Method for Global Optimization. October 23, 2012. ed: Montréal : Groupe d'études et de recherche en analyse des décisions, 2010. Cahiers du GÉRAD, G-2010-31.
A. F. Finger, A. B. Loreto, M. A. Campos, F. R. G. Varjão, M. G. dos Santos. The Computational Complexity of Problems to Compute Intervals Wrappers for Random Variables Uniform, Exponential and Pareto. 978– 1–4673–0793–2/ c 2012 IEEE
F. T. Santana, F. L. Santana, A. D. D. Neto, R. H. N. Santiago. Sinais e Sistemas Definidos Sobre Aritmética Intervalar Complexa. Tema: Tendências em Matemática Aplicada e Computacional, 13, Nº. 1 (2012), 85-96. DOI: 10.5540/tema. 2012.013.01.0085. © Uma Publicação da Sociedade Brasileira de Matemática Aplicada e Computacional.
E. J. Rothwell, J. Edward, M. J. Cloud. Automatic Error Analysis Using Intervals. – IEEE Transations on Education, vol.55, nº 1, February 2012.0018-9359. IEEE DOI 10.1109/TE.2011.2109722.
Z. Zhou, Z. Liu, B. Zeng, Y. Pang, L. He. Application of the Interval Arithmetic in Reliability Analysis of Distribution System. Quality, Reliability, Risk, Maintenance, and Safety Engineering (ICQR2MSE), 2012 International Conference on. IEEE, 2012.
K. Compton, S. Hauck. Reconfigurable Computing: A Survey of Systems and Software, ACM Computing Survey, 2002. Vol. 34, n. 2, p. 171-210
D. Patterson, J. Hennessy. Computer Organization and design: the hardware/software interface. [S.I.]: Morgan Kaufmann Pub, 2009.
B. Harikrishna, S. Ravi. Intelligent Systems and Control (ISCO), 2013 7th International Conference on Digital Object Identifier: 10.1109/ISCO.2013.6481160 Publication Year: 2013, Page(s): 265 – 270. IEEE Conference Publications.
P. Bleisch, D. Morgan, D. Youngwith. D. The State of ReConfigurable Computing, 1995.
I. Shiliarova, A.B. Ferrari. Introdução à computação reconfigurável. Portugal: Revista DETUA, 2003.
A. Dehon. The Density Advantage of Configurable Computing. In: IEEE Computer. Vol. 33, No. 4. 2000. Page(s): 41 – 49.
C. A. P. S Martins, E. D. M. Ordonez, J. B. T. Corrêa, M. B. Carvalho. Computação Reconfigurável: Conceitos, Tendências e Aplicações. In: XXII Jornada de Atualização em Informática (JAI) - Livro Texto. Campinas: Sociedade Brasileira de Computação, 2003. v. XXII, p. 339- 388.
R. Shettar, R. M. Banakar, P. S. V. Nataraj. Implementation of Interval Arithmetic Algorithms on FPGAs. International Conference on Computational Intelligence and Multimedia Applications 2007. 0-7695- 3050-8/07 © 2007 IEEE DOI 10.1109/ICCIMA.2007.60196.
H. Ratsche, R. Rokne. New Computer Methods for Global Optimization. Ellis Horwood, 2007.
J. Villasenor, W. H. Mangione-Smith. Configurable Computing, Scientific American, Junho 1997. p. 54-59.
S. Hauck, A. Dehon.Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation, Morgan Kaufmann/Elsevier, 2008.
L. Bauer, C. Braun, M.E. Imhof, M.A. Kochte, Zhang Hongyan, H. Wunderlich, J. Henkel. Adaptive Hardware and Systems (AHS), 2012 NASA/ESA Conference on Digital Object dentifier: 10.1109/AHS.2012.6268667.Publication Year: 2012, Page(s): 38-45 Cited by 1. IEEE CONFERENCE PUBLICATIONS.
D. Llamocca, M. Pattichis, Circuits and Systems for Video Technology, IEEE Transactions on Volume: 23, Issue: 3.Digital Object Identifier: 10.1109/TCSVT.2012.2210664 Publication Year: 2013, Page(s): 488 – 502. IEEE JOURNALS & MAGAZINES
R. Harold. Review of "Highly parallel computing".Lorin IBM Thornwood Education Center, Thornwood, New York. Journal. IBM Systems Journal, archive. Vol 29. Issue 1. January 1990. Pg. 165 -166. IBM Corp. Riverton, NJ, USA.
R. Kumar, D. Marinov, D. Padua, M. Parthasarathy, S. Patel, D. Roth, J Torrellas, J. Parallel Computing Research at Illinois the UPCRC Agenda. (2008).
J. Castillo, J. L. Bosque, E. Castillo, P. Huerta, J. Martinez. Hardware accelerated Monte Carlo financial simulation over low cost FPGA cluster. Parallel and Distributed Processing Symposium, Internacional, vol.0. pgs. 1 – 8, 2009.
Leandro, A.J.M. Explorando Linhas de Execução Paralelas com Programação Orientada por Fluxo de Dados. Tese. Universidade Federal do Rio de Janeiro. UFRJ/COPPE . Outubro 2011..
R. Shettar, R. M. Banakar, P. S. V. Nataraj. Design and Implementation of Interval Arithmetic Algorithms. International Conference on Industrial and Information Systems, ICIIS 2006, 8 - 11 August 2006, Sri Lanka. 1- 4244-0322-7/06/ c2006IEE.
G.C. P Duarte; B.R.C. Bedregal. Introdução à Matemática Financeira. Intervalar: Análise Intervalar de Investimentos. Natal, RN. Sociedade Brasileira de Matemática Aplicada e Computacional. Depto de Informática e Matemática Aplicada, CCET, UFRN, Março, 2009.
J. Hormigo; J. Villaiba; E. Zapata. Arithmetic Unit for the Computation of Interval Elementary Functions. Dept. of Computer Architecture University of Malaga. DOI: 10.1109/EURMIC.1999.794447. 1999, p: 63 - 66 vol.1. IEEE CONFERENCE PUBLICATIONS.
M. Shahbazi; P. Poure; S. Saadate;M. R. Zolghadri.Fault Tolerant Five Leg Converter Topology With FPGA Based Reconfigurable Control. Industrial Electronics, IEEE Transactions on Volume: 60, Issue: 6 Digital Object Identifier: 10.1109/TIE.2012.2191754 Publication Year: 2013, Page(s): 2284 – 2294. IEEE Journals & Magazines.
Benhamou; W.J. Older; A. Vellino. Constraint Logic Programming on Boolean, Integer and Real Intervals. Journal of Symbolic Computing. May 10. 1994. (Submitted).
B. Catazaro; B. Nelson.Higher Radix Floating-Point Representations for FPGA-Based Arithmetic. Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines.2005. Page(s): 161 – 170.
R. H. Landau, R. Wangberg, K. Augustson, M.J. Páez, C. C. Bordeianu, C. Barnes. A First Course in Scientific Computing. Copyright c 2005 by Princeton University Press. Princeton and Oxford. 41 William Street, Princeton, New Jersey 08540 3 Market Place, Woodstock, Oxfordshire OX20 1SY.
R. M. P Trindade. Uma Fundação Matemática para Processamento Digital de Sinais Intervalares. Natal, RN. Universidade Federal do rio Grande do Norte: Centro de Tecnologia Programa de Pós Graduação em Engenharia Elétrica e de Computação. Tese de Doutorado, 2009
R. Moore. Dimensional Analysis. E. Cliffs, Ed. New Jersey: Prentice Hall, 1966.
L. A. Zadeh. Fuzzy sets. Information and Control, Prentice Hall PTR Upper Saddle River, NJ, USA, v. 8, n. 3, p. 338{353, 1965. ISSN 00199958.
L. A. Zadeh. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems, v. 100, p. 9{34, 1999. ISSN 01650114.
Systems, v. 100, p. 9{34, 1999. ISSN 01650114.Silveira, M. M. M. T. Teoria Fuzzy Intervalar: Uma Proposta de Integração da Teoria Fuzzy à Computação Intervalar. Master’s thesis, UFRN, Natal - RN, 2002.
R.E. Moore. Interval Arithmetic and Automatic Error Analysis in Digital Computing. Tese de Doutado, Department of Mathematics, Stanford University, Stanford California. 1962. NR – 0440211.
C. P. Callender, C. F. N. Cowan. Implementation of Numerically Robust Fast Recursive Leat Squares Adaptive Filters Using Interval Arithmetic. ELECTRONICS LETTERS 26th March 1992 Vol. 28 No. 7.
Garrozi. A Aritmética Intervalar como Ferramenta para a Solução de Problemas de Computação Científica. In: Revista Eletrônica de Iniciação Científica - Sociedade Brasileira de Computação, Artigos de pesquisa e Desenvolvimento, ano II, 2002, n 1, Março.
A. W. Lodwick. A Comparison of Interval Analysis Using Constraint Interval Arithmetic and Fuzzy Interval Analysis Using Gradual Numbers. Fuzzy Information Processing Society, 2008. NAFIPS 2008. IEEE. Annual Meeting of the North American Digital Object Identifier: 10.1109/NAFIPS.2008.4531302 Publication Year: 2008, Page(s): 1 – 6.
C. A. Holbig. Ambiente de Alto Desempenho com Alta Exatidão para a Resolução de Problemas. 2005. Tese (Instituto de Informática/Programa de PósGraduação em Computação) – Universidade Federal do Rio Grande do Sul, Porto Alegre.
A. Amaricai, M. Vladutiu, L. Prodan, M. Udrescu. Design of Addition and Multiplication Units for High Performance Interval Arithmetic Processor. Advanced Computing Systems and Architectures (ACSA) Research Group, Computer Science and Engineering Department, “Politehnica” University of Timisoara.IEEE, 2007. DDECS '07. IEEE DOI: 10.1109/DDECS.2007.4295285.
R. B. Kearfott. Interval Computations: Introduction, Uses, and Resources. Department of Mathematics University of Southwestern Louisiana U.S.L. 1996. Box 4-1010, Lafayette, LA 70504-1010 USA email: rbk@usl.edu.
R. E. Moore, R. B Kearfott, M. J Cloud. Introduction to Interval Analysis. SIAM (Society for Industrial and Applied Mathematics Philadelphia). 2009. ISBN 978-0-898716-69-6.Page(s): 19-28 and 157-170.
G. Shan, Y. Baoming, Y. Qiang. Interval Analysis and Its Applications to Control Problems. Education and Information Technology, 2010 International Conference. Vol. 1. IEEE Conference Publication. Page(s): V1-213 - V1-218. DOI 10.1109/ICEIT.2010.5607749.
J. Ninin, F. Messine, P. Hansen. A Reliable Affine Relaxation Method for Global Optimization. October 23, 2012. ed: Montréal : Groupe d'études et de recherche en analyse des décisions, 2010. Cahiers du GÉRAD, G-2010-31.
A. F. Finger, A. B. Loreto, M. A. Campos, F. R. G. Varjão, M. G. dos Santos. The Computational Complexity of Problems to Compute Intervals Wrappers for Random Variables Uniform, Exponential and Pareto. 978– 1–4673–0793–2/ c 2012 IEEE
F. T. Santana, F. L. Santana, A. D. D. Neto, R. H. N. Santiago. Sinais e Sistemas Definidos Sobre Aritmética Intervalar Complexa. Tema: Tendências em Matemática Aplicada e Computacional, 13, Nº. 1 (2012), 85-96. DOI: 10.5540/tema. 2012.013.01.0085. © Uma Publicação da Sociedade Brasileira de Matemática Aplicada e Computacional.
E. J. Rothwell, J. Edward, M. J. Cloud. Automatic Error Analysis Using Intervals. – IEEE Transations on Education, vol.55, nº 1, February 2012.0018-9359. IEEE DOI 10.1109/TE.2011.2109722.
Z. Zhou, Z. Liu, B. Zeng, Y. Pang, L. He. Application of the Interval Arithmetic in Reliability Analysis of Distribution System. Quality, Reliability, Risk, Maintenance, and Safety Engineering (ICQR2MSE), 2012 International Conference on. IEEE, 2012.
K. Compton, S. Hauck. Reconfigurable Computing: A Survey of Systems and Software, ACM Computing Survey, 2002. Vol. 34, n. 2, p. 171-210
D. Patterson, J. Hennessy. Computer Organization and design: the hardware/software interface. [S.I.]: Morgan Kaufmann Pub, 2009.
B. Harikrishna, S. Ravi. Intelligent Systems and Control (ISCO), 2013 7th International Conference on Digital Object Identifier: 10.1109/ISCO.2013.6481160 Publication Year: 2013, Page(s): 265 – 270. IEEE Conference Publications.
P. Bleisch, D. Morgan, D. Youngwith. D. The State of ReConfigurable Computing, 1995.
I. Shiliarova, A.B. Ferrari. Introdução à computação reconfigurável. Portugal: Revista DETUA, 2003.
A. Dehon. The Density Advantage of Configurable Computing. In: IEEE Computer. Vol. 33, No. 4. 2000. Page(s): 41 – 49.
C. A. P. S Martins, E. D. M. Ordonez, J. B. T. Corrêa, M. B. Carvalho. Computação Reconfigurável: Conceitos, Tendências e Aplicações. In: XXII Jornada de Atualização em Informática (JAI) - Livro Texto. Campinas: Sociedade Brasileira de Computação, 2003. v. XXII, p. 339- 388.
R. Shettar, R. M. Banakar, P. S. V. Nataraj. Implementation of Interval Arithmetic Algorithms on FPGAs. International Conference on Computational Intelligence and Multimedia Applications 2007. 0-7695- 3050-8/07 © 2007 IEEE DOI 10.1109/ICCIMA.2007.60196.
H. Ratsche, R. Rokne. New Computer Methods for Global Optimization. Ellis Horwood, 2007.
J. Villasenor, W. H. Mangione-Smith. Configurable Computing, Scientific American, Junho 1997. p. 54-59.
S. Hauck, A. Dehon.Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation, Morgan Kaufmann/Elsevier, 2008.
L. Bauer, C. Braun, M.E. Imhof, M.A. Kochte, Zhang Hongyan, H. Wunderlich, J. Henkel. Adaptive Hardware and Systems (AHS), 2012 NASA/ESA Conference on Digital Object dentifier: 10.1109/AHS.2012.6268667.Publication Year: 2012, Page(s): 38-45 Cited by 1. IEEE CONFERENCE PUBLICATIONS.
D. Llamocca, M. Pattichis, Circuits and Systems for Video Technology, IEEE Transactions on Volume: 23, Issue: 3.Digital Object Identifier: 10.1109/TCSVT.2012.2210664 Publication Year: 2013, Page(s): 488 – 502. IEEE JOURNALS & MAGAZINES
R. Harold. Review of "Highly parallel computing".Lorin IBM Thornwood Education Center, Thornwood, New York. Journal. IBM Systems Journal, archive. Vol 29. Issue 1. January 1990. Pg. 165 -166. IBM Corp. Riverton, NJ, USA.
R. Kumar, D. Marinov, D. Padua, M. Parthasarathy, S. Patel, D. Roth, J Torrellas, J. Parallel Computing Research at Illinois the UPCRC Agenda. (2008).
J. Castillo, J. L. Bosque, E. Castillo, P. Huerta, J. Martinez. Hardware accelerated Monte Carlo financial simulation over low cost FPGA cluster. Parallel and Distributed Processing Symposium, Internacional, vol.0. pgs. 1 – 8, 2009.
Leandro, A.J.M. Explorando Linhas de Execução Paralelas com Programação Orientada por Fluxo de Dados. Tese. Universidade Federal do Rio de Janeiro. UFRJ/COPPE . Outubro 2011..
R. Shettar, R. M. Banakar, P. S. V. Nataraj. Design and Implementation of Interval Arithmetic Algorithms. International Conference on Industrial and Information Systems, ICIIS 2006, 8 - 11 August 2006, Sri Lanka. 1- 4244-0322-7/06/ c2006IEE.
G.C. P Duarte; B.R.C. Bedregal. Introdução à Matemática Financeira. Intervalar: Análise Intervalar de Investimentos. Natal, RN. Sociedade Brasileira de Matemática Aplicada e Computacional. Depto de Informática e Matemática Aplicada, CCET, UFRN, Março, 2009.
J. Hormigo; J. Villaiba; E. Zapata. Arithmetic Unit for the Computation of Interval Elementary Functions. Dept. of Computer Architecture University of Malaga. DOI: 10.1109/EURMIC.1999.794447. 1999, p: 63 - 66 vol.1. IEEE CONFERENCE PUBLICATIONS.
M. Shahbazi; P. Poure; S. Saadate;M. R. Zolghadri.Fault Tolerant Five Leg Converter Topology With FPGA Based Reconfigurable Control. Industrial Electronics, IEEE Transactions on Volume: 60, Issue: 6 Digital Object Identifier: 10.1109/TIE.2012.2191754 Publication Year: 2013, Page(s): 2284 – 2294. IEEE Journals & Magazines.
Benhamou; W.J. Older; A. Vellino. Constraint Logic Programming on Boolean, Integer and Real Intervals. Journal of Symbolic Computing. May 10. 1994. (Submitted).
B. Catazaro; B. Nelson.Higher Radix Floating-Point Representations for FPGA-Based Arithmetic. Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines.2005. Page(s): 161 – 170.
Publicado
23/10/2013
Como Citar
ANSELMO, D. N.; MARTINS, C. A. P. S.; SOARES, G. L..
Arquitetura Paralela Reconfigurável em FPGA para Implementação de Operadores Elementares da Aritmética Intervalar. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 14. , 2013, Porto de Galinhas.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 152-159.
DOI: https://doi.org/10.5753/wscad.2013.16785.
