Tercer y Cuarto enfoques para programar compiladores paralelos.

En 1988 McGraw y Axelrod identificaron cuatro formas distintas de desarrollar software (aplicaciones) para las computadoras paralelas:

1. Extender o enriquecer un compilador existente para que traduzca programas secuenciales en programas paralelos.
2. Extender o enriquecer un lenguaje existente con nuevas operaciones que permita a los usuarios expresar el paralelismo.
3. Agregar una nueva capa de lenguaje paralelo encima de un lenguaje secuencial existente.
4. Definir totalmente un nuevo lenguaje paralelo así como su compilador.

Tercer enfoque: AGREGAR UNA CAPA DE PROGRAMACIÓN PARALELA

Se puede pensar en la programación paralela como tener dos capas. La capa inferior contiene el núcleo (core) del cómputo, en donde un proceso manipula su parte de los datos para producir su parte del resultado. Un lenguaje de programación secuencial existente se adaptaría para expresar esta parte de la actividad. La capa superior controla la creación y sincronización de los procesos y la partición de los datos entre los procesos. Estas acciones podrían ser programadas usando un lenguaje paralelo (quizá un lenguaje de programación visual). El compilador sería responsable de traducir estas dos capas del programa paralelo en código listo para su ejecución sobre una computadora paralela.

Dos ejemplos de este enfoque son el ambiente CODE (Computationally Oriented Display Environment) y el ambiente HENCE (Heterogeneous Network Computing Environment). Estos sistemas permiten al usuario representar un programa paralelo como un grafo dirigido, donde los nodos representan procedimientos secuenciales y los arcos representan dependencias de datos entre los procedimientos.

Este enfoque requiere que el programador aprenda y use un nuevo sistema de programación paralelo, lo cual puede ser la razón por la que no ha captado mucha atención en la comunidad de programación paralela. Mientras que los prototipos de investigación están siendo distribuidos, no se conoce ningún sistema comercial basado en esta filosofía.

Cuarto enfoque: CREAR UN LENGUAJE PARALELO

El cuarto enfoque es darle al programador la habilidad de expresar explícitamente operaciones paralelas.

Una forma de soportar la programación paralela explícita es desarrollar un lenguaje paralelo desde cero. El lenguaje de programación OCCAM es un ejemplo famoso de este enfoque. Con una sintaxis sorprendentemente diferente de los lenguajes tradicionales imperativos, este lenguaje soporta tanto la ejecución de procesos en paralelo como secuenciales, así como la comunicación y la sincronización entre ellos.

Otra forma de soportar el paralelismo explícito es agregar construcciones paralelas a un lenguaje ya existente. Ejemplos de este enfoque son los lenguajes FORTRAN 90, HIGH PERFORMANCE FORTRAN y C*.

Anteriormente se mencionó la ironía de un programador codificando un algoritmo inherentemente paralelo en lenguaje de programación secuencial y un compilador trabajando para redescubrir el paralelismo. Un lenguaje que soporte el paralelismo explícito cambia la relación entre el programador y el compilador de adversarios a aliados.

Agregar construcciones paralelas a un lenguaje de programación existente o crear por completo un nuevo lenguaje de programación paralelo requiere el desarrollo de nuevos compiladores. Aún y cuando se adopte un lenguaje estándar, típicamente les lleva años a los vendedores desarrollar compiladores de alta calidad para sus sistemas paralelos.

Algunos lenguajes paralelos, tales como C*, no fueron adoptados como estándar. En esta situación muchos vendedores en competencia decidieron no proporcionar compiladores para el lenguaje en sus máquinas. Cuando esto pasa, la portabilidad de códigos se encuentra severamente en peligro.

Otra barrera para la adopción de nuevos lenguajes de programación es la resistencia del usuario. Cuando nuevas construcciones paralelas se agregan a un lenguaje de programación, los programadores deben aprender cómo usar estas nuevas construcciones. Muchos programadores están renuentes a tomar esta transición.

Más Ejemplos:

*Concurrent Pascal: diseñado por Brinch Hansen en 1975.

*Chapel: desarrollado en el 2010

*X10: basado en java y desarrollado en el 2004 por la IBM.

* NESL

*Cilk

*ZPL

*Linda

*Parlog

Referencias

-http://es.slideshare.net/neztooor7/presentacin-lenguajes-paralelos

-Elfego Gutierrez. "Programación Paralela y Distribuida".

Algoritmos de Búsqueda.

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

BUSQUEDA BINARIA

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado. Esta búsqueda utiliza un método de “divide y vencerás” para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sublista. Este tipo de búsqueda se utiliza en vectores ordenados.

Código Python

def busqueda_binaria(lista, x):
    Precondición: lista está ordenada

    Devuelve -1 si x no está en lista;

    Devuelve p tal que lista[p] == x, si x está en lista

   

    # Busca en toda la lista dividiéndola en segmentos y considerando

    # a la lista completa como el segmento que empieza en 0 y termina

    # en len(lista) - 1.

    izq = 0 # izq guarda el índice inicio del segmento

    der = len(lista) -1 # der guarda el índice fin del segmento

    # un segmento es vacío cuando izq > der:

    while izq <= der:

        # el punto medio del segmento

        medio = (izq+der)/2

        print "DEBUG:", "izq:", izq, "der:", der, "medio:", medio

        # si el medio es igual al valor buscado, lo devuelve

        if lista[medio] == x:

            return medio

        # si el valor del punto medio es mayor que x, sigue buscando

        # en el segmento de la izquierda: [izq, medio-1], descartando la

        # derecha

        elif lista[medio] > x:

            der = medio-1

        # sino, sigue buscando en el segmento de la derecha:

        # [medio+1, der], descartando la izquierda

        else:

            izq = medio+1

        # si no salió del ciclo, vuelve a iterar con el nuevo segmento

    # salió del ciclo de manera no exitosa: el valor no fue encontrado

    return -1

# Código para probar la búsqueda binaria

def main():

    lista = input ("Dame una lista ordenada ([[]] para terminar): ")

    while lista != [[]]:

        x = input("¿Valor buscado?: ")

        resultado = busqueda_binaria(lista, x)

        print "Resultado:", resultado

        lista = input ("Dame una lista ordenada ([[]] para terminar): ")

BÚSQUEDA SECUENCIAL

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.

Código Python

def sequentialSearch(alist, item):
   pos = 0
   found = "El valor no está en la lista"

   while pos < len(alist) and not found:
       if alist[pos] == item:
           found = "Se encontró el valor!"
       else:
           pos = pos+1

   return found



lista=[]
cn=int(raw_input("Cantidad de numeros a ingresar: "))

for i in range(0,cn):
    lista.append(int(raw_input("Ingrese numero %d : " % i)))


n=int(raw_input("Dame el numero a buscar:  "))

print(sequentialSearch(lista, n))

Referencias

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheSequentialSearch.html http://macabremoon0.tripod.com/id2.html
https://ronnyml.wordpress.com/2009/07/09/busqueda-lineal-y-busqueda-binaria/
http://librosweb.es/libro/algoritmos_python/capitulo_8/busqueda_binaria.html

Procesamiento Pipeline

Procesador Pipeline

Un solo computador el cual puede realizar simultáneamente operaciones de cálculos en determinadas secciones, con diferentes estadios de completitud. Los procesadores pipeline se basan en el principio de dividir los cálculos entre una cantidad de unidades funcionales que operan simultáneamente existiendo superposición.

 COMPUTADORES PIPELINE

Veamos el ejemplo de un pipeline de cuatro etapas: el proceso de ejecución de una instrucción en un computador digital envuelve cuatro pasos principales: levantar la instrucción de memoria (Instruction Fetch - IF); identificar la operación que debe efectuarse (Instruction Decoding - ID); levantar los operandos si son necesarios en la ejecución (Operand Fetch - OF); y ejecutar la operación aritmético lógica que ha sido decodificada. Antes de comenzar a ejecutar una nueva instrucción deben completarse estos cuatro pasos. La idea de un computador pipeline la vemos en la figura 4.9 : hay cuatro etapas

 IF, ID, OF y EX ordenadas de forma de una "cascada lineal".

 Las instrucciones sucesivas se ejecutan de forma superpuesta. La diferencia entre la ejecución superpuesta de instrucciones y la ejecución no superpuesta secuencial se muestra en los diagramas de espacio/tiempo de las Fig. 4.10

CLASIFICACIONES DE PROCESADORES PIPELINE. 

De acuerdo a los niveles de procesamiento, Händler (1977) ha propuesto el siguiente esquema de clasificación para los procesadores pipeline:

 Pipelines aritméticos La ALU de un computador puede dividirse para hacer operaciones de pipeline en varios formatos. Hay ejemplos bien claros en los pipelines usados en la Star-100, TI-ASC, Cray-1 y Cyber 205 (Fig. 4.14). 4.6.2. - Pipelines de instrucción La ejecución de un flujo de instrucciones puede hacerse en forma de pipeline, como vimos en la primer parte del capítulo, superponiendo la ejecución de la instrucción actual con las acciones de levantar, decodificar instrucciones y levantar operandos. Esta técnica también es conocida con el nombre de lookahead de instrucciones. Casi todos los computadores de alta performance actuales tienen pipelines de instrucción.

 Pipelines de procesador Se refiere al procesamiento del mismo flujo de datos por una cascada de procesadores, cada uno de los cuales procesa una tarea específica. El flujo de datos pasa el primer procesador, cuyo resultado se almacena en un bloque de memoria intermedia, que también es accesible por el segundo procesador. Este pasa el resultado refinado al tercero, y así siguiendo. En el momento en que Händler escribió su clasificación de los pipelines aún no existían implementaciones de pipelines de procesador (Fig. 4.16).

Referencias

http://msanchez.usach.cl/lcc/Arquitectura-Pipeline.pdf