Algorithm-oriented design of efficient many-core architectures applied to dense matrix multiplication

Recent integrated circuit technologies have opened the possibility to design parallel architectures with hundreds of cores on a single chip. The design space of these parallel architectures is huge with many architectural options. Exploring the design space gets even more difficult if, beyond performance and area, we also consider extra metrics like performance and area efficiency, where the designer tries to design the architecture with the best performance per chip area and the best sustainable performance. In this paper we present an algorithm-oriented approach to design a many-core architecture. Instead of doing the design space exploration of the many core architecture based on the experimental execution results of a particular benchmark of algorithms, our approach is to make a formal analysis of the algorithms considering the main architectural aspects and to determine how each particular architectural aspect is related to the performance of the architecture when running an algorithm or set of algorithms. The architectural aspects considered include the number of cores, the local memory available in each core, the communication bandwidth between the many-core architecture and the external memory and the memory hierarchy. To exemplify the approach we did a theoretical analysis of a dense matrix multiplication algorithm and determined an equation that relates the number of execution cycles with the architectural parameters. Based on this equation a many-core architecture has been designed. The results obtained indicate that a 100 mm(2) integrated circuit design of the proposed architecture, using a 65 nm technology, is able to achieve 464 GFLOPs (double precision floating-point) for a memory bandwidth of 16 GB/s. This corresponds to a performance efficiency of 71 %. Considering a 45 nm technology, a 100 mm(2) chip attains 833 GFLOPs which corresponds to 84 % of peak performance These figures are better than those obtained by previous many-core architectures, except for the area efficiency which is limited by the lower memory bandwidth considered. The results achieved are also better than those of previous state-of-the-art many-cores architectures designed specifically to achieve high performance for matrix multiplication.

Parallelization of SAT on Reconfigurable Hardware

Quoique très difficile à résoudre, le problème de satisfiabilité Booléenne (SAT) est fréquemment utilisé lors de la modélisation d’applications industrielles. À cet effet, les deux dernières décennies ont vu une progression fulgurante des outils conçus pour trouver des solutions à ce problème NP-complet. Deux grandes avenues générales ont été explorées afin de produire ces outils, notamment l’approche logicielle et matérielle. Afin de raffiner et améliorer ces solveurs, de nombreuses techniques et heuristiques ont été proposées par la communauté de recherche. Le but final de ces outils a été de résoudre des problèmes de taille industrielle, ce qui a été plus ou moins accompli par les solveurs de nature logicielle. Initialement, le but de l’utilisation du matériel reconfigurable a été de produire des solveurs pouvant trouver des solutions plus rapidement que leurs homologues logiciels. Cependant, le niveau de sophistication de ces derniers a augmenté de telle manière qu’ils restent le meilleur choix pour résoudre SAT. Toutefois, les solveurs modernes logiciels n’arrivent toujours pas a trouver des solutions de manière efficace à certaines instances SAT. Le but principal de ce mémoire est d’explorer la résolution du problème SAT dans le contexte du matériel reconfigurable en vue de caractériser les ingrédients nécessaires d’un solveur SAT efficace qui puise sa puissance de calcul dans le parallélisme conféré par une plateforme FPGA. Le prototype parallèle implémenté dans ce travail est capable de se mesurer, en termes de vitesse d’exécution à d’autres solveurs (matériels et logiciels), et ce sans utiliser aucune heuristique. Nous montrons donc que notre approche matérielle présente une option prometteuse vers la résolution d’instances industrielles larges qui sont difficilement abordées par une approche logicielle.

Safe Distributed Coordination of Heterogeneous Robots through Dynamic Simple Temporal Networks

Research on autonomous intelligent systems has focused on how robots can robustly carry out missions in uncertain and harsh environments with very little or no human intervention. Robotic execution languages such as RAPs, ESL, and TDL improve robustness by managing functionally redundant procedures for achieving goals. The model-based programming approach extends this by guaranteeing correctness of execution through pre-planning of non-deterministic timed threads of activities. Executing model-based programs effectively on distributed autonomous platforms requires distributing this pre-planning process. This thesis presents a distributed planner for modelbased programs whose planning and execution is distributed among agents with widely varying levels of processor power and memory resources. We make two key contributions. First, we reformulate a model-based program, which describes cooperative activities, into a hierarchical dynamic simple temporal network. This enables efficient distributed coordination of robots and supports deployment on heterogeneous robots. Second, we introduce a distributed temporal planner, called DTP, which solves hierarchical dynamic simple temporal networks with the assistance of the distributed Bellman-Ford shortest path algorithm. The implementation of DTP has been demonstrated successfully on a wide range of randomly generated examples and on a pursuer-evader challenge problem in simulation.

Mid-term evaluation of African Technology Policy Studies Network Phase VI Strategic Plan: for the period January 1, 2009 to December 31, 2010

The African Technology Policy Studies Network (ATPS) is a multidisciplinary network of researchers, private sector actors, policymakers and civil society. ATPS has the vision to become the leading international centre of excellence and reference in science, technology and innovation (STI) systems research, training and capacity building, communication and sensitization, knowledge brokerage, policy advocacy and outreach in Africa. It has a Regional Secretariat in Nairobi Kenya, and operates through national chapters in 29 countries (including 27 in Africa and two Chapters in the United Kingdom and USA for Africans in the Diaspora) with an expansion plan to cover the entire continent by 2015. The ATPS Phase VI Strategic Plan aims to improve the understanding and functioning of STI processes and systems to strengthen the learning capacity, social responses, and governance of STI for addressing Africa's development challenges, with a specific focus on the Millennium Development Goals (MDGs). A team of external evaluators carried out a midterm review to assess the effectiveness and efficiency of the implementation of the Strategic Plan for the period January 1, 2009 to December 31, 2010. The evaluation methodology involved multiple quantitative and qualitative methods to assess the qualitative and quantitative inputs (human resources, financial resources, time, etc.) into ATPS activities (both thematic and facilitative) and their tangible and intangible outputs, outcomes and impacts. Methods included a questionnaire survey of ATPS members and stakeholders, key informant interviews, and focus group discussions (FGDs) with members in six countries. Effectiveness of Programmes Under all six strategic goals, very good progress has been made towards planned outputs and outcomes. This is evidenced by key performance indicators (KPIs) generated from desk review, ratings from the survey respondents, and the themes that run through the FGDs. Institutional and Programme Cost Effectiveness Institutional Effectiveness: assessment of institutional effectiveness suggests that adequate management frameworks are in place and are being used effectively and transparently. Also technical and financial accounting mechanisms are being followed in accordance with grant agreements and with global good practice. This is evidenced by KPIs generated from desk review. Programme Cost Effectiveness: assessment of cost-effectiveness of execution of programmes shows that organisational structure is efficient, delivering high quality, relevant research at relatively low cost by international standards. The evidence includes KPIs from desk review: administrative costs to programme cost ratio has fallen steadily, to around 10%; average size of research grants is modest, without compromising quality. There is high level of pro bono input by ATPS members. ATPS Programmes Strategic Evaluation ATPS research and STI related activities are indeed unique and well aligned with STI issues and needs facing Africa and globally. The multi-disciplinary and trans-boundary nature of the research activities are creating a unique group of research scientists. The ATPS approach to research and STI issues is paving the way for the so called Third Generation University (3GU). Understanding this unique positioning, an increasing number of international multilateral agencies are seeking partnership with ATPS. ATPS is seeing an increasing level of funding commitments by Donor Partners. Recommendations for ATPS Continued Growth and Effectiveness On-going reform of ATPS administrative structure to continue The on-going reforms that have taken place within the Board, Regional Secretariat, and at the National Chapter coordination levels are welcomed. Such reform should continue until fully functional corporate governance policy and practices are fully established and implemented across the ATPS governance structures. This will further strengthen ATPS to achieve the vision of being the leading STI policy brokerage organization in Africa. Although training in corporate governance has been carried out for all sectors of ATPS leadership structure in recent time, there is some evidence that these systems have not yet been fully implemented effectively within all the governance structures of the organization, especially at the Board and National chapter levels. Future training should emphasize practical application with exercises relevant to ATPS leadership structure from the Board to the National Chapter levels. Training on Transformational Leadership - Leading a Change Though a subject of intense debate amongst economists and social scientists, it is generally agreed that cultural mindsets and attitudes could enhance and/or hinder organizational progress. ATPS’s vision demands transformational leadership skills amongst its leaders from the Board members to the National Chapter Coordinators. To lead such a change, ATPS leaders must understand and avoid personal and cultural mindsets and value systems that hinder change, while embracing those that enhance it. It requires deliberate assessment of cultural, behavioural patterns that could hinder progress and the willingness to be recast into cultural and personal habits that make for progress. Improvement of relationship amongst the Board, Secretariat, and National Chapters A large number of ATPS members and stakeholders feel they do not have effective communications and/or access to Board, National Chapter Coordinators and Regional Secretariat activities. Effort should be made to improve the implementation of ATPS communication strategy to improve on information flows amongst the ATPS management and the members. The results of the survey and the FGDs suggest that progress has been made during the past two years in this direction, but more could be done to ensure effective flow of pertinent information to members following ATPS communications channels. Strategies for Increased Funding for National Chapters There is a big gap between the fundraising skills of the Regional Secretariat and those of the National Coordinators. In some cases, funds successfully raised by the Secretariat and disbursed to national chapters were not followed up with timely progress and financial reports by some national chapters. Adequate training in relevant skills required for effective interactions with STI key policy players should be conducted regularly for National Chapter coordinators and ATPS members. The ongoing training in grant writing should continue and be made continent-wide if funding permits. Funding of National Chapters should be strategic such that capacity in a specific area of research is built which, with time, will not only lead to a strong research capacity in that area, but also strengthen academic programmes. For example, a strong climate change programme is emerging at University of Nigeria Nsukka (UNN), with strong collaborations with Universities from neighbouring States. Strategies to Increase National Government buy-in and support for STI Translating STI research outcomes into policies requires a great deal of emotional intelligence, skills which are often lacking in the first and second generation universities. In the epoch of the science-based or 2GUs, governments were content with universities carrying out scientific research and providing scientific education. Now they desire to see universities as incubators of new science- or technology-based commercial activities, whether by existing firms or start-ups. Hence, governments demand that universities take an active and leading role in the exploitation of their knowledge and they are willing to make funds available to support such activities. Thus, for universities to gain the attention of national leadership they must become centres of excellence and explicit instruments of economic development in the knowledge-based economy. The universities must do this while working collaboratively with government departments, parastatals, and institutions and dedicated research establishments. ATPS should anticipate these shifting changes and devise programmes to assist both government and universities to relate effectively. New administrative structures in member organizations to sustain and manage the emerging STI multidisciplinary teams Second Generation universities (2GUs) tend to focus on pure science and often do not regard the application of their know-how as their task. In contrast, Third Generation Universities (3GUs) objectively stimulate techno-starters – students or academics – to pursue the exploitation or commercialisation of the knowledge they generate. They view this as being equal in importance to the objectives of scientific research and education. Administratively, research in the 2GU era was mainly monodisciplinary and departments were structured along disciplines. The emerging interdisciplinary scientific teams with focus on specific research areas functionally work against the current mono-disciplinary faculty-based, administrative structure of 2GUs. For interdisciplinary teams, the current faculty system is an obstacle. There is a need for new organisational forms for university management that can create responsibilities for the task of know-how exploitation. ATPS must anticipate this and begin to strategize solutions for their member institutions to transition to 3Gus administrative structure, otherwise ATPS growth will plateau, and progress achieved so far may be stunted.

Scheduling of a parallel computation-bound application and sequential applications executing concurrently on a cluster - a case study

Studies have shown that most of the computers in a non-dedicated cluster are often idle or lightly loaded. The underutilized computers in a non-dedicated cluster can be employed to execute parallel applications. The aim of this study is to learn how concurrent execution of a computation-bound and sequential applications influence their execution performance and cluster utilization. The result of the study has demonstrated that a computation-bound parallel application benefits from load balancing, and at the same time sequential applications suffer only an insignificant slowdown of execution. Overall, the utilization of a non-dedicated cluster is improved.

The application of the psychological contract to workplace safety

Introduction: Psychological contracts of safety are conceptualized as the beliefs of individuals about reciprocal safety obligations inferred from implicit or explicit promises. Although the literature on psychological contracts is growing, the existence of psychological contracts in relation to safety has not been established. The research sought to identify psychological contracts in the conversations of employees about safety, by demonstrating reciprocity in relation to employer and employee safety obligations. The identified safety obligations were used to develop a measure of psychological contracts of safety. Method: The participants were 131 employees attending safety training sessions in retail and manufacturing organizations. Non-participant observation was used to collect the data during safety training sessions. Content analysis was used to analyze the data. Categories for coding were established through identification of language markers that demonstrated contingencies or other implied obligations. Results: Direct evidence of reciprocity between employer safety obligations and employee safety obligations was found in statements from the participants demonstrating psychological contracts. A comprehensive list of perceived employer and employee safety obligations was compiled and developed into a measure of psychological contracts of safety. A small sample of 33 safety personnel was used to validate the safety obligations. Conclusions and impact on industry: Implications of these findings for safety and psychological contract research are discussed.

Carl Maria von Weber’s Overture to Oberon: A History of Recorded Performance

My research examines the recorded performance history of the Overture to Weber’s Oberon in light of these aesthetic goals. I have charted changes in performance practice trends, including in timing, tempo fluctuation, rhythmic accuracy and ensemble, and the use of portamento. The twenty recordings studied that I surveyed span nearly seventy-five years, and include many of the 20th century’s most prominent conductors and orchestras, including groups from Communist Russia, both pre-World War II and post-World War II continental Europe, the British Isles, and the United States.8 Though by no means comprehensive, my selections encompass a diverse sampling of surviving recordings, ensuring a large enough sample size to reflect general trends in the performance of Weber’s masterpiece. My research and analysis confirms the conventional view of a move toward more accurate—but also more cautious, uniform, and inexpressive— performances. Surprisingly, however, this analysis also suggests that we are on the cusp of a new era in orchestra performance practice, one that shares many of the values of the earlier recorded performances. While maintaining today’s high standards of execution, modern performances now look to regain many of the past’s expressive qualities, doing so in sometimes surprising ways.

Ideal golf swing : an evaluation of its characteristics and the assumptions underlying its acquisition during coaching

The game of golf requires hitting a ball from a range of lies over a range of distances in environments that include many obstacles to be avoided. Each of these different golf shots arc designed to move the ball from the tee to the hole in the least number of strokes. However, the fundamental assumption that seems to underlie the coaching of golf, particularly to novice players, is that acquisition of an ideal basic golf swing is the most important outcome of coaching. Implicit in this view are three further assumptions. The first is that once this ideal basic golf swing is acquired by players, they are able to complete a game of golf in a competent manner even though this requires a range of different shots. The second is that there is a close correspondence between the quality of execution of any golf swing as judged in terms of this ideal swing, and the quality of outcome of the golf shot of which the swing is a part, as judged by where the ball comes to rest. The third assumption is that visual inspection of the golf swing by a coach can reveal inadequacies which can be remedied leading lo improved performance in the game of golf. The research reported in this thesis is an investigation of these assumptions. The rationale underlying coaching of golf was examined by reviewing the golf coaching literature (Chapter 1) and conducting a survey of professional golf coaches (Chapter 2). Results of the literature review and the survey indicated that the major emphasis of golf coaching of novices was on their acquiring what might be described as an ideal basic golf swing. This typically involved identifying components in sequence. Little emphasis was placed during this stage of coaching on what might be described as the complete action of a golf shot which involves hitting a ball to some target location. To examine the assumption that there was a close correspondence between the quality of execution of the golf swing and the quality of the outcome of a golf shot, two studies were conducted. In Chapter 3 the development of a 70-item checklist to be used to evaluate the quality of execution of a golf swing is reported. This checklist was based on a detailed behavioural analysis of the golf swing involving collaboration with relevant experts (i.e., golf coaches, biomechanist, kinesiologist), and information derived from a review of golf coaching materials. Development of the checklist was an iterative process in which earlier versions were used to evaluate sample golf swings, and problems identified during this lest process were used to improve the checklist. The final 70-item checklist comprised of a static component with three parts (left-hand grip; right-hand grip; stance) and a dynamic component with six parts (half backswing; full backswing; half downswing; ball contact; half followthrough; finish position). This version of the checklist was used in a study (reported in Chapter 4) of the relationship between the judged quality of execution of a golf swing and the outcome accuracy of a golf shot. Three groups of golfers with varying ability and experience were required to hit 50 balls with a 9-iron club to a target. Outcome accuracy for each shot was assessed in terms of the distance between the target and the resting location of the ball. Edited videotapes (showing only execution of the golf swing) of the five most, and five least accurate shots produced a sub-sample of these golfers (four professional players; four novice players) were subsequently viewed by three expert coaches. They independently rated using the checklist, the quality of execution of the 80 golf swings in random order without having information about the accuracy of any shot. As expected, the professional golfers completed more accurate golf shots than did the novices, and the golf swings completed by the professionals were rated more highly than those completed by the novices. However, for both groups of golfers the results indicated that there was no clear relationship between the rated quality of execution of golf swings and the outcome accuracy of the shots of which the swing were the initial part. Chapter 5 provides a summary and overview of the research reported in Chapter 1 to 4. It is argued that this research suggests a need for a change of emphasis in golf coaching away from consideration of the golf swing in isolation to consideration of the golf swing as part of a complete action. That is, the quality of execution of a golf swing should not be judged simply in relation to some ideal set of golf-swing components, but rather in relation to how well the completed swing (i.e., the golf shot) achieves the desired aim of propelling the ball from its present location to the target location.

Employee psychological contracts

This thesis concerns the psychological contracts of employees. A psychological contract is an employee’s perception that: 1) an employer has certain obligations to them, and 2) in return, they have obligations as employees. A psychological contract is therefore a set of subjectively perceived reciprocal obligations. The psychological foundations of this construct are linked with cognitive schemas and social exchange theories. While the concept of psychological contracts was first proposed in the early 1960s, it has only been operationalised for empirical study in the last decade. The purpose of the thesis was to increase the understanding of the content and structure of employee psychological contracts and their links with career cognitions. The specific aims of the thesis were to: 1) examine the relational-transactional dimensions of psychological contracts, 2) develop a comprehensive set of workplace obligations for use with employees, 3) consider alternative dimensions of employee psychological contracts, 4) demonstrate reciprocity between obligations, and 5) determine whether psychological contracts directly affect career cognitions. The thesis contains four quantitative studies. Data were collected using self-report questionnaires that contained both established and new measures. Most participants were employees from a large insurance company, government vocational services or educational institutions. The analyses included canonical correlation, factor analysis, development of measurement models and structural analysis. The findings did not strongly support a distinction between relational and transactional obligations. Instead, a five-factor model of psychological contracts emerged from an expanded set of workplace obligations when it was used with two separate employee samples. This model demonstrated reciprocal relationships between the dimensions of employee and employer obligations. It was also found that alternative dimensions of the psychological contract have a direct influence on organisational commitment and career satisfaction. The thesis supports several general conclusions about the nature of employee psychological contracts, appropriate measures and future research. General workplace obligations that apply across different workplaces can be found, and these should continue to be refined. Such workplace obligations group in meaningful ways, and they can be usefully studied in terms of employer support and employee attitudes to work, rather than in terms of relational and transactional dimensions. Furthermore, this thesis shows that reciprocity in psychological contracts can be demonstrated by correlations between dimensions of employee and employer obligations. The measure used for studying reciprocity was new, and it requires further work. However, this measure is as reliable and valid as any currently available. Measurement is the single most urgent issue facing researchers. Finally, this thesis provides sufficient empirical evidence to support the claim that psychological contracts are an important variable for the understanding of careers.

Scheduling of a parallel computation-bound application and sequential applications executing concurrently on a cluster - a case study.

Studies have shown that most of the computers in a non-dedicated cluster are often idle or lightly loaded. The underutilized computers in a non-dedicated cluster can be employed to execute parallel applications. The aim of this study is to learn how concurrent execution of a computation-bound and sequential applications influence their execution performance and cluster utilization. The result of the study has demonstrated that a computation-bound parallel application benefits from load balancing, and at the same time sequential applications suffer only an insignificant slowdown of execution. Overall, the utilization of a non-dedicated cluster is improved.

Large economies with differential information but without free disposal

We consider exchange economies with a continuum of agents and differential information about finitely many states of nature. It was proved in Einy, Moreno and Shitovitz (2001) that if we allow for free disposal in the market clearing (feasibility) constraints then an irreducible economy has a competitive (or Walrasian expectations) equilibrium, and moreover, the set of competitive equilibrium allocations coincides with the private core. However when feasibility is defined with free disposal, competitive equilibrium allocations may not be incentive compatible and contracts may not be enforceable (see e.g. Glycopantis, Muir and Yannelis (2002)). This is the main motivation for considering equilibrium solutions with exact feasibility. We first prove that the results in Einy et al. (2001) are still valid without freedisposal. Then we define an incentive compatibility property motivated by the issue of contracts’ execution and we prove that every Pareto optimal exact feasible allocation is incentive compatible, implying that contracts of competitive or core allocations are enforceable.

Electromyographic validation of the trapezius and serratus anterior muscles in frontal-lateral cross, dumbbells exercises

Based on the lack of electromyographic researches on sport and programmes of physical conditioning, we can say that it is necessary to reexamine some exercises routinely used in the programmes of physical conditioning. Thus, the trapezius and serratus anterior muscles were studied electromyographically so that we could evaluate the validity in some ways of execution of the frontal-lateral cross, dumbbells exercises for the development of these muscles. We analyzed 24 male volunteers, 18 to 25 years old, using a 2-channel TECA TE 4 electromyograph and Hewlett Packard surface electrodes. For the execution of the exercise it was used a supine bench, a straight board and two bars of 40 cm made of light wood. The results showed that TS acted preferentially in standing modality and in the inclined supine modality, however with activity levels that do not justify its inclusion in physical fitness programmes.

Electromyographic validation of basic exercises for physical conditioning programmes V. The comparison of the response in the deltoid muscle (anterior portion) and the pectoralis major muscle (clavicular portion) determined by the frontal-lateral cross, dumbbells and the rowing exercises

The action potential level for shoulder muscles deltoid-anterior portion (DA) and pectoralis major-clavicular portion (PMC) determined by four different modalities of execution of rowing exercises, each one with two different grips, was recorded. These were compared with the action potential level determined for the same muscles by four different modalities of execution of the frontal-lateral cross, dumbbells exercises. Twenty-four male volunteers were examined using a 2 channel TECA TE4 electromyograph and Hewlett Packard surface electrodes. The statistic analysis showed significant (p<0,05) superiority for all the frontal-lateral cross, dumbbells exercises in comparison to all rowing exercises for the PMC, for the DA this generalized supremacy was not observed.

Comparative study of algorithms for mining association rules: Traditional approach versus multi-relational approach

The multi-relational Data Mining approach has emerged as alternative to the analysis of structured data, such as relational databases. Unlike traditional algorithms, the multi-relational proposals allow mining directly multiple tables, avoiding the costly join operations. In this paper, is presented a comparative study involving the traditional Patricia Mine algorithm and its corresponding multi-relational proposed, MR-Radix in order to evaluate the performance of two approaches for mining association rules are used for relational databases. This study presents two original contributions: the proposition of an algorithm multi-relational MR-Radix, which is efficient for use in relational databases, both in terms of execution time and in relation to memory usage and the presentation of the empirical approach multirelational advantage in performance over several tables, which avoids the costly join operations from multiple tables. © 2011 IEEE.

Aspectos jurídicos da celebração de contratos pela Internet

Pós-graduação em Direito - FCHS