Supercómputo con grandes matrices de dispositivos móviles · 2018-10-26 · •Cluster puede ser...

Supercómputo con

grandes matrices de

dispositivos móviles

Orador Ing. Carlos Alejandro Pérez

Universidad Tecnológica Nacional

07.06.2018

IEEE COMPUTER INTELLIGENCE SOCIETY CAPITULO ARGENTINA

Objetivo

•Construir un sistema de cálculo de alta performance utilizando una matriz de cantidades masivas de dispositivos móviles, en plataformas disímiles.•Caso de uso → fase de entrenamiento de una red

neuronal.

PRIMERA PARTE

¿ES POSIBLE?

Primera parte: ¿es posible?

¿Qué es la convergencia?• Es la evolución independiente de tecnologías que alcanzan a

un momento dado la habilidad de ejecutar tareas similares.

SOFTWARE MICROELECTRÓNICASISTEMA

CONVERGENTE

REDES

Primera parte: ¿es posible?

¿Hemos alcanzado la convergencia?

ES POSIBLE QUE SÍ

Las redes, hardware y software han dado enormes pasos.Ya se tuveron los primeros ejemplos de sistemas convergentes (Ubuntu Unity 8, Windows 10)Subsisten enormes problemas y desafíos.

Estamos en los albores de una nueva época (ca. 2018)

Primera parte: ¿es posible?

La microelectrónica convergentePrimera parte: ¿es posible?

Procesador. Memoria. Almacenamiento• Los servicios actuales se han visto impulsado por la

explosión de dispositivos móviles• La microelectrónica debe atacar simultáneamente dos

frentes: SERVIDOR y CLIENTE.

Fuente: “The Zettabyte Era: Trend and Analysis (Mayo 2015)Primera parte: ¿es posible?

Incremento constante en clientes

Fuente: “The Zettabyte Era: Trend and Analysis (Mayo 2015)Primera parte: ¿es posible?

Entretenimiento demandante

Fuente: “The Zettabyte Era: Trend and Analysis (Mayo 2015)

Primera parte: ¿es posible?

Crecimiento explosivo•7294 millones de personas vs. 7620 millones líneas

celulares•Crecimiento de datos móviles 2015 → 2021: 10X•CAGR (compound annual growth rate) 25% en LTE•Para 2021 → 4.100 millones de líneas LTE.• Suponiendo que en 2021 esté en uso un perfil muy

conservador (ca. 2015):• ARM 4-core @1.2GHz & 2GB RAM

•Poder de cómputo latente sin ser aprovechado

Primera parte: ¿es posible?

Potencia latente•Con un perfil muy conservador (ca. 2015):•ARM 4-core @1.2GHz & 2GB RAM

•Y sólo 1% de antedicha cantidad de móviles

•3.74 exa-instructions per second (EIPS)

•1.9 exa-floating point operations per second(EFLOPS)

•Memoria en bruto de 7.7 exa bytes.

Primera parte: ¿es posible?

¿La red 4G es lenta para una grilla?El sistema nervioso humano trasmite de 55 a 200 m/s

P: ¿Cómo podemos hacer todo lo que hacemos con una red tan lenta?

R: Masividad de neuronas y conexiones.

No es posible replicar esa masividad con la microelectrónica moderna.

Primera parte: ¿es posible?

¿Computación cuántica?

No resuelve cualquier problema

La computación actual →mucho futuro aún

Server: IBM Power 8 (2015 - mainframe)

12 núcleos96 hilos96 MB caché interno128 MB caché externo4GHz

Power 920 núcleos?160 hilos?Nvidia Tesla GPU?

Server: IBM Power 9 (2017 - mainframe)

Power 9• 8.000 millones de transistores (4.200) • Hasta 24 nucleos (12 núcleos)• 14nm FinFET (22nm SOI)• PCIe Gen4 (PCIe Gen3)• 120 MB shared L3 cache (96 MB

shared L3 cache)• Multihilos de 4-vías y 8-vías

simultáneos (8-way simultaneous multithreading) → 192 hilos

• Ancho de banda 120 or 230 GB/sec (230 GB/sec)

Server: Intel Knights Landing (Nov-2015)

•MCDRAM (DRAM multicanal) 5x velocidad

•215 watts máx.

•16 GB RAM on-chip

•72 núcleos, 4 hilos por núcleo = 288 hilos

Server: ¿Intel Xeon Phi v3 2017?...No

Server: MCDRAM

•Memoria hibrida.

•16 GBytes en chip. 500 GBytes/seg.

•Puede ser• Todo caché• RAM del sistema• Parte caché, parte

RAM de sistema

Client: Qualcomm Snapdragon 820 S.o.C. (2016)

64 bitsFINFET (familia lógica)14 nanómetros2,2 GHz (hasta 3GHz)4 núcleos

HDMI 2.0 → 4K 60 fpsMiracast→ 4K 30 fps

Image Signal Processor25 megapíxels máx.14 bits

Por primera vez, mejora de 2x en un solo salto de generación.

WiFi 802.11 ad 4.6 Gbps @ 60 GHzLTE Cat- 12 @ 600 MbpsLTE - U

CLIENT: Intel Atom x5 y x74 núcleos4 hilos1.6 GHz → 2.4 GHz2MB Caché2 watts16 shaders GPUH.265 HEVC

Qualcomm Snapdragon 835

Avanza sobre la compatibilidad binaria con Windows (?)

Un sistema Android ejecuta binarios Win32 instalados físicamente a velocidad casi-nativa.

Redes en la convergencia

Limitaciones actuales• Los protocolos se definieron siempre para solucionar

un problema específico (árbol vs. bosque)

• En una red compleja, agregar un (1) dispositivo implica:• Tocar múltiples switches, routers, firewalls, portals.• Actualizar ACLS, VLAN, QOS, protocolos → sólo accesibles

desde el mismo dispositivo

• La complejidad impide aplicar un conjunto consistente de políticas en la red• En una red mobile, puede llevar días reconfigurar listas de

acceso, seguridad y calidad de servicio

Limitaciones actuales• Escalamiento muy difícil.

• En los data centers existen miles de servidores• ISP utilizaban modelos predictivos del tráfico• Con los servicios actuales y la masividad, el tráfico es

impredecible

•Ciclos no sincronizados entre Carrier y Vendor• Un proveedor de servicios (Google) depende de la

capacidad del vendor (HP, Cisco) en innovar.• Ciclos de recambio tecnológico: 36 meses o más.• Se necesita un modelo donde el Carrier pueda actualizar

la red más rápidamente → SDN

Redes definidas por software (SDN)• La red actual es una estructura arbórea, propia de

sistemas cliente-servidor, pero inadecuada por• Cambios en los patrones de tráfico (este-oeste = P2P en

vez de norte-sur = C-S)• IT pasa a ser de consumo masivo (smartphones)• Explosión de servicios en la nube• Datacenters de la nube requieren constante ampliación de

la red, miles de servidores.

Red es estática <> Servicios son dinámicos.

Redes definidas por software - SDN•Una SDN permite

administrar la red a través de capas de abstracción, los servicios se controlan por software, que interactúa con “el metal” a través de una interfaz, ej. OpenFlow

Redes definidas por software - SDN• El firmware de cada

dispositivo (enrutador, conmutador, etc.) se migra a computadoras fácilmente accesibles.

•Un solo punto lógico de administración

• Este modelo simplificado es programable.

¿Qué es LTE-U?• Long Term Evolution – Unlicensed.

•Propuesto por Qualcomm

•Usar el espectro “descongestionado” de 5GHz que utiliza WiFi, pero coexiste con ella.

• Los operadores celulares podrían ofrecer en esa banda sus servicios LTE

•Muy controversial.

•Conglomerado tecnológico a partir del 2-10-2015•Contiene a Google después de la reestructuración

Gigabit internet

• 1 GBPS download• 1 GBPS upload

LTE-U: en contra

WiFi 802.11 AD/ AF / AH

El Software convergente

Linux Ubuntu 8

Sistemas operativos convergentes

•Plataforma = CPU + sistema operativo

•Compatibilidad binaria• 32 – 64 bits• Diferencias entre Big Endian (Motorola) y Little-Endian

(Intel)

•Buen rendimiento en factores de forma pequeños

• Interfaz del usuario unificada en el paradigma, adaptable en tiempo de ejecución

Desafíos en S.O.

Orden “natural” según está escritoOrden en el cual entran los bytes por la red

Orden “inverso” que facilita acceso a datos

Software convergente• Juegos y entretenimiento

•Comunicaciones y procesamiento de señales

•Visión por computadora y aplicaciones

•Redes definidas por software

•Redes y aplicaciones vehiculares inteligentes

• Salud remota.

Sistema convergente

Windows 10

Desktop

PC

2 en 1

Mobile

Tablet

Phablet

Phone

Xbox

Xbox

IoT

Band

IoT headless

RaspberryPI

Home Automation

Surface Hub

Surface hub

Holographic

Hololens

UWP (Universal Windows Platform):• Un mismo kernel para todos los factores de forma• Una API para cada factor de forma.

W

Proyección de Lenguaje (2012)

Código Binario Puro (32-64 bits)

Maquina virtual .NET , Java

Browser con marco de ejecución

Objeto

IInspectable

IUnknown

C++ AppProjectio

n

CLR

C#/VB

App

Projectio

n

HTML App

Ch

akra

Projectio

n

Windows Metadata

(antes MS CLI)

Windows Runtime (8.0, 8.1)C#, C++, VB.NET y JavascriptTodo compilado

¿Evolución o Crisis? 2015

Nativo, sin VMTodo se compila a binario Intel o

ARM

Gran dependencia del servicio NUGET

para instalar bibliotecas

Framework modular open-source (2.6

millones de líneas), corre en Windows,

Linux y Android

Self-hosted compilerOpen Source

Deja de ser blackbox para pasar a tener APIs

Nuevo Jitter 64 bitsPensado para carga de trabajo en

datacenters. Varios órdenes de magnitud más rápido. Vectores.

¿obsoleto?

Paginas web sin servidor web

Interfaz unificada XAML

Snapdragon 835 compatible con binarios Win32 (Intel 32 bits) 2017

CHPE: COMPILED HYBRID PORTABLE EXECUTION.Al instalar una DLL de Intel x86 32 bits, se traduce binariamente, instrucción por instrucción, a ARM 64 bits. Pero la interfaz que exhibe es 32 bits

ARM CODE + 32 bits entry points

Browsers

Contenido de 200 MBServidor IIS 2.7GBGoogle Chrome 1 GB

Todo es servidor, todo es cliente

Smartphone corriendo un portal

HTTP para diagnostico y gestión de software

Smartphone visualizando en el browser la pagina HTML 5 + Javascript. No se

admiten plugins en los browser móviles

Veamos ahora

PARALELISMO

Fin de la introducción

Potencia de cálculo → LímiteCausas del límite•Ruido electromagnético

• Límites en la tecnología de la litografía (10 nm)

•Arquitectura de la familia lógica difícilmente mejorable

Workaround• Aumentar el paralelismo

• A bordo del procesador• Aumentando los nodos de cómputo

• Implica tener frameworks adecuados en software

PAR1: Memoria distribuida compartida

dynamic distributed mobile computing, D2MCLiang,Hsieh, & Lyu, 2007

PAR1: D2MC: dynamic distributed mobile computing, D2MC• Si el procesador se adapta 300 veces por segundo a la

carga instantánea de cómputo

•Podremos considerar que la energía eléctrica consumida para resolver un problema distribuido, se distribuye entre los nodos también.• ¿Qué implicancias tendría sobre la entropía real vs.

información?

PAR2: Interfaz de pase de mensajes MPI

SCATTERNETDonegan, Doolan, & Tabirca, 2008

PICO-RED

PAR3: PVM, parallel virtual machines• VM: es una máquina lógica única• Ejecuta sobre cluster o conjunto de procesadores con memoria

distribuida• Cluster puede ser de hardware heterogéneo , tiene una capa de

abstracción HAL• Unidad de paralelismo es la TAREA: subproceso que se conmuta

a si mismo entre tareas de cálculo puro y tareas de Comunicaciones• Ejemplo: TRAVELER (Wims, B., Xu, C. Z, 1999)

• Colección de agentes Java desplegados en WAN.• Bytecodes viajan de un nodo a otro para se ejecutados.• Utiliza matrices distribuidas para la comunicación• Demostró que una solución pura OO es posible en entorno

distribuído utilizando VM y código móvil.

Paralelismo de redes neuronalesTipo paralelismo Hilos de ejecución Paralelismo tipo

Sesión de entrenamiento

Por cada sesión de entrenamiento

De sesión de entrenamiento

Datos de ejemploPor cada conjunto de ejemplos

dentro de una misma sesiónDe conjunto de ejemplos de

entrenamiento

Capa de neuronas Por cada capa de neuronasDe capas (hacia adelante y hacia

atrás)

Neurona Por cada neurona en una capa De neurona

Peso sinápticoPara todos los pesos sinápticos de

la neuronaDe peso sináptico

Bits en el peso sináptico

Para todos los bits del valor del peso sináptico

De bit de peso

Nordström, 1995

AN

TEC

EDEN

TES

Redes y super-redes (1994)

• Una red neuronal distribuida es• Una super-red• Un numero determinado de sub-redes

• Cada sub-red se puede entrenar independientemente de las otras. • Una vez entrenadas, las sub-redes se interconectan de tal forma que

la información puede circular a través de lared como un todo.

• La red no puede entrenarse como un conjunto entero, sino que las sub-redes deben hacerlo independientemente

• Una red está entrada si todas sus sub redes los están

Arcand & Pelletier, 1994

AN

TEC

EDEN

TES

Partición de datos (1997)• Cada procesador entrena la red utilizando un

subconjunto de datos

• Los cambios obtenidos se combinan y los nuevos valores se aplican a la red una vez que la fase de entrenamiento hafinalizado.

• Restricción: la sincronización debeocurrir una sola vez al finalizar el lapso de entrenamiento debido a que la misma operación se ejecuta para cada subconjunto de datos.

Rogers & Skillicorn, 1997

AN

TEC

EDEN

TES

Gran red distribuida (2001)

•RNA virtual, con algoritmo de retro-propagación

•Conjunto de PCs interconectadas

•Problemas• Complejidad de la red → dificultad de entrenamiento• Gran cantidad de ramas entre nodos• Fase de retro propagación → cuello de botella de red

Milea & Svasta, 2001

AN

TEC

EDEN

TES

Optimizando la comunicación (2005)Se parte de dos modelos, y se los combina en un sistema híbrido

AN

TEC

EDEN

TES

Modelo cooperativo de RNA de entornodistribuido híbrido

Yang,Wang, & Su, 2005

AN

TEC

EDEN

TES

Matriz de computo móvil•Cada nodo de cálculo es un smartphone

• Se conectan por red inalámbrica (WiFi, WAN)• Operador celular: alguien que desplegó la red por

nosotros

•Ventaja del smartphone• Ampliamente programable• Ampliamente conectable• Importante potencia de cálculo• System on a chip• Dispositivos de visualización y entrada integrados

Diagrama simplificado

HTTPServer

Router WiFi APFirewall

MNIST database

PC #1 PC #n

Smartphone #1

Smartphone #2Tablet #1

Laptop #1

Smartphone #nSmartphone #3

Sele

ctio

n fo

r P

C#1

Controlpage

INTERNET

Carrier base station

SignalRservice

Odataservice

Entrenamiento en paralelo por patrones

1• RNA completa se copia a cada dispositivo

2• Cada dispositivo procesa un sub conjunto de datos, durante una época.

3

• Cada dispositivo transmite sus resultados al resto, y recibe los resultados del resto y los combina con los propios (suma de los pesos sinápticos, etc.)

4

• Se verifica si se alcanzó la condición de error mínimo

• SI: red entrenada; NO: seguir con el proceso.

Dahl, Mc Avinney, & Newhall, 2008

Concepto de partida (impracticable)

Paralelismo de datos

Comunicación con estándar abierto

•OPEN DATA Protocol• Transmisión y recepción de datos entre servidor y móviles

•HTML 5 WebSockets• Se puede montar una WebApi que utilice este modelo.

Los resultados se devuelven como documentos JSON

•HTML 5 persistent connection• Permite emular un sistema distribuido con estado sobre

HTTP inherentemente state-less.

servicio

Técnicas necesarias• Intra-process parallelism

•Asynchronous calls.

• Lazy evaluation techniques

•Generic collections

•Concurrent collections.

• Support for universal applications (deprecated?)

• Support for binary compatibility with Android• Snapdragon 835 or later processor

Open DataLos datos de un RDBMS se exponen a la web como documentos XML o JSON.Las consultas se realizan invocando una llamada HTTP estándar, como si navegásemos en la internet.

http://host/servicio/Productoshttp://host/servicio/Rubros(1)http://host/servicio/Productos/Modelo.ElMasCaro()

SignalR•Proporciona respuesta real-time utilizando estándar

abierto HTTP (!)

•Utiliza hasta 4 transportes para lograrlo• HTML 1.1 Forever Frame• AJAX Long-polling• HTML5 Server-sent events• HTML 5 Websocket

•Código compacto, Agnóstico a la conexión, Reconexión automática, Backplane con scale-out

SignalR – llamada en reverso

Clases neuralnetwork

Clases: Colecciones de objetos

Colecciones de objetos

•Matriz convencional. Un elemento=una neurona

• Lista. N neuronas, se agregan al final.

•Diccionario. N neuronas con índice b-tree

•Bolsa de objetos.

•Colección hash. N neuronas con método de almacenamiento y acceso basado en hash (25% menos eficiente en RAM)

Paralelismo de cálculo• Los modernos frameworks móviles tienen amplias

facilidades para cálculo paralelo.• Las tareas en segundo plano no son servicios o daemons

convencionales• Deben verse como código ejecutable in-process.• No se admiten servicios reales en segundo plano que no estén

previstos en el framework.• Extraordinariamente difícil comunicar AppA con AppB en un

mismo dispositivo (sandboxing)• Relativamente fácil conectar AppA y AppB a servicios fuera del

dispositivo.

Paralelismo de cálculo en el móvil•Por ello, todo cálculo paralelo debe ejecutarse en un

solo proceso de usuario.• El framework

• distribuirá automáticamente el cálculo en los hilos disponibles del procesador.

• Sincronizará automáticamente el conjunto de resultados• Pondrá en cola las tareas si éstas son más que los núcleos

disponibles del procesador y las irá ejecutando a medida que éstos queden libres.

Paralelismo de cálculo en el móvil

•Un proceso en el hilo principal• N subprocesos en paralelo en hilos secundarios (1 en cada

núcleo del procesador)

• El subproceso no puede comunicarse directamente al hilo principal donde ejecuta la GUI.• Lo hace a través de un despachador, objeto que puede

interactuar con todos los subprocesos de un proceso

Ejemplo de paralelismo de tareas (2do. Nivel), perceptrón

Cada salida tiene una colección de ramas. Por cada salida se genera una tarea paralela, que suma los valores de entrada , ejecuta la activación y calcula el error.

Paralelismo de tercer nivel?

ES POSIBLE, CON COLECCIONES

CONCURRENTES

Colecciones concurrentes

• Son aquellas que pueden ser escritas al mismo tiempo desde N subprocesos.

• El framework gestiona automáticamente la ejecución.

Diccionario concurrente

¿Podemos paralelizar datos, luego tareas, luego colecciones?• Si, pero no conviene.

•Paralelizar la colección implica que el subproceso debería generar otro subproceso.

• La gestión de este escenario gasta más recursos que la ganancia en performance.

•→ En 1 móvil = 1 nivel de paralelismo.

Tiempo(n_dispositivos)

Medición de las colecciones en RAMSnapdragon 400, 1 GB RAM.

Tiempos de creación de coleccionesSnapdragon 810, 3GB RAM

Programación asincrónica• Es obligatoria en dispositivos móviles.

•No existen bases de datos on-board• ¿Qué pasó con HTML5 local database?

• Los datos deben traerse desde servicios en la nube

•Un servidor proporciona los datos de entrenamiento y los metadatos para construir la red neuronal en memoria en cada móvil.

• La conexión entre el móvil y el servidor es WLAN o WiFi

•Código es rápido, servidor es lento → asincrónica.

async Task<int> MiTarea() {

// crea clienteHttpClient client = new HttpClient(); // GetStringAsync retorna una Task del tipo <string>Task<string> getStringTask = client.GetStringAsync("http://www.misitio.com");

// ejecute codigo que NO DEPENDA del resultadpTrabajoIndependiente1();TrabajoIndependiente2();TrabajoIndependiente3();// aqui se NECESITA el resultado, el codigo debe ESPERARLO// el control se devuelve al llamador de MiTarea()// la primitiva await bloquea la ejecuciónstring cualEsMiSitio = await getStringTask; // con el resultado, el control se devuelve y se continúa

return cualEsMiSitio.Length;}

Recupera del servidor los datos

public async Task GetTrainingInputs1(int startt2ID, int endt2ID) {

// recuperar datos de entrenamiento, imágenes 1 a 100 inclusivestring lcUri = "http://localhost/t1?$filter=t2ID+ge+1+and+t2ID+le+100"lcUri = System.Net.WebUtility.HtmlEncode(lcUri);Uri serviceuri = new Uri(lcUri, UriKind.RelativeOrAbsolute);HttpClient http = new HttpClient();HttpResponseMessage response = http.GetAsync(serviceuri);

string json = await response.Content.ReadAsStringAsync();SizeRetrieveTrainingData = json.Length;JToken token = JToken.Parse(json);JArray aj = (JArray)token.SelectToken("value");TrainingInputList.Clear();TrainingInputList = aj.ToObject<List<t1>>();

}

Código real (petición de datos al servidor

Medición de la potencia consumida

•Tarea extraordinariamente difícil (por la API).

•Números macro:•AMD Threadripper @ 2.2 GHz, 16-core, 32 threads100W+• Intel I7 8850 mobile: 6-core, 12 threads @2.3-4.6 GHz. 45W.•Snapdragon 835. big.LITTLE, 8-core, 8-threads @2.45GHz+@1.9GHz. 2W

Nuevos desafíos

•La ley de Amdahl y la de Gustafson se afecta por procesadores Asimetrcos

•Y dejan de aplicarse en procesadores móviles componibles.•Un procesador que se “cablea” en tiempo real dependiendo de la demanda.

¿Preguntas?

•Carlos Alejandro Pérez

• cperez@rec.utn.edu.ar