Numerical Algorithms and Intelligent Software for the Evolving HPC Platform
Lead Research Organisation:
University of Edinburgh
Department Name: Sch of Mathematics
Abstract
Advances in computing power have broadened the spectrum of applications amenable to computational treatment, but software improvements must keep pace with advances in computing technology if new hardware investment is to be fully exploited for the benefit of society. Numerical analysis is a traditional strength of UK mathematics, but it must establish new means of collaboration with computer scientists to be relevant for the fast changing platforms of high performance computing. In this well-supported and timely initiative, numerical analysts at Edinburgh, Heriot-Watt and Strathclyde Universities will work together with compiler experts from Edinburgh Informatics and specialists in parallel computing from the Edinburgh Parallel Computing Centre (EPCC) to improve the software development paradigm for implementation of numerical algorithms on diverse and evolving multiprocessor systems. By bringing mathematicians and computer scientists into close collaboration with HPC specialists, this initiative will address key issues raised in the international reviews of UK mathematics and high performance computing. Additional strategic appointments will be made by the universities, providing a sustainable, long-term commitment. Advanced numerical algorithms will be developed for state-of-the-art applications, such as high order adaptive finite elements for solid and fluid mechanics, numerical optimization, multi-scale methods, and new parallel methods for molecular simulation and data analysis. Algorithms will be coded using better systems of markup and annotation, and new compilation techniques will be introduced by the computer scientists and implemented in collaboration with researchers at EPCC. This paradigm shifts the details of implementation to compilers, but compilers informed by algorithm developers via annotation. The methods developed will have clear potential to impact the key themes of the EPSRC delivery plan, including energy, health sciences, nanoscience, and the digital economy. To strengthen the uptake of new methodology among the research base, algorithms will be tested and their performance evaluated in collaboration with applications scientists and engineers. This proposal includes knowledge exchange partnerships with major computing companies (HP, IBM, SGI) as well as industrial users of HPC algorithms (Schlumberger, Orange/France Telecom, SAS), opening new pathways for effective utilisation of new software techniques. Connections to national laboratories such as Daresbury and Rutherford Appleton are also planned. The project is further enhanced through funded connections with Cambridge University, the University of Warwick, and the Wales Institute for Mathematical and Computational Science.
Publications
Richtarik Peter
(2016)
Distributed Coordinate Descent Method for Learning with Big Data
in JOURNAL OF MACHINE LEARNING RESEARCH
Richtarik, P
Distributed Coordinate Descent Method for Learning with Big Data
in Journal of Machine Learning Research
Richtárik P
(2012)
Operations Research Proceedings 2011
Richtárik P
(2015)
Parallel coordinate descent methods for big data optimization
in Mathematical Programming
Richtárik P
(2015)
On optimal probabilities in stochastic coordinate descent methods
in Optimization Letters
Richtárik P
(2012)
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
in Mathematical Programming
Sergio Campobasso M
(2013)
Turbulent Navier-Stokes analysis of an oscillating wing in a power-extraction regime using the shear stress transport turbulence model
in Computers & Fluids
Stratford K
(2014)
Self-assembly of colloid-cholesteric composites provides a possible route to switchable optical materials.
in Nature communications
Svärd M
(2012)
Third-order accurate entropy-stable schemes for initial-boundary-value conservation laws
in Zeitschrift für angewandte Mathematik und Physik
Tak
(2013)
TOP-SPIN: TOPic discovery via Sparse Principal component INterference
in arXiv e-prints
| Description | Compiler-based SC enforcement [PACT '10] [IJPP '11]Although sequential consistency (SC) is most intuitive of memory models, and enables programmers to reason about their programs the best, current processors support relaxed memory models for performance. Programs running on such relaxed models can be transformed to enforce SC by inserting memory fences at appropriate points using Shasha and Snir's delay set analysis. Insertion of such memory fences, however, can signi_cantly slowdown the program, since memory fences are costly. In this work, we observed that most of the memory fences need not stall since the ordering that fences strive to enforce is typically already enforced in the normal course of execution. We proposed the conditional fence mechanism (C-Fence) that decides dynamically if there is a need to stall at each fence and stalls only if necessary. Experiments show that with C-Fences enforcing SC incurs only 12% slowdown, as opposed to 43% slowdown using conventional fences. Hardware-based SC enforcement [ASPLOS' 12]Building upon [PACT '10], we then proposed an efficient hardware based SC implementation requiring no compiler analysis. In this work we identify those con_icting memory operations whose ordering is critical for the maintenance of SC and explicitly order only these. This allows us to safely (non-speculatively) reorder memory operations while still ensuring SC. Our experiments show that SC can be achieved very efficiently, with performance comparable to RMO (relaxed memory order) - one of the most relaxed memory models. Fast RMWs for TSO [PLDI '13] [ASPLOS-Poster '12]Atomic Read-Modify-Writes (RMWs) are primitive synchronization operations using which a variety of concurrency problems are solved. RMWs, however, are expensive in mainstream processor architectures such as x86 which support Total-Store-Order (TSO) -- where these are ordered like a memory barrier, incurring the cost of a write-buffer drain. In this work [4] we proposed an efficient RMW implementation for TSO - experiments show that the proposal reduces the cost of an RMW by 64.5%.Efficient Supervised Memory Systems [CF '12]Supervised memory systems maintain additional metadata for each memory address accessed by the program, to control and monitor accesses to the program data - examples include memory checking, race detection, and transactional memory. While, existing supervised systems assume SC, we show how they can be efficiently adapted for relaxed memory models like TSO. References:[PACT '10] Efficient Sequential Consistency Using Conditional Fences The 19th International Conference on Parallel Architectures and Compilation Techniques,Vienna, Austria, September 2010. (Won a Best Paper Award)[IJPP '11] Efficient Sequential Consistency Using Conditional Fences International Journal of Parallel Programming, June 2011.[ASPLOS '12] Efficient Sequential Consistency via Conflict Ordering ACM 17th International Conference on Architectural Support for Programming Languages and Operating Systems, March 2012.[ASPLOS-Poster '12] Fast RMWs for TSO ACM 17th International Conference on Architectural Support for Programming Languages and Operating Systems,Poster session. (Won 2nd prize: best poster) [CF '12] SuperCoP: A General, Correct, and Performance-efficient Supervised Memory System ACM International Conference on Computing Frontiers, May 2012.[PLDI '13]: Fast RMWs for TSO: Semantics and Implementation ACM SIGPLAN Conference on Programming Language Design and Implemenation,to appear. |
| Exploitation Route | Edinburgh - Maths NAIS has hosted or organized around 60 events (workshops, seminars, training sessions) in the past 4 years addressed to a wide variety of topics. There was an immense ground swell of interest in the area of high performance computing within the School of Mathematics, with strong involvement by both staff and graduate students. Currently in post, and working in a substantial way on HPC-related research are 8 staff, whereas at the start of the project, only about 4 could be identified in this way. During the period of the centre operation, Cartis and Tanner both also benefitted substantially from NAIS support, before their move to Oxford in 2013. Some specific follow-on projects involving Mathematics that have built on the foundation provided by NAIS include an EPSRC-NSF grant in Software Infrastructures for Sustained Innovation, the Centres for Doctoral Training in Analysis and Its Applications and Data Science, EPSRC grants Accelerated Coordinate Descent for Big Data Problems and Algorithms for Data Simplicity. Edinburgh - EPCC Having the NAIS grant has enabled EPCC to be a leader in Exascale research in UK, EU, and global projects. The expertise and collaborations built up during the project enabled EPCC to be active and involved in some of the flagship Exascale projects, such as Nu-FuSE and CRESTA. It was also instrumental in establishing workshops and conferences (such as the EASC conferences) in high performance and parallel computing that have built collaborations for EPCC and the University of Edinburgh, and have brought world class scientists to the UK for collaborations and research. Edinburgh - Informatics The appointment of Nagarajan represents an outstanding strengthening of our ICSA research group. Since appointment Nagarajan has built his own research group, attracting substantial RCUK and industrial funding. PDRA appointment Fensch went on to acquire an RAE fellowship which enabled him to extend his period in the school. This led to further successes (including collaborative funding from Samsung). He recently obtained a lectureship at Heriot-Watt, and continues to collaborate with the Edinburgh NAIS core. These appointments have contributed significantly to the growing critical mass of parallel computing research in Edinburgh and Central Scotland. This was recognized by the recent award of an EPSRC Centre for Doctoral Training in Pervasive Parallelism. Heriot-Watt All three of the appointments (Loisel, Banjai and Gimperlein) are open-ended, and have really strengthened our Scientific Computing group. Loisel is already training three PhD students, and worked closely with two shorter-term NAIS post-docs (Subber and Nguyen). Banjai has a current PhD student and Gimperlien is about to start on a project with a new PhD student. These three staff appointments provide a very strong base to continue NAIS-related work long into the future, and the students will take what they learn into industry or academia. Other staff, such as Lord are supervising students in NAIS-related areas, and the NAIS project has encouraged people to work in this area, and educated them in the techniques required to do so. Strathclyde Despite the fact that the PI and the EPSRC-funded lecturer (Ergul) left in 2012, we have been able to appoint a talented experienced researcher (Dolean), who brought a highly needed expertise in the interface of mathematics and HPC to the Department. She also brings an expertise that acts as a bridge between different parts of the Numerical Analysis and Scientific Computing group. As a matter of fact, she is already supervising a PhD studentship (Bosy) in collaboration with Barrenechea. Also, as a part of her PhD studentship, Yorston has done the master in High-Performance Computing in Edinburgh. She, as well as other PhD students (Riaz, Allendes, Bosy) have attended several training courses in HPC, programming in GPUs, and similar topics. Finally, it is interesting to notice that the dedicated cluster that was purchased has been intensively used, not only by the academics and students linked to the project grant, but also by other members of the department, including academics of the Population Modelling Group. For the moment in this group they are using a commercially purchased code, but their need made it clear that good HPC/Computational Mathematics are needed, and the starting point of a collaboration is in place. |
| Sectors | Digital/Communication/Information Technologies (including Software) |
| Description | (i) Other UK research groups The NAIS initiative has led to increased collaboration both within the partner institutions as well as with NA-HPC communities across the UK, especially the NAIS extended network partners (Bath, Leicester and Warwick). NAIS co-organised the NA-HPC networks, based in Manchester. The collaboration between academics was promoted throughout the lifetime of the NAIS programme, supported through sponsored seminar series, workshops/meetings and research visits. This culminated in a series of meetings in the final 6 months of the programme. Either organised or co-supported by NAIS, these meetings covered a broad range of topics. These events were held at the NAIS centres at Edinburgh and Glasgow, as well as at NAIS Network venues throughout the UK (Cambridge, Durham, Bath and Dundee). With over 500 delegates, these meetings represent an excellent opportunity for cross-discipline networking, research ideas exchange. As a consequence of these meetings, and earlier activities, we are already aware of joint projects being initiated and NAIS members arranging future research visits. (ii) Industry and commerce During the NAIS programme there has been a wide range of external (industry/commerce) involvement in the programme through, participation in workshops/meetings, student placements, specific research collaboration, fellowships/awards for NAIS researchers and Industry visits/briefings. Areas of collaboration have included HPC/Software/Hardware (Cray, Agilent, Intel, OpenAcc Standards Consortium), Engineering/Defence/Aerospace (Dstl/Selex/QinetiQ/Airbus/ Cobham/Sandia/Naval Research laboratory), Drug Design/Molecular Dynamics (Plebiotic, Accelrys, NVIDIA, IBM), Industrial Fellowships/Awards/Student Placements (Google/Intel/IBM), Marketing/Social Media/Big Data (Bloom Media/IQcodex/Schuh/Tag Digital/Merchant Soul/NHS/Scottish Government/HRL Labs), Finance (Bloomberg LP, Lloyds Banking Group), Optimisation (Amazon, SAS Institute, IBM, Baidu, Western General Hospital, Arup), Medical Imaging (SINAPSE), and Oil and Gas (DNV-GL). (iii) International collaboration Through the meetings/workshops discussed previously, sponsored research visits, and appointment of staff with established connections, the NAIS programme has led to substantially enhanced international collaborations. This includes links/collaborations with researchers based in the US (Rice, Chicago, Texas, Wisconsin Madison University, UC Berkeley), across Europe, (CERFACS (France), Besancon (France), Paris (France), Geneva (Switzerland), Louvain-la-Neuve (Belgium), Bonn (Germany) and the Swiss National Supercomputer Centre), as well as the rest of the world (Singapore). Additionally, many of the industrial connections detailed in (ii) were international. (iv) Collaboration leading to building capability Collaborations with other UK research groups established in this programme will be key to ongoing research excellence/success, e.g. the links between the Informatics Group and EPCC are a key feature of the CDT in Pervasive Parallelism, links between EPCC and UoE Maths were key to obtaining a joint NSF-EPSRC software infrastructures grant. Networks, established and co-organised under this programme will provide long-term opportunities for collaboration of UK NAIS members. The established industrial/commerce links are being used in on-going and future research projects. For example, Google, SAS, Amazon and Baidu are involved as a project partner in an EPSRC bid, SAS is a project partner in a funded EPSRC grant, Selex and Dstl were used in shaping the industrial participation for the successful MIGSAA CDT. Furthermore, there are examples where Industrial Collaborators re using tangible outputs from research e.g. Google and Amazon are using parallel and distributed algorithms developed in Richtarik's group. These tangible outputs and collaborations are a key success of the programme and will feed directly the future IMPACT case studies from the partner institutions. The international collaborations have provided enhanced scope for research visits. The ability to attract world-leading academics to the partner institutions for seminars/workshops/research visits was a real asset of the NAIS programme. These collaborations have enhanced the international standing of the research as well as providing opportunities to attract world-leading expertise to the UK/partner institutions. |
| Title | Quasi-geostrophic double gyre force function data |
| Description | |
| Type Of Material | Database/Collection of data |
| Year Produced | 2015 |
| Provided To Others? | Yes |
| Title | oBB |
| Description | oBB is an algorithm for the parallel global optimization of functions with Lipchitz continuous gradient or Hessian. The algorithm is described in the paper: Cartis, C., Fowkes, J. M., and Gould, N. I. M. (2013). Branching and Bounding Improvements for Global Optimization Algorithms with Lipschitz Continuity Properties |
| Type Of Technology | Software |
| Year Produced | 2014 |
| Open Source License? | Yes |
| Impact | . |
| URL | https://projects.coin-or.org/oBB/ |