{"id":62112,"date":"2018-03-09T22:49:59","date_gmt":"2018-03-09T22:49:59","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/division-and-square-root-for-mobile-and-scientific-computing-markets\/"},"modified":"2018-03-09T22:49:59","modified_gmt":"2018-03-09T22:49:59","slug":"division-and-square-root-for-mobile-and-scientific-computing-markets","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/santiago-de-compostela\/division-and-square-root-for-mobile-and-scientific-computing-markets\/","title":{"rendered":"Divisi\u00f3n and square root for mobile and scientific computing markets"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Vijaykumar Holimath <\/strong><\/h2>\n<p>En esta tesis se analizan los algoritmos para el c\u00edculos de la divisi\u00f3n y la ra\u00edz cuadrada para una representaci\u00f3n punto flotante con simple y doble precisi\u00f3n y se proponen varias implementaciones alternativas. Los aspectos b\u00e1sicos relacionados con la representaci\u00f3n punto flotante, modos de redondeo, valores especiales y excepciones, se resumen en el cap\u00edtulo 1. el uso que se hace de las funciones de divisi\u00f3n y ra\u00edz cuadrada depende, en gran medida, del mercado al que se dirige la implementaci\u00f3n. Por ejemplo, en mercados de computaci\u00f3n m\u00f3vil, tales como pdas, tablet pc, d\u00f3nde se requiere la ejecuci\u00f3n de aplicaciones de internet, visi\u00f3nde fotogramas, presentaciones, etc. No se realiza un uso masivo de estas operaciones; por este motivo, una representaci\u00f3n de punto flotante con precisi\u00f3n simple es suficiente. Por otra parte, en estos segmentos de mercado, se imponen procesadores con una arquitectura de bajo coste y baja complejidad, pero con rendimiento aceptable. El algoritmo newton-raphson (n-r) modificado para c\u00e1lculo del rec\u00edproco y divisi\u00f3n, que se propone en esta memoria, puede ser adecuado para este mercado. otra de las implementaciones propuestas, ra\u00edz cuadrada de tabla de aproximaci\u00f3n inicial (look.Up table, lut) est\u00e1 basado en una modificaci\u00f3n del algoritmo n-r. Sin embargo, su rendimiento es algo deficiente, porque cada interaci\u00f3n requiere tres ciclos y son necesarias varias iteraciones. El n\u00famro total de ciclos que se necesitan para el c\u00e1lculo de la ra\u00edz cuadrada con este algoritmo es, aproximadamente, 50. Creemos que es necesario profundizar todav\u00eda m\u00e1s en este algoritmo para lograr una implementaci\u00f3n eficiente.  estas funciones son frecuentes en aplicaciones de computaci\u00f3n gr\u00e1fica 3d, aplicaciones de c\u00e1lculo cient\u00edfico, aplicaciones matem\u00e1ticas, etc. La mayor parte de estas aplicaciones necesitan utilizar una representaci\u00f3n punto flotante de doble precisi\u00f3n. En estos campos de aplicaci\u00f3n, el procesador tiene una arquitectura de alto rendimiento con niveles de complejidad y coste aceptables. Otro de los algoritmos propuestos, el m\u00e9todo aqa (accurate quotient aproximation) puede ser de utilidad. Adem\u00e1s, este m\u00e9todo podr\u00e1 ser utilizado para procesamientos futuros orientados a aplicaciones m\u00f3viles. Para aumentar el rendimiento de estas implementaciones, la aproximaci\u00f3n inicial se obtiene mediante la lut o la lut combinada con algoritmos de aproximaci\u00f3n lineal o cuadr\u00e1tica para reducir el \u00e1rea necesaria. Esta aproximaci\u00f3n inicial est\u00e1 acoplada a las interacciones del algoritmo n-r, el algoritmo de goldschmidt (gld) y los algoritmos de d\u00edgito recurrencia (dr).  en el cap\u00edtulo 2, se discute de forma detallada la obtenci\u00f3n de la aproximaci\u00f3n inicial y los algoritmos n-r, gld y dr. estas funciones son lentas porque efect\u00faan secuencias de sumas y rests, multiplicaciones y suma-multiplicaci\u00f3n, bloqueando la unidad de punto flotante del procesador (fpu) durante el c\u00edrculo. Algunos procesadores implementan estas funciones en software, por ejemplo el itanium, y otros en hardware, tales como procesadores de ibm y amd. La implementaci\u00f3n software proporciona un alto grado de paralelismo y no bloquea la fdu, sin embargo su rendimiento es bastante pobre. Las implementaciones hardware obtienen mejores rendimentos, pero a costa de una complejidad y coste mayores. Muchos dise\u00f1adores est\u00e1n dispuestos a sacrificar la velocidad para obtener costes y complejidad menores. El rendimiento y la complejidad dependen de la precisi\u00f3n, y la precisi\u00f3n depende a su vez del mercado al que est\u00e1 dirigido el procesador y de los requerimientos de este mercado. en esta memoria se propone un m\u00e9todo, el m\u00e9todo aqa modificado, que proporciona mejoras significativas en el rendimiento, con una mayor eficiencia en t\u00e9rminos de \u00e1rea de silicio que los procesadores convencionales utilizados para c\u00e1clulos en precisi\u00f3n simple. en el cap\u00edtulo 3 se describe una modificaci\u00f3n del algoritmo n-r sin lut para el c\u00e1lculo del rec\u00edproco, que es la implementaci\u00f3n de mayor eficiencia en t\u00e9rminos de \u00e1rea. Es un algoritmo de latencia variable, con convergencia lineal que requiere un m\u00e1ximo de 22 iteraciones. Un algoritmo de latencia variables es \u00fatil en divisores auto-controlados, d\u00f3nde la capacidad de procesamiento depende de la aplicaci\u00f3n. De esta forma, se puede reducir el consumo de potencia sin sacrificar el rendimiento. para evaluar el m\u00e9todo propuesto utilizamos multiplicadores de radix 4 y radix 8. El resultado de la evaluaci\u00f3n muestra que puede haber un ligero incremento de tiempo debido a los componentes extra que se necesitan, recodificador de booth radix 8 y recodificaci\u00f3n entre representaciones redundantes. Hemos comparado el m\u00e9todo propuesto con implementaciones en procesadores actuales (tabla 3.4). El m\u00e9todo propuesto puede ser implementado en un multiplicador radix 4 y un multiplicador radix 8 con un peque\u00f1o incremento de \u00e1rea con respecto al \u00e1rea del multiplicador integrado en el procesador. Por otra parte, se observa un incremento en el rendimiento con respecto al procesador itanium y a los procesadores de ibm, pero una p\u00e9rdida con respecto al ibm 603etm y los procesadores de amd. Esta p\u00e9rdida es debida a que se retiran 1,09 bits por interacci\u00f3n y no hay disponible una lut de tama\u00f1o elevado. Por lo tanto, el rendimiento es parecido al rendimiento medio de los procesadores actuales. en el cap\u00edtulo 4, se propone una modificaci\u00f3n del m\u00e9todo aqa para divisi\u00f3n y ra\u00edz cuadrada, utilizando una lut, para aplicaciones de c\u00e1lculo de alto rendimiento. Esta implementaci\u00f3n ofrece algunas estrategias atractivas adicionales a los algoritmos n-r convencional, gld, dr y cyrix, que se discuten m\u00e1s adelante. Para evaluar el algoritmo aqa modificado hemos utilizado el multiplicador radix 4 de la fpu del ibm 603tm, orientado a aplicaciones m\u00f3viles, y el multiplicador radix 8 de la fpu del ibm g5, orientado a aplicaciones de alto rendimiento; en ambos casos se ha utilizado una representaci\u00f3n de doble precisi\u00f3n (ver tabla 4.7). La comparaci\u00f3n muestra que se obtiene una mayor eficiencia en t\u00e9rminos de \u00e1rea y un mayor rendimiento. Se obtiene una reducci\u00f3n de \u00e1rea respecto a implementaciones tradicionales basadas en lut. las principales contribuciones de las propuestas presentadas en la tesis se resumen a continuaci\u00f3n. Con respecto al algoritmo n-r modificado para el c\u00edrculo del rec\u00edproco, podemos destacar que no necesita tablas para la aproximaci\u00f3n inicial y que el rendimiento se mantiene similar al obtenido con los procesadores actuales, debido a que se est\u00e1n calculando los resultados intermedios en representaci\u00f3n redudante. La aproximaci\u00f3n inicial es el complemento a dos del divisor, que puede obtenerse en paralelo con la suma de los productos parciales. \u00c2\u00bfcada iteracci\u00f3n es un ciclo, a diferencia de los dos ciclos por iteraci\u00f3n de los procesadores actuales. Los m\u00faltiplos del divisor se mantienen constantes durante la iteracci\u00f3n por lo tanto, es necesario generarlos solamente una vez. Adem\u00e1s, la operaci\u00f3n multiplicaci\u00f3n-suma y la recodificaci\u00f3n de booth pueden ser realizadas en el mismo ciclo que la suma de los productos parciales. El resultado es un algoritmo de latencia variable que requiere s\u00f3lo 22 iteraciones. este m\u00e9todo puede ser extendido al c\u00e1lculo de la ra\u00edz cuadrada y s\u00f3lo necesita 22 iteraciones. pero no mejora el rendimiento medio de los procesadores convencionales debido a que en cada iteraci\u00f3n hay que calcular el cuadrado del cociente. Cada iteraci\u00f3n precisa tres ciclos por lo tanto, son necesarios m\u00e1s de 50 ciclos para obtener el resultado final. las principales contribuciones y ventajas del m\u00e9todo aqa modificado son las siguientes. En comparaci\u00f3n con el m\u00e9todo n-r, solamente se necesita la aproximaci\u00f3n inicila de 30 bits para obtener el cociente. Con respecto al algoritmo gld, la metodolog\u00eda es parecida, pero la organizaci\u00f3n del hardware es diferente. Los resultados intermedios en representaci\u00f3n redundante se utilizan como multiplicadores y se solapan diversas operaciones. Estas caracter\u00edsticas incrementan el rendimiento. La duraci\u00f3n del ciclo no aumenta aunque el n\u00famero de bits que se retiran en cada iteraci\u00f3n es elevado. Esto no ocurre en los algoritmos dr, en los que la duraci\u00f3n del ciclo aumenta con el radix. Con respecto al algoritmo cyrix, el algoritmo aqa modificado necesita una iteraci\u00f3n para obtener el resultado en doble precisi\u00f3n. Los 28 bits m\u00e1s significativos y los 28 bits significativos del cociente se generan en paralelo y se suman durante la multiplicaci\u00f3n. Para obtener doble precisi\u00f3n con el algoritmo cyrix se necesitan dos iteraciones. Los 28 bits m\u00e1s significativos y los 28 bits menos significativos del cociente se generan de forma secuencial. Por otra parte, el algoritmo propuesto puede adaptarse a operar con operandos en punto fijo, mientras que el algoritmo cyrix no es posible adaptarlo. El tama\u00f1o de la lut para la aproximaci\u00f3n inicial es, aproximadamente, la mitad que el tama\u00f1o de la lut en los procesadores convencionales. La recodificaci\u00f3n booth puede llevarse a cabo en el mismo ciclo que la suma de los productos parciales y solap\u00e1ndose con alguna de las operaciones necesarias para la obtenci\u00f3n del resto, lo cual aumenta el rendimiento. el algoritmo aqa modificado puede ser extendido tambi\u00e9n al mercado de la computaci\u00f3n m\u00f3vil y al de aplicaciones de alto rendimiento de procesadores futuros. Puede ser incorporado a multiplicadores industriales con poco hardware extra.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Divisi\u00f3n and square root for mobile and scientific computing markets<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Divisi\u00f3n and square root for mobile and scientific computing markets <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Vijaykumar Holimath <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Santiago de compostela<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 18\/12\/2007<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Javier D\u00edaz Bruguera<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: Francisco Fern\u00e1ndez rivera <\/li>\n<li>Alberto Nannarelli (vocal)<\/li>\n<li>marc Daumas (vocal)<\/li>\n<li>julio Villalba moreno (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Vijaykumar Holimath En esta tesis se analizan los algoritmos para el c\u00edculos de la divisi\u00f3n y la [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[8991,45382,977,2535],"tags":[137178,21042,21041,70604,137179,137177],"class_list":["post-62112","post","type-post","status-publish","format-standard","hentry","category-circuitos-integrados","category-instrucciones-aritmeticas-y-de-maquina","category-santiago-de-compostela","category-tecnologia-de-los-ordenadores","tag-alberto-nannarelli","tag-francisco-fernandez-rivera","tag-javier-diaz-bruguera","tag-julio-villalba-moreno","tag-marc-daumas","tag-vijaykumar-holimath"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/62112","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=62112"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/62112\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=62112"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=62112"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=62112"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}