analisis de complejidad de operaciones aritmeticas

An´lisis de complejidad de operaciones aritm´ticas
a
e
Frida Pacheco T., frida.pacheco@usach.cl
20 de junio de 2014
En el cluster de computadores utilizado en el motor de
Es evidente que para un valor alto de Ce , dicho costo
b´squeda de Yahoo! se utiliza un hardware que NO es
u
domina la complejidad, lo cual aproxima al costo
homog´neo y se desea que en el servicio de Indice - se
ete´rico O(), pero como cada consulta en el motor de
o
utilicen los procesadores que mejor rendimiento
b´squeda se ejecuta en tiempos menores que un
u
reportan. El servicio de indice (ver figura 1), es el
segundo, se considera en este estudio solo el an´lisis de
a
servicio donde se construyen los ranking de documentos Ct . Para ello se establece un sencillo algoritmo para el
Web dada lasconsultas de los usuarios con computo
an´lisis de complejidad en tiempo real, del cual se
a
paralelo en un ambiente distribuido. En el servicio de
puede obtener el peso de cada operaci´n aritm´tica.
o
e
indice se disponen de 2048 procesadores y se desea solo
Resultado = 0;
utilizar 1024, para ello se deben seleccionar los 1024 con
for i:n
mayor rendimiento.
Resultado =Resultado+(a+b∗c)/d−log10 (b∗c)+(a∗c)10
endfor
Por lo cual la medida de costo temporal del algoritmo
sera:
Ct (p) = α0 ∗ Ct (+) + α1 ∗ Ct (−) + α2 ∗ Ct (∗) + +α3 ∗
Ct (/) + α4 ∗ Ct (log10 ) + α5 ∗ Ct (potencia)
Donde, para obtener los valores de α, primeramente se
deben obtener los valores de tiempo promedio de cada
operaci´n aritm´tica (+,−,∗,/,log10, potencia). (obs:
o
e
recuerde que existen operacionesaritm´ticas que se
e
repiten en el algoritmo). Entonces, se requiere realizar
un an´lisis del costo temporal del algoritmo, como este
a
se ve afectado por distintos tipos de datos (unsigned
int,unsigned long int, int, float, double, long double) y
distintos valores de a, b, c y d a medida que aumenta el
valor de n.
´
ANALISIS POR TIPO DE DATOS

Figura 1: Esquema general del motor debusqueda de
Yahoo!

Para realizar un mejor an´lisis es necesario conocer los
a
rangos de los tipos de datos, as´ se puede estudiar el
ı
grado en que influye cada tipo al hacer el experimento.
En la siguiente tabla observaremos los rangos de cada
tipo de dato que se utilizar´ para el experimento.
a

Para solucionar esta problem´tica, se recurre a los
a
brillantes alumnos de la Licenciaturaen Ciencia de la
Computaci´n - para que construyan un programa que
o
determine los tiempos promedios de las operaciones
aritm´ticas en cada uno de los 2048 procesadores y
e
establezcan un ranking de los 1024 con mayor
rendimiento a nivel de procesamiento. Ademas, se
requiere un estudio sobre cual es el peso de cada
operaci´n aritm´tica en una medida de costo temporal.
o
e
En laexpresi´n (Ec. 1) se presenta una generalizaci´n
o
o
de la complejidad de un algoritmo en funci´n de costos
o
normalizados, donde Ct es el costo temporal y Ce es el
costo espacial de un algoritmo p. Los valores de α y β
son los pesos que cada costo tiene en el algoritmo p.

TIPO
Short int
Unsigned short int
Int
Unsigned int
Long long int
Unsigned long long int
Float
Double

O(p) = α ∗ Ct(p) + β ∗ Ce (p)
1

RANGO
-32,768 a 32,768
0 a 65,535
-2,147,483,648 a 2,147,483,648
0 a 4,294,967,295
-9,223,372,036,854,775,808 a
9,223,372,036,854,775,808
0 a 18,446,744,073,709,551,615
1.17549e-38 a 3.40282e+38
2.22507e-308 a 1.79769e+308

El experimento por tipo de dato se realiza resolviendo
las operaciones con dos datos, el algoritmo utiliza x e y,
estas variables tienenun valor de x=20 e y=2. Estos
valores son utilizados para todos los tipos de datos.
Se realiza de esta manera para estudiar el
comportamiento del tiempo por cada operaci´n seg´n el
o
u
tipo de dato sin tener alguna influencia de los distintos
valores que puedan tomar x e y.
Adem´s el programa se ejecuta en la frecuencia m´xima
a
a
de CPU, para esto se define la pol´
ıtica Cpufreq...