Implementacja arytmetyki przedziałowej z wykorzystaniem rozszerzeń multimedialnych SSE oraz zmodyfikowanej metody dzielenia przedziałowego

• Autorzy: Pilarek M.
• Języki publikacji: PL

Abstrakty

PL

Otrzymane wyniki badań potwierdzają, że zastosowanie rozszerzeń multimedialnych SSE w zagadnieniach związanych z arytmetyka˛ przedziałową znacznie skraca czas wykonywania obliczeń. Biblioteki Profil/BIAS oraz Boost, które zostały zaimplementowane z pominięciem rozszerzeń multimedialnych wykonują. obliczenia zdecydowanie dłużej. Zastosowanie innego formatu przechowywania przedziałów w pamięci ([a --- a]) oraz odpowiednie zmodyfikowanie operacji arytmetycznych pozwoliło na wykonywanie obliczeń bez ciągłej zmiany trybu zaokrąglania, co nie spowodowało utraty wydajności. Ponadto zastosowana w naszej implementacji zmodyfikowana metoda dzielenia bazująca na koncepcji metody "rozszerzonego przedziałowego zero" pozwala na uzyskiwanie znacznie węższych przedziałów, bez utraty wydajności.

EN

The aim of this paper is to show interval arithmetics implementation using single-instructionmultiple- data (SIMD) SSE (Streaming SIMD Extensions) multimedia instructions, and register set extensions. It was proven previously that SSE extensions can increase performance of interval calculations, since both interval bounds can be kept in one SSE register and all arithmetic operations can be done in parallel. In this work a new approach to the modified interval division is proposed based on the concept of “interval extended zero” method which is a part of this implementation. This method allows us to reduce the undesirable excess width effect. We show the results obtained for several randomly generated matrices using different algorithms (matrix-matrix multiplication, Gauss elimination) and compare them also with results obtained using other interval libraries.

Słowa kluczowe

PL

arytmetyka przedziałowa; SIMD; SSE; przedział obliczeń

EN

interval arithmetics; SIMD; SSE; interval computation

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2010
• Tom: nr 2 (23)
• Strony: 127--135
• Opis fizyczny: Bibliogr. 15 poz., tab.

Twórcy

autor

Pilarek M.

• Politechnika Częstochowska, Instytut Informatyki Teoretycznej i Stosowanej

Bibliografia

• [1] 3D Now! Technology Manual [online]. http://www.amd.com/us-en/ assets/ content_type/white_papers_and_tech_docs/21928.pdf
• [2] Basic Linear Algebra Subprograms Standard [online]. http://www.netlib.org/ blas/ blast-forum/blas-report.pdf
• [3] Boost Interval Arithmetic Library [online]. http://www.boost.org/ doc/ libs/1_43_0/libs/numeric/interval/ doc/ interval.htm
• [4] J. C. Cleary, Logical Arithmetic. Future Computing Systems 2, 1987, s. 125-149
• [5] L. Dymova, M. Pilarek, R. Wyrzykowski, Solving the systems of interval linear equations with use of modified interval dividing procedure. Lecture Notes in Computer Science, vol. 6068, 2010
• [6] L. Dymova, P. Sevastjanov, Fuzzy solution of interval linear equations. Lecture Notes in Computer Science, vol. 4697, 2008, s. 1392-1399
• [7] L. Dymova, P. Sevastjanov, A new method for solving interval and fuzzy equations: linear case. Information Sciences 17, 2009, s. 925-937
• [8] F. Goualard, Fast and Correct SIMD Algorithms for Interval Arithmetic [online]. INRIA, 2008, http:// hal.archives-ouvertes.fr/ docs/ 00/ 28/ 84/ 56/PDF/intervals-sse2-long-paper.pdf
• [9] J.Wolff von Gudenberg, Interval Arithmetic on Multimedia Architectures. RR 265, Lehrstuhl fur Informatik II. Universitat Wurzburg, October 2000.
• [10] Intel SSE4 Programming Reference [online]. http:// software.intel.com/ file/18187/
• [11] R. B. Kearfott, Interval Computations: Introduction, Uses, and Resources. Euromath Bulletin, vol. 2, 1996, s. 95-112
• [12] O. Knuppel, Profil/BIAS v2.0 [online]. http://www.ti3.tu-harburg.de/keil/profil/Profil2.ps.gz
• [13] B. Lambov, Interval Arithmetic using SSE-2. Lecture Notes In Computer Science, vol. 5045, 2008, s. 102-113
• [14] B. Lambov, RealLib 3 Manual [online]. http://www.brics.dk/ ~barnie/ RealLib/RealLib.pdf
• [15] R. E. Moore, Interval Arithmetic and Automatic Error Analysis in Digital Computing. PhD thesis, Stanford University, 1962