A parallel programming model for ada

Over the last three decades, computer architects have been able to achieve an increase in performance for single processors by, e.g., increasing clock speed, introducing cache memories and using instruction level parallelism. However, because of power consumption and heat dissipation constraints, this trend is going to cease. In recent times, hardware engineers have instead moved to new chip architectures with multiple processor cores on a single chip. With multi-core processors, applications can complete more total work than with one core alone. To take advantage of multi-core processors, parallel programming models are proposed as promising solutions for more effectively using multi-core processors. This paper discusses some of the existent models and frameworks for parallel programming, leading to outline a draft parallel programming model for Ada.

P-SOCRATES: A parallel software framework for time-critical many-core systems

Article in Press, Corrected Proof

Multicore Scheduling of Real-Time Irregular Parallel Algorithms in Linux

Face �� estagna����o da tecnologia uniprocessador registada na passada d��cada, aos principais fabricantes de microprocessadores encontraram na tecnologia multi-core a resposta `as crescentes necessidades de processamento do mercado. Durante anos, os desenvolvedores de software viram as suas aplica����es acompanhar os ganhos de performance conferidos por cada nova gera����o de processadores sequenciais, mas `a medida que a capacidade de processamento escala em fun����o do n��mero de processadores, a computa����o sequencial tem de ser decomposta em v��rias partes concorrentes que possam executar em paralelo, para que possam utilizar as unidades de processamento adicionais e completar mais rapidamente. A programa����o paralela implica um paradigma completamente distinto da programa����o sequencial. Ao contr��rio dos computadores sequenciais tipificados no modelo de Von Neumann, a heterogeneidade de arquiteturas paralelas requer modelos de programa����o paralela que abstraiam os programadores dos detalhes da arquitectura e simplifiquem o desenvolvimento de aplica����es concorrentes. Os modelos de programa����o paralela mais populares incitam os programadores a identificar instru����es concorrentes na sua l��gica de programa����o, e a especific��-las sob a forma de tarefas que possam ser atribu��das a processadores distintos para executarem em simult��neo. Estas tarefas s��o tipicamente lan��adas durante a execu����o, e atribu��das aos processadores pelo motor de execu����o subjacente. Como os requisitos de processamento costumam ser vari��veis, e n��o s��o conhecidos a priori, o mapeamento de tarefas para processadores tem de ser determinado dinamicamente, em resposta a altera����es imprevis��veis dos requisitos de execu����o. `A medida que o volume da computa����o cresce, torna-se cada vez menos vi��vel garantir as suas restri����es temporais em plataformas uniprocessador. Enquanto os sistemas de tempo real se come��am a adaptar ao paradigma de computa����o paralela, h�� uma crescente aposta em integrar execu����es de tempo real com aplica����es interativas no mesmo hardware, num mundo em que a tecnologia se torna cada vez mais pequena, leve, ub��qua, e port��vel. Esta integra����o requer solu����es de escalonamento que simultaneamente garantam os requisitos temporais das tarefas de tempo real e mantenham um n��vel aceit��vel de QoS para as restantes execu����es. Para tal, torna-se imperativo que as aplica����es de tempo real paralelizem, de forma a minimizar os seus tempos de resposta e maximizar a utiliza����o dos recursos de processamento. Isto introduz uma nova dimens��o ao problema do escalonamento, que tem de responder de forma correcta a novos requisitos de execu����o imprevis��veis e rapidamente conjeturar o mapeamento de tarefas que melhor beneficie os crit��rios de performance do sistema. A t��cnica de escalonamento baseado em servidores permite reservar uma fra����o da capacidade de processamento para a execu����o de tarefas de tempo real, e assegurar que os efeitos de lat��ncia na sua execu����o n��o afectam as reservas estipuladas para outras execu����es. No caso de tarefas escalonadas pelo tempo de execu����o m��ximo, ou tarefas com tempos de execu����o vari��veis, torna-se prov��vel que a largura de banda estipulada n��o seja consumida por completo. Para melhorar a utiliza����o do sistema, os algoritmos de partilha de largura de banda (capacity-sharing) doam a capacidade n��o utilizada para a execu����o de outras tarefas, mantendo as garantias de isolamento entre servidores. Com efici��ncia comprovada em termos de espa��o, tempo, e comunica����o, o mecanismo de work-stealing tem vindo a ganhar popularidade como metodologia para o escalonamento de tarefas com paralelismo din��mico e irregular. O algoritmo p-CSWS combina escalonamento baseado em servidores com capacity-sharing e work-stealing para cobrir as necessidades de escalonamento dos sistemas abertos de tempo real. Enquanto o escalonamento em servidores permite partilhar os recursos de processamento sem interfer��ncias a n��vel dos atrasos, uma nova pol��tica de work-stealing que opera sobre o mecanismo de capacity-sharing aplica uma explora����o de paralelismo que melhora os tempos de resposta das aplica����es e melhora a utiliza����o do sistema. Esta tese prop��e uma implementa����o do algoritmo p-CSWS para o Linux. Em concord��ncia com a estrutura modular do escalonador do Linux, ��e definida uma nova classe de escalonamento que visa avaliar a aplicabilidade da heur��stica p-CSWS em circunst��ncias reais. Ultrapassados os obst��culos intr��nsecos `a programa����o da kernel do Linux, os extensos testes experimentais provam que o p-CSWS ��e mais do que um conceito te��rico atrativo, e que a explora����o heur��stica de paralelismo proposta pelo algoritmo beneficia os tempos de resposta das aplica����es de tempo real, bem como a performance e efici��ncia da plataforma multiprocessador.

Server-based scheduling of parallel real-time tasks

Multicore platforms have transformed parallelism into a main concern. Parallel programming models are being put forward to provide a better approach for application programmers to expose the opportunities for parallelism by pointing out potentially parallel regions within tasks, leaving the actual and dynamic scheduling of these regions onto processors to be performed at runtime, exploiting the maximum amount of parallelism. It is in this context that this paper proposes a scheduling approach that combines the constant-bandwidth server abstraction with a priority-aware work-stealing load balancing scheme which, while ensuring isolation among tasks, enables parallel tasks to be executed on more than one processor at a given time instant.

Suporte �� computa����o paralela e distribu��da em Java: distribui����o e execu����o de trabalho

Nos ��ltimos anos come��aram a ser vulgares os computadores dotados de multiprocessadores e multi-cores. De modo a aproveitar eficientemente as novas caracter��sticas desse hardware come��aram a surgir ferramentas para facilitar o desenvolvimento de software paralelo, atrav��s de linguagens e frameworks, adaptadas a diferentes linguagens. Com a grande difus��o de redes de alta velocidade, tal como Gigabit Ethernet e a ��ltima gera����o de redes Wi-Fi, abre-se a oportunidade de, al��m de paralelizar o processamento entre processadores e cores, poder em simult��neo paraleliz��-lo entre m��quinas diferentes. Ao modelo que permite paralelizar processamento localmente e em simult��neo distribu��-lo para m��quinas que tamb��m t��m capacidade de o paralelizar, chamou-se ���modelo paralelo distribu��do���. Nesta disserta����o foram analisadas t��cnicas e ferramentas utilizadas para fazer programa����o paralela e o trabalho que est�� feito dentro da ��rea de programa����o paralela e distribu��da. Tendo estes dois factores em considera����o foi proposta uma framework que tenta aplicar a simplicidade da programa����o paralela ao conceito paralelo distribu��do. A proposta baseia-se na disponibiliza����o de uma framework em Java com uma interface de programa����o simples, de f��cil aprendizagem e legibilidade que, de forma transparente, �� capaz de paralelizar e distribuir o processamento. Apesar de simples, existiu um esfor��o para a tornar configur��vel de forma a adaptar-se ao m��ximo de situa����es poss��vel. Nesta disserta����o ser��o exploradas especialmente as quest��es relativas �� execu����o e distribui����o de trabalho, e a forma como o c��digo �� enviado de forma autom��tica pela rede, para outros n��s cooperantes, evitando assim a instala����o manual das aplica����es em todos os n��s da rede. Para confirmar a validade deste conceito e das ideias defendidas nesta disserta����o foi implementada esta framework �� qual se chamou DPF4j (Distributed Parallel Framework for JAVA) e foram feitos testes e retiradas m��tricas para verificar a exist��ncia de ganhos de performance em rela����o ��s solu����es j�� existentes.

Real-Time Support in the Proposal for Fine-Grained Parallelism in Ada

Presented at Work in Progress Session, IEEE Real-Time Systems Symposium (RTSS 2015). 1 to 3, Dec, 2015. San Antonio, U.S.A..

Ensemble: an innovative approach to practice computer programming

Currently, the teaching-learning process in domains, such as computer programming, is characterized by an extensive curricula and a high enrolment of students. This poses a great workload for faculty and teaching assistants responsible for the creation, delivery, and assessment of student exercises. The main goal of this chapter is to foster practice-based learning in complex domains. This objective is attained with an e-learning framework���called Ensemble���as a conceptual tool to organize and facilitate technical interoperability among services. The Ensemble framework is used on a specific domain: computer programming. Content issues are tacked with a standard format to describe programming exercises as learning objects. Communication is achieved with the extension of existing specifications for the interoperation with several systems typically found in an e-learning environment. In order to evaluate the acceptability of the proposed solution, an Ensemble instance was validated on a classroom experiment with encouraging results.

Design a computer programming learning environment for Massive Open Online Courses

Teaching and learning computer programming is as challenging as difficult. Assessing the work of students and providing individualised feedback to all is time-consuming and error prone for teachers and frequently involves a time delay. The existent tools and specifications prove to be insufficient in complex evaluation domains where there is a greater need to practice. At the same time Massive Open Online Courses (MOOC) are appearing revealing a new way of learning, more dynamic and more accessible. However this new paradigm raises serious questions regarding the monitoring of student progress and its timely feedback. This paper provides a conceptual design model for a computer programming learning environment. This environment uses the portal interface design model gathering information from a network of services such as repositories and program evaluators. The design model includes also the integration with learning management systems, a central piece in the MOOC realm, endowing the model with characteristics such as scalability, collaboration and interoperability. This model is not limited to the domain of computer programming and can be adapted to any complex area that requires systematic evaluation with immediate feedback.

BabeLO : an extensible converter of programming exercises formats

In the last two decades, there was a proliferation of programming exercise formats that hinders interoperability in automatic assessment. In the lack of a widely accepted standard, a pragmatic solution is to convert content among the existing formats. BabeLO is a programming exercise converter providing services to a network of heterogeneous e-learning systems such as contest management systems, programming exercise authoring tools, evaluation engines and repositories of learning objects. Its main feature is the use of a pivotal format to achieve greater extensibility. This approach simplifies the extension to other formats, just requiring the conversion to and from the pivotal format. This paper starts with an analysis of programming exercise formats representative of the existing diversity. This analysis sets the context for the proposed approach to exercise conversion and to the description of the pivotal data format. The abstract service definition is the basis for the design of BabeLO, its components and web service interface. This paper includes a report on the use of BabeLO in two concrete scenarios: to relocate exercises to a different repository, and to use an evaluation engine in a network of heterogeneous systems.

A distributed system for learning programming on-line

Several Web-based on-line judges or on-line programming trainers have been developed in order to allow students to train their programming skills. However, their pedagogical functionalities in the learning of programming have not been clearly de���ned. EduJudge is a project which aims to integrate the ���UVA On-line Judge���, an existing on-line programming trainer with an important number of problems and users, into an effective educational environment consisting of the e-learning platform Moodle and the competitive learning tool QUESTOURnament. The result is the EduJudge system which allows teachers to apply different pedagogical approaches using a proven e-learning platform, makes problems easy to search through an effective search engine, and provides an automated evaluation of the solutions submitted to these problems. The ���nal objective is to provide new learning strategies to motivate students and present programming as an easy and attractive challenge. EduJudge has been tried and tested in three algorithms and programming courses in three different Engineering degrees. The students��� motivation and satisfaction levels were analysed alongside the effects of the EduJudge system on students��� academic outcomes. Results indicate that both students and teachers found that among other multiple bene���ts the EduJudge system facilitates the learning process. Furthermore, the experi- ment also showed an improvement in students��� academic outcomes. It must be noted that the students��� level of satisfaction did not depend on their computer skills or their gender.

Orchestration of e-learning services for automatic evaluation of programming exercises

Managing programming exercises require several heterogeneous systems such as evaluation engines, learning objects repositories and exercise resolution environments. The coordination of networks of such disparate systems is rather complex. These tools would be too specific to incorporate in an e-Learning platform. Even if they could be provided as pluggable components, the burden of maintaining them would be prohibitive to institutions with few courses in those domains. This work presents a standard based approach for the coordination of a network of e-Learning systems participating on the automatic evaluation of programming exercises. The proposed approach uses a pivot component to orchestrate the interaction among all the systems using communication standards. This approach was validated through its effective use on classroom and we present some preliminary results.

Programming atomic multicasts in CAN

In Distributed Computer-Controlled Systems (DCCS), a special emphasis must be given to the communication infrastructure, which must provide timely and reliable communication services. CAN networks are usually suitable to support small-scale DCCS. However, they are known to present some reliability problems, which can lead to an unreliable behaviour of the supported applications. In this paper, an atomic multicast protocol for CAN networks is proposed. This protocol explores the CAN synchronous properties, providing a timely and reliable service to the supported applications. The implementation of such protocol in Ada, on top of the Ada version of Real-Time Linux is presented, which is used to demonstrate the advantages and disadvantages of the platform to support reliable communications in DCCS.

A framework for the development of parallel and distributed real-time embedded systems

Embedded real-time applications increasingly present high computation requirements, which need to be completed within specific deadlines, but that present highly variable patterns, depending on the set of data available in a determined instant. The current trend to provide parallel processing in the embedded domain allows providing higher processing power; however, it does not address the variability in the processing pattern. Dimensioning each device for its worst-case scenario implies lower average utilization, and increased available, but unusable, processing in the overall system. A solution for this problem is to extend the parallel execution of the applications, allowing networked nodes to distribute the workload, on peak situations, to neighbour nodes. In this context, this report proposes a framework to develop parallel and distributed real-time embedded applications, transparently using OpenMP and Message Passing Interface (MPI), within a programming model based on OpenMP. The technical report also devises an integrated timing model, which enables the structured reasoning on the timing behaviour of these hybrid architectures.

Direct search optimization application programming interface with remote access

Search Optimization methods are needed to solve optimization problems where the objective function and/or constraints functions might be non differentiable, non convex or might not be possible to determine its analytical expressions either due to its complexity or its cost (monetary, computational, time,...). Many optimization problems in engineering and other fields have these characteristics, because functions values can result from experimental or simulation processes, can be modelled by functions with complex expressions or by noise functions and it is impossible or very difficult to calculate their derivatives. Direct Search Optimization methods only use function values and do not need any derivatives or approximations of them. In this work we present a Java API that including several methods and algorithms, that do not use derivatives, to solve constrained and unconstrained optimization problems. Traditional API access, by installing it on the developer and/or user computer, and remote API access to it, using Web Services, are also presented. Remote access to the API has the advantage of always allow the access to the latest version of the API. For users that simply want to have a tool to solve Nonlinear Optimization Problems and do not want to integrate these methods in applications, also two applications were developed. One is a standalone Java application and the other a Web-based application, both using the developed API.