DiDi: Mitigating the Performance Impact of TLB Shootdowns Using a Shared TLB

Carlos Villavieja, UPC

@PACT 2011

Translation Lookaside Buffers (TLBs) are ubiquitously used in modern architectures to cache virtual-to-physical mappings and, as they are looked up on every memory access, are paramount to performance scalability. The emergence of chipmultiprocessors (CMPs) with per-core TLBs, has brought the problem of TLB coherence to front stage. TLBs are kept coherent at the software-level by the operating system (OS). Whenever the OS modifies page permissions in a page table, it must initiate a coherency transaction among TLBs,a process known as a TLB shootdown. Current CMPs rely on the OS to approximate the set of TLBs caching a mapping and synchronize TLBs using costly Inter-Proceessor Interrupts (IPIs) and software handlers. In this paper, we characterize the impact of TLB shootdowns on multiprocessor performance and scalability, and present the design of a scalable TLB coherency mechanism. First, we show that both TLB shootdown cost and frequency increase with the number of processors and project that softwarebased TLB shootdowns would thwart the performance of large multiprocessors. We then present a scalable architectural mechanism that couples a shared TLB directory with load/store queue support for lightweight TLB invalidation, and thereby eliminates the need for costly IPIs. Finally, we show that the proposed mechanism reduces the fraction of machine cycles wasted on TLB shootdowns by an order of magnitude.

Optimizing Data Layouts for Parallel Computation on Multicores

Yuanrui Zhang, Wei Ding, Jun Liu, and Mahmut Kandemir

The Pennsylvania State University

@PACT 2011

The emergence of multicore platforms offers several opportunities for boosting application performance. These opportunities, which include parallelism and data locality benefits,require strong support from compilers as well as operating systems. Current compiler research targeting multicores mostly focuses on code restructuring and mapping. In this work,we explore automatic data layout transformation targeting multithreaded applications running on multicores. Our transformation considers both data access patterns exhibited by different threads of a multithreaded application and the on chip cache topology of the target multicore architecture. It automatically determines a customized memory layout foreach target array to minimize potential cache conflicts acrossthreads. Our experiments show that, our optimization brings significant benefits over state-of-the-art data locality optimization strategies when tested using 30 benchmark programs on an Intel multicore machine. The results also indicate that this strategy is able to scale to larger core counts and it performs better with increased data set sizes.

Phase-Based Application-Driven Hierarchical Power Managementon the Single-chip Cloud Computer

Nikolas Ioannou @ PACT 2011

University of Edinburgh

To improve energy efficiency processors allow for Dynamic Voltage and Frequency Scaling (DVFS), which enables changing their performance and power consumption on-thefly.Many-core architectures, such as the Single-chip Cloud Computer (SCC) experimental processor from Intel Labs,have DVFS infrastructures that scale by having many more independent voltage and frequency domains on-die than today’smulti-cores.This paper proposes a novel, hierarchical, and transparent client-server power management scheme applicable to such architectures. The scheme tries to minimize energy consumption within a performance window taking into consideration not only the local information for cores within frequency domains but also information that spans multiple frequency and voltage domains.We implement our proposed hierarchical power control using a novel application-driven phase detection and prediction approach for Message Passing Interface (MPI) applications, a natural choice on the SCC with its fast on-chip network and its non-coherent memory hierarchy. This phase predictor operates as the front-end to the hierarchical DVFS controller,providing the necessary DVFS scheduling points.Experimental results with SCC hardware show that our approach provides significant improvement of the EnergyDelayProduct (EDP) of as much as 27.2%, and 11.4% on average,with an average increase in execution time of 7.7% over a baseline version without DVFS. These improvements come from both improved phase prediction accuracy and more effectiveDVFS control of the domains, compared to existing approaches.

No More Backstabbing... A Faithful Scheduling Policy for Multithreaded Programs

PACT Conference 11 Octubre de 2011, 17:00 Spanish Time, Galveston Island TX, USA, Hotel Galvez.

Kishore Kumar Pusukuri, Rajiv Gupta, and Laxmi N. Bhuyan

Efficient contention management is the key to achieving scalable performance for multithreaded applications running on multicore systems. However, contention management policies provided by modern operating systems increase context-switches and lead to performance degradation for multithreaded applications under high loads. Moreover, this problem is exacerbated by the interaction between contention management policies and OS scheduling polices. Time Share(TS) is the default scheduling policy in a modern OS such as OpenSolaris and with TS policy, priorities of threads change very frequently for balancing load and providing fairness inscheduling. Due to the frequent ping-ponging of priorities, threads of an application are often preempted by the threads of the same application. This increases the frequency of involuntary context-switches as wells as lock-holder thread preemptions and leads to poor performance. This problem becomes very serious under high loads.To alleviate this problem, in this paper, we present ascheduling policy called Faithful Scheduling (FF), which dramatically reduces context-switches as well as lock-holder thread preemptions. We implemented FF on a 24-core Dell PowerEdgeR905 server running OpenSolaris.2009.06 and evaluated it using 22 programs including the TATP database application, SPECjbb2005, programs from PARSEC, SPEC OMP, and some microbenchmarks. The experimental results show that FF policy achieves high performance for both lightly and heavily loaded systems. Moreover it does not require any changes to the application source code or the OS kernel.

A Unified Scheduler for Recursive and Task Dataflow Parallelism

PACT Conference 11 Octubre de 2011, 17:00 Spanish Time, Galveston ISland TX,USA, Hotel Galvez, Music Hall.

Hans Vandierendonck

Task dataflow languages simplify the specification of parallel programs by dynamically detecting and enforcing dependencies between tasks. These languages are, however, often restricted to a single level of parallelism. This language design is reflected in the runtime system, where a master thread explicitly generates a task graph and worker threads execute ready tasks and wake-up their dependents. Such an approach is incompatible with state-of-the-art schedulers such as the Cilk scheduler, that minimize the creation of idle tasks (work-first principle) and place all task creation and scheduling off the critical path. This paper proposes an extension to the Cilk scheduler in order to reconcile task dependencies with the work-first principle. We discuss the impact of task dependencies on the properties of the Cilk scheduler. Furthermore, we propose a low-over head ticket-based technique for dependency tracking and enforcement at the object level. Our scheduler also supports renaming of objects in order to increase task-level parallelism. Renaming is implemented using versioned objects, a new type of hyperobject. Experimental evaluation shows that the unified scheduler is as efficient as the Cilk scheduler when tasks have no dependencies.Moreover, the unified scheduler is more efficient than SMPSS, a particular implementation of a task dataflow language.

Extreme Computing

PACT Conference
11 Octubre de 2011, 15:50 Spanish Time

Galveston ISland TX,USA, Hotel Galvez, Music Hall.

Stuart Feldmanm
Vice-President, Engineering, Google

Computing at the limits of technology calls for numerous engineering decisions and tradeoffs. General purpose solutions do not work at the extremes. Traditional HPC has been analyzed for decades, resulting in specialized architectures. Systems for life critical systems, those for large enterprises, those for tiny devices, also present their own special requirements. The area of data intensive computing is newer, and the computing models are less established. To support large (millions) of users doing similar but different computations, expecting to have access to enormous amounts of information (petabytes, not gigabytes) and to get prompt responses and global access calls for different compromises. Different applications present their own requirements and difficulties. This talk will address some of those needs - different models of storage and data management that are appropriate for different types of application, networking demands for parallelism and global access, management of large numbers of fallible processors and storage. Support for such computing also calls for different approaches to software methodology, system management, and deployment. But massive data also opens new ways to approach science and to get remarkable results the delight and surprise users.

Biography:

Stuart Feldman is responsible for the health and productivity of Google's engineering offices in the eastern part of the Americas, Asia, and Australia. He also has executive responsibility for a number of Google products. Before joining Google, he worked at IBM for eleven years. Most recently, he was Vice President for Computer Science in IBM Research, where he drove the long-term and exploratory worldwide science strategy in computer science and related fields, led programs for open collaborative research with universities, and influenced national and global computer science policy. Prior to that, Feldman served as Vice President for Internet Technology and was responsible for IBM strategies, standards, and policies relating to the future of the Internet, and managed a department that created experimental Internet-based applications. Earlier, he was the founding Director of IBM's Institute for Advanced Commerce, which was dedicated to creating intellectual leadership in e-commerce. Before joining IBM in mid-1995, he was a computer science researcher at Bell Labs and a research manager at Bellcore (now Telcordia). In addition he was the creator of Make as well as the architect for a large new line of software products at Bellcore. Feldman did his academic work in astrophysics and mathematics and earned his AB at Princeton and his PhD at MIT. He was awarded an honorary Doctor of Mathematics by the Univeristy of Waterloo in 2010. He is former President of ACM (Association for Computing Machinery) and member of the board of directors of the AACSB (Association to Advanced Collegiate Schools of Business). He received the 2003 ACM Software System Award. He is a Fellow of the IEEE, of the ACM, and of the AAAS and serves on a number of government advisory committees.

La Naturaleza en un chip: Inteligencia Computacional y Sistemas Bioinspirados

Dentro de los Cursos de Verano de el Escorial, se celebró el Curso de Verano titulado "La Naturaleza en un chip: Inteligencia Computacional y Sistemas Bioinspirados" y del que ofrecemos un resumen de las distintas charlas.

LUNES, DÍA 18 de Julio
10.30 horas: Inauguración Computación Evolutiva y sistemas Bioinspirados

Como presentación del curso esta primera charla introducirá al cursillista en el mundo de la Computación Evolutiva y sistemas bioinspirados, explicando los conceptos básicos y poniendo algunos ejemplos y aplicaciones ilustrativos.

12.00 horas: Conferencia Algoritmos de Estimación de Distribuciones y Neurociencia

Profesor Pedro Larrañaga Múgica

Catedrático de Universidad, Departamento de Inteligencia Artificial, Facultad de Informática, Universidad Politénica de Madrid.

En la charla se introducirán los algoritmos de estimación de distribuciones, una nueva manera de llevar a cabo la computación evolutiva. Dichos algoritmos tienen características comunes con los algoritmos genéticos, radicando su principal diferencia en el hecho de que los primeros no se basan en operaciones de cruce y mutación para evolucionar una población de individuos, cada uno de los cuales puede ser considerado como posible solución a un problema de optimización. En su lugar, los algoritmos de estimación de distribuciones aprenden una distribución de probabilidad conjunta de los individuos seleccionados en cada generación, para posteriormente, simulando de la misma, obtener la nueva población de individuos. Se mostrarán diferentes tipos de algoritmos de estimación de distribuciones en función de la complejidad del modelo probabilístico aprendido en cada generación, así como del dominio (discreto o continuo) de la función a optimizar. En la parte final de la charla se mostrarán tres aplicaciones de estos algoritmos en neurociencia: a) el estudio de la dependencia entre parámetros en modelos compartimentales; b) la optimización de estructuras cerebrales artificiales; y c) la clasificación supervisada de datos provenientes de magnetoencefalografías.

16.30 horas: Mesa redonda Aplicaciones en Medicina. Seguridad del paciente.

Pedro Larrañaga Múgica (UPM), José Ignacio Hidalgo (UCM), Jose Luis Risco-Martín (UCM), Juan Lanchares Dávila (UCM).

MARTES, DÍA 19 de Julio
10.00 horas: Conferencia De la investigación al negocio: impacto de la Inteligencia Computacional en Telefónica

Profesor: David Millán-Ruiz Especialista Tecnológico, Telefónica i+D.

A lo largo de los últimos años, se puede percibir una tendencia creciente orientada a resolver problemas cada vez más complejos donde el flujo de datos es altamente cambiante y el volumen datos es demasiado grande para muchas de las técnicas convencionales. Los algoritmos bioinspirados han demostrado ser suficientemente potentes como para poder resolver problemas de esta índole hasta el punto de que muchas empresas han apostado por usar dichas técnicas en entornos industriales reales, dando el salto de la teoría a la práctica. Empresas como Telefónica y, más extensivamente en otros casos, la sociedad se han beneficiado de este enorme potencial. En esta charla, se presentarán algunas de las aplicaciones de estos algoritmos dentro del grupo Telefónica, así como su impacto económico y social en algunos casos. Aunque la charla incluirá algunas nociones teóricas, se centrará en las aplicaciones en sí, dando un punto de vista de negocio.

12.00 horas: Conferencia Algunas Aplicaciones Reales de los Algoritmos Bioinspirados

Profesor: Oscar Cordón Investigador Principal,Unidad de Investigación “Aplicaciones de Lógica Fuzzy y Algoritmos Evolutivos”, Centro Europeo de Soft Computing.

Catedrático, Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Granada.

En esta charla presentaremos una serie de aplicaciones reales de los algoritmos evolutivos y los algoritmos de optimización basada en colonias de hormigas mono- y multi-objetivo desarrolladas en el European Centre for Soft Computing, un centro internacional de investigación y desarrollo existente desde principios de 2006 en Mieres, Asturias.

En primer lugar se introducirán los conceptos básicos de los dos tipos de algoritmos bio-inspirados comentados, así como los de la lógica fuzzy, otra de las técnicas del área de soft computing empleada para resolver los problemas considerados mediante un enfoque híbrido. Posteriormente, se repasarán los conceptos básicos de la optimización multi-objetivo puesto que varias de las aplicaciones tratadas responden a esta naturaleza, como suele ocurrir en los problemas reales. Finalmente, se describirán en detalles los problemas concretos, los mecanismos de resolución considerados y los resultados obtenidos:

■Uso de algoritmos evolutivos y sistemas basados en reglas fuzzy para el control automático de sistemas de ventilación en grandes edificios.
■Uso de algoritmos de minería de grafos y de algoritmos evolutivos multi-objetivo para la el análisis y comparación de mapas visuales de la ciencia.
■Uso de algoritmos multi-objetivo de optimización basada en colonias de hormigas para el equilibrado de líneas de montaje en Nissan.
■Uso de algoritmos evolutivos y conjuntos fuzzy para el apoyo a la identificación forense de personas desaparecidas.
16.30 horas: Mesa redonda: Nuevas formas de computación evolutiva ¿Estamos reinventando la rueda? Abraham Duarte Muñoz

MIÉRCOLES, DÍA 20 de Julio
10.00 horas: Conferencia Aplicaciones de la Inteligencia Computacional para la Generación de Contenidos en Videojuegos

Profesor: Francisco Fernández de Vega

Profesor Titular de Universidad, Director Grupo de Evolución Artificial, Dpto. Tecnología de los Computadores y de las Comunicaciones, Universidad de Extremadura.

La Inteligencia Computacional ha conseguido un éxito notable en los últimos años. Surgida al amparo de la Inteligencia Artificial, en las últimas décadas ha madurado y diversificado sus potencialidades: el número de técnicas incluidas en el término a crecido de manera importante, y los problemas reales que ha enfrentado son de lo más variopinto: Visión por Computador, Diseño electrónico, planificación de trabajos, modelado de sistemas, procesamiento del lenguaje, diseño de interfaces hombre-máquina, vida artificial, etc. Uno de los campos que con más fuerza está incorporando nuevas técnicas de Inteligencia Computacional se enmarca en la industria del ocio: generación de contenidos para videojuegos. En esta charla se realizará un recorrido de las aplicaciones de la IC en la industria del videojuego, las líneas de investigación actual y algunos resultados de interés. En particular se mostrará la aplicación de la Programación Genética (PG) y algunos resultados obtenidos y utilizados en videojuegos 3D. Se mostrará la utilizad de la PG en general, y su aplicación particular para el diseño gráfico.

16.30 horas: Mesa redonda Hardware Evolutivo. ¿Futuro o utopía?

Juan Lanchares Dávila (UCM), Francisco Fernández de Vega (UEx), David Millán (Telefónica i+D), José Ignacio Hidalgo (UCM), José Luis Risco-Martín (UCM).

JUEVES, DÍA 21 de Julio
10.00 horas: Conferencia Algoritmos Meméticos: Presente y Futuro

Prof. Carlos Cotta

Profesor Titular de Universidad, Departamento Lenguajes y Ciencias de la Computación, ETSI Informática, Universidad de Málaga.

Durante las dos últimas décadas hemos podido ser testigos del asentamiento de los algoritmos meméticos (AMs) como una de las técnicas más populares para la resolución de problemas complejos de optimización. El pragmatismo inherente de estas técnicas ha facilitado el desarrollo de modelos híbridos basados en la búsqueda de sinergias entre diferentes técnicas y a la explotación de todo tipo de conocimiento dependiente del problema, dado lugar a enfoques algorítmicos de gran riqueza y sofisticación. De este modo, los modelos iniciales apenas basados en el uso conjunto de algoritmos evolutivos y técnicas de búsqueda local han ido dando paso a modelos y arquitecturas que aunque predichas hace tiempo eran impensables hasta hace bien poco. Así, hoy se dispone de AMs que incorporan mecanismos de auto-adaptación y auto-generación de estrategias de búsqueda y que son capaces de interactuar con técnicas completas o con expertos humanos. A lo largo de charla se hará un breve recorrido histórico de estas técnicas, se abordarán estas extensiones así como algunas de las características que pueden aguardar a los AMs en el futuro.

12.00 horas: Conferencia Algoritmos Evolutivos Paralelos

Prof. Marco Tomassini

Profesor Titular, Department of Information Systems, Université de Lausanne (Suiza)

Los algoritmos evolutivos, por su naturaleza propia, consumen una buena cantidad de recursos computacionales. Afortunadamente, la estructura de estas heurísticas permite el desarrollo de versiones paralelas de las mismas mediante el uso de modificaciones del algoritmo, sobre todo con respecto a su estructura de población. Estas versiones pueden incluso llegar a proporcionar un mejor rendimiento aunque estén implementadas a través de técnicas de computo secuencial estándar. A estas consideraciones hay que sumar los avances tecnológicos de la última década, mejoras que contribuyen de manera determinante a acelerar el computo gracias a la posibilidad de llevar a cabo operaciones con alto grado de paralelismo físico.

16.30 horas: Mesa redonda Algoritmos Evolutivos e Inversión en bolsa

Dra. Laura Nuñez Letamendía (IE Business School, Head of Research Office, Assistant Professor of Finance). Carlos Cotta (UMA), Marco Tomassini (UNIL), José Ignacio Hidalgo (UCM).

VIERNES, DÍA 22 de Julio
10.00 horas: Conferencia Aplicando Inteligencia Computacional en la PYME española

Dra. Anna Esparcia

Directora de I+D+i, S2 Grupo, http://www.s2grupo.es/,

Profesora asociada, Dpto. Ingeniería de Sistemas y Automática, E.T.S. de Ingenieria del Diseño, Universidad Politécnica de Valencia

En esta ponencia se discutirá el interés de la utilización de las técnicas de Inteligencia Computacional (IC) en el entorno empresarial español, en particular de la PYME española. Además se presentarán varias aplicaciones de la IC a problemas reales en la industria, desde ubicar productos en supermercados, hasta el control ecológico de plagas, pasando por el software que se repara a sí mismo.

12.00 horas: Clausura y entrega de diplomas