Algoritmos sistólicos para transformaciones ortogonales

Resumen

EN ESTA TESIS SE DESARROLLAN ALGORITMOS PARALELOS PARA LA OBTENCION DE LOS AUTOVALORES DE UNA MATRIZ Y PARA OTROS PROBLEMAS RELACIONADOS, QUE SE PUEDEN EJECUTAR EFICIENTEMENTE EN AGRUPACIONES SISTOLICAS DE PROCESADORES, QUE NO SON MAS QUE UN TIPO DE ARQUITECTURAS PARALELAS, CONSTRUIDAS MEDIANTE LA TECNOLOGIA VLSI, PARA TODOS LOS PROBLEMAS CONSIDERADOS, DISEÑAMOS AGRUPACIONES DE PROCESADORES CUYO TAMAÑO ES INDEPENDIENTE DEL TAMAÑO DEL PROBLEMA. ESTE PUNTO ES DE GRAN INTERES PRACTICO YA QUE EN UN SISTEMA DE PROPOSITO GENERAL, LOS PROBLEMAS A RESOLVER SON DE TAMAÑO ARBITRARIO. EL CONJUNTO DE PROBLEMAS COMPRENDE: LA DESCOMPOSICION QR DE UNA MATRIZ, LA RESOLUCION DEL LMS, LA TRANSFORMACION SIMILAR DE UNA MATRIZ A TIPO HESSENBERG, LA TRIDIAGONALIZACION DE UNA MATRIZ HERMITICA Y LA ITERACION QR. PARA EL CALCULO DE AUTOVALORES SOBRE UNA MATRIZ HESSENBERG Y SOBRE UNA MATRIZ BANDA. LA ESTRUCTURA COMPUTACIONAL QUE RESULTA CONSISTE DE VARIOS EPS, DE LOS CUALES UNICAMENTE EL PRIMERO DEBE REALIZAR CALCULOS COSTOSOS (RAICES CUADRADAS Y DIVISIONES) MIENTRAS EL RESTO DE EPS SOLO DEBEN REALIZAR PRODUCTOS Y SUMAS. ESTE TIPO DE AGRUPACION VA A SER UTILIZADA POR TODOS LOS DISEÑOS, POR LO QUE LA DENOMINAMOS VERSATIL, POR SU CAPACIDAD DE SER USADA PARA LA RESOLUCION DE UN CONJUNTO AMPLIO DE PROBLEMAS. PRIMERAMENTE, SE PRESENTAN DOS NUEVOS ALGORITMOS SISTOLICOS PARA LA RESOLUCION DE LA DESCOMPOSICION QR EN UNA ARRAY LINEAL. EN EL PRIMERO, LOS DATOS INICIALES ESTAN ALMACENADOS POR COLUMNAS, MIENTRAS QUE EL RESULTADO QUEDA POR DIAGONALES, EL FLUJO DE DATOS ES 1-SLOW, Y NO TIENE CONTRAFLUJO. LA EFICIENCIA DE UTILIZACION DEL ARRAY ES DEL ORDEN DEL 90%. AMBOS DISEÑOS PUEDEN COMBINARSE DE FORMA OPTIMA CON EL DISEÑO DE UN ALGORITMO SISTOLICO PARA LA RESOLUCION DEL SISTEMA TRIANGULAR DE ECUACIONES, CONFORMANDO ASI, UNA ESTRUCTURA COMPUTACIONAL PARA EL LMS. TAMBIEN SE REALIZAN DISEÑOS PARA LA REALIZACION DE LA TRANSFORMACION SIMILAR QUE PERMITE R