Estructura de los datos: Grafos en Haskell

Introducción

Terminología.

1. Se dice que G es completo si A = V x V, esto es, si todas las aristas

posibles pertenecen a A.

2. Se dice que G es no dirigido si

∀ v1, v2 ∈ V : (v1, v2) ∈ A ⇒ (v2, v1) ∈ A

3. Se dice que dos vértices v1, v2 ∈ V son adyacentes o vecinos si

existe una arista a ∈ A conectándolos. Si el grafo es dirigido y

(v1, v2) ∈ A , decimos que v1 es adyacente a v2 y v2 es adyacente

desde v1.

4. Una secuencia de vértices v1, ..., vm ,decimos que es un camino si

∀ i ∈ {1, . . .,m-1}, (vi, vi+1) ∈ A.

5. Se dice que un camino es simple si cada vértice sólo aparece una

vez en la secuencia.

6. Se dice que v1, v2 ∈ V están conectados si existe un camino en

G de v1 a v2.

7. Un grafo no dirigido es conexo si para cada par de vértices

distintos vi, vj existe un camino que los conecta.

8. Un grafo dirigido es fuertemente conexo si para cada par de

vértices distintos, vi , vj existe un camino de vi a vj.

9. Un ciclo es un camino para el que los vértices inicial y final

coinciden, y los vértices intermedios solo aparecen una vez en

la secuencia.

10. Un grafo es acíclico si no contiene ciclos.

Especificación algebraica.

Definición formal (Haskell) de grafo no dirigido.

Podemos dar varias definiciones formales de grafo ( aunque usaremos la 1º para nuestros ejemplos ):

-- 1. Similar a Conjunto:

data Grafo a = GVacio | Nodo a (Grafo a) | Arco a a (Grafo a)

g1 :: Grafo Int

g1 = Arco 1 3 (Arco 1 2 (Arco 2 3 (Nodo 4 (Nodo 3 (Nodo 2 (Nodo 1 GVacio))))))

-- 2. Par nodos + aristas como pares:

data Grafo2 a = G2 [a] [(a, a)]

g2 :: Grafo2 Int

g2 = G2 [1,2,3,4] [(1,3), (1,2), (2,3)]

-- 3. Par nodos + aristas como operación sucesor:

data Grafo3 a = G3 [a] (a -> [a])

g3 :: Grafo3 Int

suc :: Int -> [Int]

suc 1 = [2,3]; suc 2 = [1,3]; suc 3 = [1,2]; suc _ = []

g3 = G3 [1,2,3,4] suc

Las operaciones generadoras no son libres (en ningún caso).

-- Axiomas de equivalencia para la 1ª forma:

-- los extremos de un arco deben existir, y pueden estar en cualquier orden:

Arco n m g = if existe n g && existe m g

then Arco m n g

else GVacio -- o un dato Error definido en data, o error “no existe extremo”

-- los nodos o arcos repetidos no hacen diferente a un grafo:

Nodo m (Nodo n g) = if (n == m)

then Nodo n g

else Nodo n (Nodo m g) -- pueden intercambiarse las posiciones

Arco n’ m’ (Arco n m g) = if (n == n’ && m == m’) or (n == m’ && m == n’)

then Arco n m g

else Arco n m (Arco n’ m’ g) -- pueden intercambiarse las posiciones

-- podemos suponer todo Nodo mas interno (anterior) que todo Arco:

Nodo n’ (Arco n m g) = Arco n m (Nodo n’ g)

Operaciones básicas según la forma 1

-- Suponemos grafos en forma normal (sin repeticiones, no errores, y arcos antes que nodos).

-- Para cualquier operación op puede implementarse otra op0 que obtiene previamente la forma normal del grafo:

op0 … grafo … = op … (fn grafo) …

fn :: (Eq a) => Grafo a -> Grafo a -- forma normal de un grafo:

fn g = let gre = reordena g in -- parte Nodo dentro de parte Arista

if aristasok gre -- los nodos de las aristas estan en el grafo

then quitarrepes gre -- quita aristas y nodos repetidos

else GVacio

reordena :: Grafo a -> Grafo a

reordena g = aux g GVacio

aux :: Grafo a -> Grafo a -> Grafo a -- acumula nodos en el 2º parámetro

aux (Nodo n g) h = aux g (Nodo n h)

aux (Arco x y g) h = Arco x y (aux g h)

aux GVacio h = h

aristasok :: (Eq a) => Grafo a -> Bool

aristasok (Arco x y g) = (esta x g) && (esta y g) && (aristasok g)

aristasok _ = True

quitarrepes :: (Eq a) => Grafo a -> Grafo a

quitarrepes GVacio = GVacio

quitarrepes (Nodo x g) = if esta x g then quitarrepes g else Nodo x (quitarrepes g)

quitarrepes (Arco x y g) = if adyacentes x y g then quitarrepes g else Arco x y (quitarrepes g)

-- Otras funciones implementadas.

esta :: (Eq a) => a -> Grafo a -> Bool

esta _ GVacio = False

esta x (Nodo y g) = x==y || esta x g

esta x (Arco _ _ g) = esta x g -- sólo mira en los nodos

􀂄 adyacentes :: (Eq a) => a -> a -> Grafo a -> Bool

adyacentes x y (Arco u v g) = x==u && y==v || x==v && y==u || adyacentes x y g

adyacentes _ _ _ = False

􀂄 gvacio :: Grafo a -> Bool

gvacio GVacio = True

gvacio _ = False

􀂄 borranodo :: (Eq a) => a -> Grafo a -> Grafo a

borranodo _ GVacio = GVacio

borranodo n (Arco x y g) = if n==x || n==y then borranodo n g else Arco x y (borranodo n g)

borranodo n (Nodo x g) = if n==x then g else Nodo x (borranodo n g)

􀂄 borraarco :: (Eq a) => a -> a -> Grafo a -> Grafo a

borraarco x y (Arco u v g) = if x==u && y==v || x==v && y==u

then g else Arco u v (borraarco x y g)

borraarco _ _ g = g

􀂄 sucesores :: (Eq a) => a -> Grafo a -> [a]

sucesores x (Arco y z g) | (x==y) = z : sucesores x g

| (x==z) = y : sucesores x g

| True = sucesores x g

sucesores _ _ = []

Ejemplo que nos pude caer en un examen: Especificar en Haskell la operación:

mas :: Grafo a -> a -> Grafo a

que a partir de un grafo en forma normal, le añade un nuevo nodo y todos los arcos necesarios para conectar este nodo con todos los demás. La salida debe darse en forma normal, sin hacer uso de la operación fn.

Por ejemplo, si tenemos el grafo:

g1 = Arco 1 3 (Arco 1 2 (Arco 2 3 (Nodo 4 (Nodo 3 (Nodo 2 (Nodo 1 GVacio))))))

entonces, al evaluar mas g1 5 obtendremos:

Arco 5 4 (Arco 5 3 (Arco 5 2 (Arco 5 1 (Arco 1 3 (Arco 1 2 (Arco 2 3 (Nodo 5 (Nodo 4 (Nodo 3 (Nodo 2 (Nodo 1 GVacio)))))))))))

(salvo el orden en los arcos y los nodos).

-- Solución.

mas :: Grafo a -> a -> Grafo a

mas g n = auxMas (listaNodos g ) g n

auxMas :: [a] -> Grafo a -> a -> Grafo a

auxMas (x:xs) g n = Arco n x (auxMas xs g n)

auxMas [] (Arco x y g) n = Arco x y (auxMas [] g n)

auxMas x g n = Nodo n g

listaNodos :: Grafo a -> [a]

listaNodos (Arco _ _ g) = listaNodos g

listaNodos ( Nodo x GVacio ) = x:[]

listaNodos ( Nodo x g ) = x:listaNodos g

E-Learning desde mi móvil.

INDICE:

1.- Introducción a E-Learning.

2.- En qué consiste la enseñanza E-Learning.

3.- ¿Como debería ser el estudiante en la enseñanza On-line?.

4.- Diferencias ente E-Learning y M-Learning.

5.- M-Learning para dispositivos móviles.

6.- Modulo M-Learning off-Line.

7.- Ejemplos de algunos proyectos M-Learning, en la actualidad.

8.- Bibliografía.

1.- INTRODUCCIÓN AL E-LEARNING.

El E-learning es un medio de educación a distancia completamente virtualizada, que literalmente significa "e-aprendizaje", es decir, aprendizaje con medios electrónicos; a través de los nuevos canales electrónicos (principalmente Internet), utilizando para ello herramientas o aplicaciones de hipertexto (correo electrónico, páginas web, foros de discusión, chat, etc., o plataformas de formación, que incorporan gran cantidad de herramientas de las nombradas anteriormente) como soporte de los procesos de enseñanza-aprendizaje.

2.- En qué consiste la enseñanza E-Learning.

Gracias a las nuevas tecnologías de la información y la comunicación (TIC), los estudiantes "en línea" pueden comunicarse con sus compañeros "de clase" y docentes, de forma síncrona (chat, skype,…) o asíncrona (correo electrónico,…), sin limitaciones espacio-temporales. Es decir, se puede entender como una modalidad de aprendizaje dentro de la educación a distancia en la que se utilizan las redes de datos como medios (Internet, intranets, etc.), las herramientas o aplicaciones hipertextuales como soporte y los contenidos y/o unidades de aprendizaje en línea como imágenes, audio, video, documentos, complejas producciones multimedia, o cualquier otro tipo de material formativo.

E-learning es principalmente una modalidad de aprendizaje a distancia o virtual, donde se puede interactuar con los profesores por medio de Internet, por lo que constituye una alternativa para aquellos que combinan trabajo con estudios, y que no es necesario para ellos acudir a un aula constantemente.

Si la educación a distancia es, desde sus orígenes, una opción para atender la formación de personas adultas, el e-learning tiene la ventaja de que los usuarios eligen sus propios horarios, y puede entrar a la plataforma desde cualquier lugar donde puedan acceder a una computadora con conexión a Internet.

También cabe mencionar, que el e-learning es una excelente herramienta que puede ayudar a los usuarios no solo a aprender conceptos nuevos sino también a afianzar conocimientos y habilidades, aumentado así la autonomía y la motivación de los estudiantes por diferentes temas.

El modo de aprendizaje electrónico, sufre una brutal expansión desde sus inicios, con lo que la pregunta que surge es: ¿Por qué se produce esta expansión tan fuerte?

Esto puede ser ocasionado, por que el actual sistema de enseñanza tradicional no es capaz de adaptarse a la sociedad ni a su forma de vida.

Esto es debido a que el sistema de enseñanza tradicional es incapaz de responder a las nuevas necesidades de la sociedad, imponiendo determinadas barreras que dificultan el aprendizaje, que podrían dividirse a grandes rasgos en tres:

• Problemas geográficos: Las personas residentes en zonas alejadas de centros educativos ven disminuidas sus posibilidades de acceso a la educación. De la misma manera, en capitales densamente pobladas existen personas que quieren seguir aprendiendo, pero el lugar físico donde se imparte esa enseñanza supone una lejanía que exige combinar diversos medios de transporte, posibles problemas de aparcamiento, horas-punta, etc. También hay que tener en cuenta los trabajadores que son desplazados por sus empresas a diferentes lugares geográficos, lo que impide una continuidad en sus estudios; a las personas discapacitadas que pueden tener problemas a la hora de desplazarse al centro de enseñanza.

• Problemas de tiempo: La enseñanza tradicional requiere establecer un horario en el que se reúnan profesores y alumnos. Sin embargo son muchas las personas que no pueden acudir al centro de enseñanza en ese horario. Cuando esas mismas personas disponen de tiempo, el centro de enseñanza puede no impartir docencia.

• Problemas de demanda: Resulta complicado crear e impartir cursos formativos cuando la demanda local no justifica el esfuerzo ni la inversión. Las acciones formativas dirigidas a pequeñas poblaciones, encuentran difícilmente justificación, por escaso número de alumnos potenciales, aunque los mismos tengan una gran necesidad de formarse o reciclarse en determinadas materias.

Basándonos en todo los anterior, se aprecian algunas ventajas que ofrece la formación online:

• Inmersión práctica en un entorno Web 2.0 (con este concepto de Web 2.0, subrayamos un cambio de paradigma sobre la concepción de Internet y sus funcionalidades, que ahora abandonan su marcada unidireccionalidad y se orientan más a facilitar la máxima interacción entre los usuarios y el desarrollo de redes sociales donde puedan expresarse y opinar, buscar y recibir información de interés, colaborar y crear conocimiento, además de compartir contenidos).

• Eliminación de barreras espaciales y temporales (desde su propia casa, en el trabajo, en un viaje a través de dispositivos móviles, etc.). Supone una gran ventaja para empresas distribuidas geográficamente.

• Prácticas en entornos de simulación virtual, difíciles de conseguir en formación presencial, sin una gran inversión (aplicaciones de simulación de reacciones químicas, montaje y desmontaje de automóviles, etc.).
• Gestión real del conocimiento: intercambio de ideas, opiniones, prácticas, experiencias. Enriquecimiento colectivo del proceso de aprendizaje sin límites geográficos.
• Actualización constante de los contenidos.

• Reducción de costes (en la mayoría de los casos, a nivel metodológico y, siempre, en el aspecto logístico).

• Permite una mayor conciliación de la vida familiar y laboral.

• Las empresas manifiestan cada vez mayor interés en las aulas virtuales porque les resulta más barato y fácil capacitar continuamente a su personal en diferentes plazas, que hacerlo viajar.

Además, se ha de destacar algunos inconvenientes importantes:

• La cultura es muy imporntante en este tipo de enseñanza ya que en muchos países todavía se tiene la mentalidad de que para aprender hay que ir a la escuela, sentarse y escuchar a los maestros.

• La accesibilidad representa también una enorme desventaja, sobre todo en países en los que no se dispone de la tecnología apropiada o donde la mayoría de la población vive en la pobreza.

• Motivación. El hecho de que el alumno asuma la responsabilidad de su propio aprendizaje implica que, si no encuentra una motivación para seguir o el curso no está bien diseñado, opte por la renuncia.

Actualmente existen gran mayoría de plataformas basadas en e-learning, tanto comerciales como de código abierto. En el ámbito universitario es la WebCT la plataforma más utilizada (aunque la plataforma de licencia libre "Moodle" se está implantando con gran fuerza), seguida a bastante distancia de la plataforma Edustance. También se utiliza en varias universidades la plataforma de código abierto LRN, Blackboard y eCollege. A nivel europeo, cobra especial relevancia la plataforma de código abierto Ilias (Ver Figura 1.), ampliamente utilizada en Europa tanto en instituciones educativas como en entornos de formación empresarial y Fronter, especialmente en Reino Unido y los países del norte.

Esta diversidad de plataformas son administradas mediante un sistema de gestión de contenidos (CMS), que es una aplicación que permite crear una estructura de soporte para la creación y administración de contenidos por parte de los participantes principalmente en páginas web.

El entorno de hardware y software diseñado para automatizar y gestionar el desarrollo de actividades formativas se conoce como Plataforma de Teleformación o LMS (Learning Management System).

Un LMS registra usuarios, organiza catálogos de cursos, almacena datos de los usuarios y provee informes para la gestión. Suelen incluir también herramientas de comunicación al servicio de los participantes en los cursos.

Las mejoras en usabilidad (navegación fácil e intuitiva) y accesibilidad (posibilidad de acceso por personas con discapacidad) permiten salvar la brecha digital y extender las posibilidades de formación a mayor número de personas, superando una de las mayores barreras del e-learning: la barrera tecnológica.

Estas plataformas de formación son una alternativa que no reemplaza necesariamente a los profesores y las clases presenciales, sino que es un espacio que desarrolla la autonomía del aprendiz.

3.- ¿Como debería ser el estudiante en la enseñanza On-line?

El estudiante a distancia online debe ser una persona capacitada, con la capacidad de adaptarse a una nueva forma de estudio. También, ser organizado, con capacidad de actualización y motivación. Y si es posible; con disciplina, ilusión y una actitud que sepa recoger las ventajas de ser cada vez un poco más dueño de su tiempo.

El e-Learning no es un remedio que sustituya a la formación presencial ni a otros métodos de formación, sobre todo en enseñanzas básicas. Pero resulta una opción particularmente interesante para la formación corporativa, así como para aquellos casos en los que haya limitaciones de horario o geográficas.

4.- Diferencias ente E-Learning y M-Learning.

En este tipo de educación y debido a la independencia del espacio y del tiempo se crean nuevos modelos de educación a distancia. En el e-learning, cuando se hace referencia a "distancia" esto implica un cambio geográfico entre donde están los contenidos y el lugar en que se enseñan, manteniendo siempre una conexión física entre ellos. En cambio, en el m-learning el término "distancia" implica que la recuperación o el acceso al contenido puede hacerse en movimiento, sin importar el lugar y obteniendo un mayor provecho del tiempo disponible.

Resumiendo, m-learning se adapta con más facilidad a la sociedad actual y a los centros de enseñanza y pretende que puedan desarrollar y adaptar el aprendizaje a una sociedad cada vez más móvil.

5.- M-Learning para dispositivos moviles.

Fué originado en la década de los 80, cuando el Xerox Palo Alto Research Center (PARC propuso el Dynabook (un ordenador del tamaño de un libro, portátil, con red inalámbrica y pantalla plana), en la década de los 90 siguió desarrollándose en universidades de Europa y Asia, donde se evaluaron las posibilidades de la educación móvil para estudiantes.

En los últimos diez años, el m-learning ha ido despertando cada vez más interés en todo el mundo. A él se han destinado ya importantes proyectos en escuelas, centros de trabajo, museos, ciudades o áreas rurales, por lo que la propuesta de los investigadores alemanes sin duda potenciará la implantación de esta nueva modalidad de aprendizaje móvil.

En la actualidad, y dentro del mundo de las nuevas tecnologías, uno de las áreas en las que más se está trabajando, es en los dispositivos móviles: PDAs, móviles de última generación, etc., lo que trasladándolo a la vida cotidiana implica un gran aumento en el tiempo que dedicamos a esos dispositivos.

Debido al aumento de este tipo de tecnologías, y haciendo hincapié en la formación cabe la posibilidad de pensar que se podrían utilizar dichos dispositivos como medio o soporte de aprendizaje, ya que en realidad, uno de los elementos fundamentales para afianzar un aprendizaje es el uso del mismo, y la posibilidad de generalizar lo aprendido en el aula al contexto de trabajo. La ventaja de esto es facilitar que el aprendizaje sea mas ágil y duradero, aumentando también la calidad del mismo, algo que ya facilitaba el e-learning pero que con estos dispositivos móviles sería aun mayor.

Este nuevo concepto es lo que se ha empezado a denominar m-learning o aprendizaje móvil.

De esta definición se puede observar que un sistema de m-learning consta de dos partes: por un lado el e-learning, que aporta los contenidos y, por el otro el dispositivo al que se traslada, que aporta la característica fundamental de este sistema de aprendizaje, la movilidad, lograda mediante el uso de protocolos de red inalámbrica como por ejemplo WAP (Wirless Aplication Protocol), que posibilitan que la exposición de los contenidos sean independientes del lugar (no resulta necesaria una conexión física entre el servidor y la terminal) y del tiempo (el usuario puede acceder a los contenidos en cualquier momento).

6.- Módulo de m-learning off line

Debido a que el coste de las comunicaciones móviles en la actualidad es excesivamente elevado ( en algunos países hasta precios desorbitados ), surge un posible problema de no viabilidad en este tipo de proyectos.

Particularmente, el usuario podría tener diversos problemas para usar este tipo de sistemas en países con condiciones socioeconómicas adversas, pero no solo por el coste de las comunicaciones, si no también, en la adquisición de terminales o dispositivos con la tecnología móvil apropiada.

Una posible solución a estos puntos pasaría por la no utilización de este tipo de terminales. No obstante, y basándose en la experiencia de utilización de los distintos usuarios, se observa que las actividades más desarrolladas son:

• Lectura del material del curso o tema.
  
• Lectura de preguntas frecuentes.
  
• Evaluación mediante un cuestionario de elección múltiple (multiple choice).
  
• Realización de preguntas, que son contestadas posteriormente vía mail.

Pensando en estas actividades y estudiándolas detenidamente, se llega a la conclusión de que, es cierto que el usuario tiene que estar conectado al servidor, pero a su vez no requiere una respuesta inmediata, por parte de este, y por lo tanto las páginas podrían estar alojadas en el dispositivo local, comportándose de esta forma como un sistema de e-learning off-line.

Para un sistema m-learning, las aplicaciones residirían en los dispositivos móviles, comportándose también como un sistema de m-learning off-line y se evitaría la necesidad de tener que contar con terminales con protocolo WAP u otros.

Esta solución se justificaría por el aprovechamiento del parque actual de PDAs, ampliando el alcance del m-learning a estos usuarios, por el costo cero de uso que implica, al evitar la conexión con el servidor.

Si bien con esta funcionalidad se perdería la sincronía con el servidor, no se la plantea como un reemplazo del sistema de m-learning actual, sino como un complemento o módulo adicional del mismo que se denominará m-learning off-line. Un nuevo módulo que potenciaría el sistema existente y posibilitaría, a través de esta nueva facilidad, aumentar la cantidad de usuarios que lo utilicen.

De esta forma, a la arquitectura de m-learning convencional, el módulo off-line le agrega en el web server una página específica para descargar las aplicaciones en la PC local; que posteriormente, luego de la sincronización, pasarían al PDA para su ejecución.

En el otro sentido, la comunicación con el servidor se realiza automáticamente vía e-mail también en cada sincronización, apreciándose de esta forma la asincronía del módulo.

7.- Ejemplos de algunos proyectos M-Learning, en la actualidad.

Diversas compañías de carácter internacional, están comenzando a experimentar con este tipo de tecnologías implementando contenidos educativos para dispositivos móviles. En este aspecto se ha logrado desarrollar proyectos pilotos a fin de evaluar la efectividad de esta nueva metodología. A continuación veremos algunos ejemplos de estos emprendimientos:

Proyecto	Objetivo
MoLeNet (Mobile Learning Network). Organizaciones participantes: Further Education colleges, Learning and Skills Council (LSC) y Learning and Skills Network (LSN) de Inglaterra.	Promover el aprendizaje electrónico, apoyando emprendimientos y ofreciendo asesoramiento técnico y pedagógico, herramientas de investigación, capacitación profesional, materiales, etc.
MILLEE (Aprendizaje Móvil e Inmersivo para la Alfabetización de Economías Emergentes). Organizaciones Participantes: Nokia y diferentes universidades e Institutos de Ciencia de EE.UU. y China.	Facilitar el acceso a la educación a estudiantes de la India rural que no pueden asistir a clases regularmente a través de juegos didácticos en teléfonos celulares.
Exploratorium Electronic Guidebook Research Project (Proyecto de Investigación para el Desarrollo de una Guía Electrónica). Organizaciones Participantes: Museo Exploratorium de San Francisco, California, HP, National Science Foundation y Consorted Consortium.	Investigar el uso de dispositivos informáticos portátiles y las redes inalámbricas para proporcionar una experiencia de aprendizaje enriquecedora y una interacción más profunda con los visitantes del Museo de Ciencias Exploratorium.

8.- Bibliografía.

http://es.wikipedia.org/wiki/E-learning

http://www.tress.com.mx/esp/ ( Empresa Mejicana líder en soluciones para la administración del Recurso Humano )

http://www.uoc.edu/rusc/3/1/dt/esp/cabero.pdf (Artículo de revista sobre e-learning)

www.educativa.com

www.icdn.cisco.com/global/MX/ee/el/que_es.shtml

www.reforma.com/cultura/articulo/089390/

www.brandonhall.com/public/pdfs/sixstepguidebook.pdf

www.astd.org/astd

http://portal.sol.edu/index.php?option=com_content&view=article&id=73:ique-es-m-learning&catid=49&Itemid=79

http://www.maestrosdelweb.com/editorial/elearning/

Planificacion de Instrucciones

Desenrollamiento de Bucles.

• Técnica de planificación software, realizada por el compilador

• Su objetivo es reducir las detenciones por riesgos de control ( Producidas por saltos ).

• Consiste en replicar el código base del bucle varias veces

􀂋 disminuye el número total de iteraciones (número de saltos)

􀂋 aumenta el tamaño del bloque básico

􀂋 aumenta la flexibilidad para separar instrucciones con dependencias

• Mejora el rendimiento incrementando el código máquina.

• Se realiza, normalmente, en las primeras etapas de la compilación.

Límites

• Reducción de la sobrecarga

Con un mayor número de iteraciones consideradas en el proceso de desenrollamiento se amortiza la sobrecarga, pero hay un límite en el número de iteraciones.

• Tamaño del código

• Limitaciones del compilador:

Si la planificación es muy agresiva, se pueden generar problemas debidos a la escasez de registros.

Segmentación software

• Técnica de planificación software, realizada por el compilador

• Su objetivo es reducir las detenciones por riesgos de datos y el CPIideal

• Consiste en transformar un bucle con instrucciones dependientes e iteraciones independientes en un bucle con instrucciones independientes e iteraciones dependientes.

Ejemplo:

loop:

LD F2, 0(R1)

ADDD F4, F0, F2

SD 0(R1), F4

SUBI R1, R1, #8

BNEZ R1, loop

Iteración 1:

F2, 0(R1)

ADDD F4, F0, F2

SD 0(R1), F4

Iteración 2:

LD F2, -8(R1)

ADDD F4, F0, F2

SD -8(R1), F4

Iteración 3:

LD F2, -16(R1)

ADDD F4, F0, F2

SD -16(R1), F4

Codigo Final:

LD F2, 0(R1)

ADDD F4, F0, F2 Start-up

LD F2, -8(R1)

loop: SD 0(R1), F4 ; almacena en x[i]

ADDD F4, F0, F2 ; suma el escalar k a x[i-1]

LD F2, -16(R1) ; carga x[i-2]

SUBI R1, R1, #8 ; decrementa el puntero en 8

BNEZ R1, loop ; salta si R1 no es cero

SD 0(R1), F4

ADDD F4, F0, F2 Finish-up

SD -8(R1),F4

Modelo MPI: Paso de Mensajes

 La principal característica del modelo de programación de paso de mensajes es que los procesos se comunican entre sí enviando mensajes.

 En el paso de mensajes los datos contenidos en unas variables de un sub-programa se mueven a otro sub-programa.

 En general la siguiente información debe suministrarse en la transferencia de mensajes:

1. Proceso que envía
2. Dónde están los datos a enviar
3. Clase de datos que se envían
4. Cuántos datos hay
5. Quién o quienes (procesos) reciben los datos
6. Dónde deben dejarse los datos recibidos
7. Cuántos datos puede recibir el proceso destino

Ejemplo: MPI

¿Qué es?

• Una especificación de una librería de paso de mensajes.
• No es un producto concreto.
• Un proceso MPI es un programa en C o Fortran77 que se comunica.

con otros procesos MPI mediante llamadas a las subrutinas MPI.

¿Para qué?

• Programación paralela sobre estructuras SPMD y MIMD (computadores paralelos, clusters, redes heterogéneas).

¿Por qué?

• Portabilidad del código fuente.
• Permite implementaciones eficientes en un gran rango de arquitecturas.
• No existía un a biblioteca estándar ampliamente aceptada.

Ejemplo de C:

#include

#include "mpi.h"

main () {

int argc;

char *argv[];

MPI Status st;

int mid, np , num;

MPI Init ( &argc, &argv );

MPI Comm_size( MPI_COMM_WORLD, &np );

MPI Comm_rank ( MPI_COMM_WORLD, &mid );

printf ( "Soy el proceso %d de %d\n", mid, np );

if ( mid == 0 ){

printf(“Dame un número entero: );

scanf(“%d”,&num);

num++;

MPI_Send( &num, 1, MPI_INT, 1 , 0 , MPI_COMM_WORLD);

MPI_Recv( &num, 1, MPI_INT, np - 1 , 0 , MPI_COMM_WORLD, &st);

printf("El resultado es: %d\n", num);

}else{

MPI_Recv(&num, 1 ,MPI_INT, mid - 1, 0 , MPI_COMM_WORLD, &st);

num++;

MPI_Send(&num, 1 ,MPI_INT, (mid+1)%np ,0 ,MPI_COMM_WORLD);

}

MPI Finalize();

} //FIn

Organización de computadores + Procesador MIPS

El pasado día 13/09/10 y con motivo del comienzo de este nuevo curso comenzamos la asignatura de Organización de computadores. Ya adaptados a los nuevos planes de estudio, cual fue nuestra sorpresa cuando nos comunicaron que todas las prácticas serán realizadas con un procesador MIPS.

Para aquellos que nunca han oído hablar de esta familia de procesadores deciros que MIPS (siglas de Microprocessor without Interlocked Pipeline Stages) se conoce a toda una familia de microprocesadores de arquitecturaRISC desarrollados por MIPS Technologies.

Los diseños del MIPS son utilizados en la línea de productos informáticos de SGI; en muchos sistemas embebidos; en dispositivos para Windows CE; routersCisco; y videoconsolas como la Nintendo 64 o las Sony PlayStation, PlayStation 2 y PlayStation portable.

Debido a que los diseñadores crearon un conjunto de instrucciones tan claro, los cursos sobre arquitectura de computadores en universidades y escuelas técnicas a menudo se basan en la arquitectura MIPS. El diseño de la familia de CPU's MIPS influiría de manera importante en otras arquitecturas RISCposteriores como los DEC Alpha.

Para la realización de las prácticas estamos usando un simulador llamado Simula3MS, desarrollado por la universidad de la Coruña, el cual me recuerda a nuestro querido compañero de batalla OllyDbg.

http://simula3ms.des.udc.es/

Por último os dejo un ejemplo sencillo del uso de este simulador, lo único que hace es contar el número de caracteres de una cadena y almacenarlo en memoria.

#Segmento de datos

.data

#.ascii str --> Almacena la cadena str en memoria, ya la termina con el caracter nulo.

cadena: .asciiz "Esto es una prueba "

longitud: .word 0

.text

.globl main

main:

#cargo en $t3 la cadena.

la $t3,cadena

#cargo en $t5 longitud y despues su valor.

la $t5, longitud

lb $t5, 0($t5)

bucle:

lb $t4, 0($t3) # carácter primero de t3

beq $t4,$zero,fin # si es NULL bifurcar a fin

addi $t5,$t5,1 # sumamos uno al contador

addi $t3,$t3,1 # apuntamos al siguiente carácter

j bucle # repetimos

# aquí se llega cuando se encuentra el NULL

fin:

la $t1, longitud #Almacenamos el resultado en la direccion de longitud.

sb $t5, 0($t1) #Almacena el byte de $t5 en la direccion de $t1+0 que es la de longitud

nop

SIMO NETWORK 2010

Hola a tod@s, os comunico que hoy mismo he recibido la invitación para visitar Simo Network 2010, este año son solo 3 días desde el 5 de octubre hasta el 7 estos incluidos y cae entre semana, asi que como el año pasado nos quedaremos sin ir.

De todas formas, para aquellos que si puedan asistir, deciros que si no os mandan invitación, podéis registraros como profesionales en:

http://www.visitantes.ifema.es/ControlUsuarios/login.htm?idioma=es&url=http://www.pre-registro.ifema.es/Pre_registro3/ifema/preinscripciones/registros.jsp?codferia=5325%26tipo=esp

Lo que no estoy seguro es que así, podáis entrar de forma gratuita al recinto.

Este año se sigue notando que la feria no tiene todas las empresas asociadas que nos gustaría, pero quiero pensar que irá creciendo.

Por último me gustaría destacar algunas actividades de interés este 2010.

5 de octubre 2010
SALA 1
17:30 - 18:30
Consejos prácticos para implantaciones rentables

SALA 2
13:00 - 14:00
"Valor de negocio de la nueva arquitectura IBM eX5 para el mundo Intel: ofrezca más que rendimiento"
16:00 - 17:00
“Oportunidades de Negocio para el Canal con Dell – Presentación del programa de canal PartnerDirect”
17:30 - 18:30
“Oportunidades de Negocio para el Canal con Dell – Cómo ganar proyectos con las soluciones de almacenamiento iSCSI de Dell “


6 de octubre 2010
SALA 1
11:30 - 12:30
“Pandalabs. Conoce como se comporta un virus y aprende a combatirlo”
13:00 - 14:00
“Construye y gestiona la política de seguridad que se adapta a tus clientes”
16:00 - 17:00
"Acelerando el valor de su negocio con Smarter Systems: optimizando Hardware, Software y Servicios"
17:30 - 18:30

SALA 2
17:30 - 18:30
TPV, una categoría con alto potencial de crecimiento y rentabilidad de la mano de HP y SAGE


7 de Octubre de 2010
SALA 1
11:30 - 12:30
“Procesos, herramientas y oportunidades diseñadas para el canal”
13:00 - 14:00
"Nuevas oportunidades de Negocio a través del Cloud y la Convergencia"

SALA 2
11:30 - 12:30
“Cómo mejorar la eficiencia en el Almacenamiento y Protección de Datos de sus clientes mediante tecnologías de Deduplicación, Archivado y Virtualización”
16:00 - 17:00
"Samsung, Virtualización real y Soluciones de impresión: La revolución en el puesto de trabajo"

www.simonetwork.es