Una contribució al càlcul de valors i vectors propis i a l'anàlisi de l'escalabilitat

Author

Royo Vallés, Dolors

Director

Valero García, Miguel

Date of defense

1999-01-27

ISBN

9788469089668

Legal Deposit

B.51290-2007



Department/Institute

Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors

Abstract

El càlcul de valors i vectors propis és un nucli computacional que forma part de diverses aplicacions de tipus científic i tècnic que requereixen una potència de càlcul molt gran. Aquestes aplicacions no poden resoldre's en sistemes monoprocessadors perquè aquests sistemes no proporcionen la potència de càlcul suficient per resoldre el problema amb un temps raonable. Una solució possible a aquest problema és la utilització de sistemes paral·lels.<br/><br/>El contingut d'aquest treball pot dividir-se en quatre parts ben diferenciades; en les tres primeres parts dels valors i vectors propis en sistemes multicomputadors amb diferents topologies: hipercub, malla i torus; en l'última part del treball es proposa una metodologia d'anàlisis de l'escalabilitat de sistemes paral·lels.<br/><br/>- En la primera part del treball es proposen un conjunt d'algorismes paral·lels per hipercubs: BR segmentat, alfa-optimal i Grau-4. Tots aquests algorismes es basen en l'algorisme Block Recursive proposat a [42]. Els nous algorismes proposats tenen la capacitat d'utilitzar de forma més eficient el potencial paral·lelisme de comunicacions que ofereix una arquitectura multiple-port amb els que s'aconsegueix una reducció del cost de la comunicació considerable respecte al cost de comunicació de l'algorisme original.<br/><br/>- En la segona part del treball es proposa un nou algorisme amb una topologia de comunicació en malla bidimensional (2D). Aquest algorimse l'hem anomenat algorisme 2D. Es veurà que aquest nou algorisme aconsegueix reduir el cost total considerablement respecte als algorismes que han estat proposats per altres autors per malles i torus.<br/><br/>- En la tercera part, s'estudia l'eficiència de l'algorisme BR-segmentat (algorisme amb una topologia de comunicació en hipercub proposat en la primera part de la tesi) un cop mapejat en un multicomputador amb una topologia en malla o en torus. A l'hora de realitzar el mapeig s'ha aplicat i ampliat una metodologia desenvolupada en el grup de treball que ens permet realitzar el mapeig de forma eficient i sistemàtic d'una topologia en hipercub a una topologia en malla o torus. El cost de la comunicació del nou algorisme es compara amb el cost de l'algorisme 2D proposat en la segona part del treball.<br/><br/>- Finalment, en l'última part d'aquest treball es proposa una metodologia d'anàlisi de l'escalabilitat de sistemes paral·lels orientada a l'usuari final del sistema. S'utilitza l'algorisme 2D mapejat en una línia per mostrar un exemple d'aplicació de la metodologia.

Keywords

xarxa d'interconnexió; xarxa d'interconnexió; malles; malles; hipercubs; hipercubs; memòria distribuïda; memòria distribuïda; arquitectures multiprocessadors; arquitectures multiprocessadors; valors i vectors propis; valors i vectors propis; paral·lelització d'algoritmes; paral·lelització d'algoritmes

Subjects

004 - Computer science and technology. Computing. Data processing

Documents

01Drv01de01.pdf

1.184Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)