Rounding Error Analysis for Non-Standard Floating-Point Hardware

PGR-P-1844

Key facts

Type of research degree: PhD
Application deadline: Ongoing deadline
Country eligibility: International (open to all nationalities, including the UK)
Funding: Non-funded
Source of funding: University of Leeds
Supervisors: Dr Mantas Mikaitis
Additional supervisors: Dr Massimiliano Fasi
Schools: School of Computer Science

<h2 class="heading hide-accessible">Summary</h2>

Background: At the time of writing, a number of high-end hardware devices come equipped with multi-term floating-point adders, that is, units that can compute the sum of more than two numbers at once. Instead of adding two values which has become a standard, such units perform a reduction over multiple numbers, that is, they compute a single scalar result from a vector of numbers. Multi-term addition is usually just one step in the computation of inner products and matrix products, but analytically it can be explored on its own. There are several ways to implement multi-term addition in hardware–the IEEE 754-2019 floating-point standard leaves the implementation undefined. For example, one can perform all operations exactly and then round the exact result to the desired floating-point format–this is the most expensive option in terms of hardware area and latency, since all bits have to be tracked and participate in the sum for the final rounding to be correct. Alternatively, one can perform all operations in some limited precision, for hardware savings and efficiency. With this second approach, one has to specify many parameters–precision, normalization, and rounding–all of which can impact the accuracy and properties of the resultant approximation of the sum. If normalisation is performed only once, at the end of the computation and before the final rounding, precision growth occurs in the internal representation where carries accumulate on addition. When subtraction occurs, precision can be significantly lower than it would be in a normalized system, such as any of the IEEE 754 arithmetics. The work of Metropolis and Ashenhurst on significant-digit computer arithmetic, which dates back to the 1950s, dealt with non-normalized floating-point computations, and together with later refinements it will be relevant to this project. Hypothesis: Current rounding error analysis (Blanchard et al., 2020) does not take into account the fact that, when a reduction is performed, intermediate results are not necessarily normalized, which may result in precision growth or loss of precision, depending on the sign of the operands. The hypothesis underlying this project is that these details about the floating-point hardware can be incorporated into existing rounding error analysis, and that doing so can provide tighter error bounds. Aims and objectives: The aim of the project is to obtain tighter error bounds on reduction operations in floating-point arithmetic.

<h2 class="heading hide-accessible">Full description</h2>

The initial objectives are as follows: 1) Develop an understanding of currently available hardware equipped with units for multi-term addition. 2) Apply the rounding error analysis of Blanchard et al. (2020) to hardware that was released after 2020, and check numerically how tight the worst-case error bounds are. 3) Develop new error bounds that account for non-normalized internal representations in the multi-term addition. 4) Determine how much the new error bounds improve on existing ones, and compare new and old bounds in numerical experiments. Once completed, the error analysis of multi-term adder can be extended to algorithms that utilize it. First, we will investigate summation algorithms that use multi-term adders to first sum blocks of numbers in parallel and then accumulate the partial sums either with multi-term adders or using different arithmetics. Worst-case rounding error bounds would need to be updated to incorporate the new bounds developed in the first part of the project (see Blanchard, Higham, and Mary, 2020). With the new error bounds for summation at hand, we can look into large matrix multiplication in standard floating-point formats and into multi-word matrix multiplication, where each matrix entry is represented by means of several floating-point numbers. Our main aim here will be to check the validity of existing error bounds via numerical experiments and to confirm how the results change with the new error bounds in reduction operations.

<h2 class="heading">How to apply</h2>

Formal applications for research degree study should be made online through the <a href="https://www.leeds.ac.uk/research-applying/doc/applying-research-degrees">University's website</a>. Please state clearly in the Planned Course of Study section that you are applying for PHD Computer Science FT, in the research information section that the research degree you wish to be considered for is Rounding Error Analysis for Non-Standard Floating-Point Hardware as well as <a href="https://eps.leeds.ac.uk/computing/staff/12197/dr-mantas-mikaitis">Dr Mantas Mikaitis</a> as your proposed supervisor and in the finance section, please state clearly the funding that you are applying for, if you are self-funding or externally sponsored. If English is not your first language, you must provide evidence that you meet the University's minimum English language requirements (below). As an international research-intensive university, we welcome students from all walks of life and from across the world. We foster an inclusive environment where all can flourish and prosper, and we are proud of our strong commitment to student education. Across all Faculties we are dedicated to diversifying our community and we welcome the unique contributions that individuals can bring, and particularly encourage applications from, but not limited to Black, Asian, people who belong to a minority ethnic community, people who identify as LGBT+ and people with disabilities. Applicants will always be selected based on merit and ability. Applications will be considered after the closing date. Potential applicants are strongly encouraged to contact the supervisors for an informal discussion before making a formal application. We also advise that you apply at the earliest opportunity as the application and selection process may close early, should we receive a sufficient number of applications or that a suitable candidate is appointed. Please note that you must provide the following documents in support of your application by the closing date of Monday 6 January 2025 if applying for the China Scholarship Council-University of Leeds Scholarship, Monday 3 February 2025 if applying for Leeds Doctoral Scholarship or Tuesday 1 April 2025 for Leeds Opportunity Research Scholarship. If you are applying with external sponsorship or you are funding your own study, please ensure you provide your supporting documents at the point you submit your application: <ul> <li>Full Transcripts of all degree study or if in final year of study, full transcripts to date</li> <li>Personal Statement outlining your interest in the project</li> <li>CV</li> </ul>

<h2 class="heading heading--sm">Entry requirements</h2>

Applicants to this research degree programme must hold a minimum of First Class Honours Bachelor Degree or equivalent in an appropriate discipline. If an Upper Second Class British Bachelors Honours degree (or equivalent) is held, a Masters Degree with Distinction is also required. Applicants who are uncertain about the requirements for a particular research degree are advised to contact the School or Graduate School prior to making an application.

<h2 class="heading heading--sm">English language requirements</h2>

The minimum English language entry requirement for research postgraduate research study is an IELTS of 6.5 overall, with at least 6.5 in writing and at least 6.0 in reading, listening and speaking or equivalent. The test must be dated within two years of the start date of the course in order to be valid. Some schools and faculties have a higher requirement.

<h2 class="heading">Funding on offer</h2>

Self-Funded or externally sponsored students are welcome to apply. UK – The <a href="https://phd.leeds.ac.uk/funding/138-leeds-doctoral-scholarship-2025-faculty-of-engineering-and-physical-sciences#:~:text=Key%20facts&text=One%20Leeds%20Doctoral%20Scholarship%20is,rata%20for%20part%2Dtime%20study.">Leeds Doctoral Scholarship</a> (closing date: Monday 3 February 2025) and <a href="https://phd.leeds.ac.uk/funding/234-leeds-opportunity-research-scholarship-2022">Leeds Opportunity Research Scholarship</a> (closing date: Tuesday 1 April 2025) are available to UK applicants. <a href="https://phd.leeds.ac.uk/funding/60-alumni-bursary">Alumni Bursary</a> is available to graduates of the University of Leeds. Non-UK – The <a href="https://phd.leeds.ac.uk/funding/48-china-scholarship-council-university-of-leeds-scholarships-2021">China Scholarship Council - University of Leeds Scholarship</a> is available to nationals of China (closing date: Monday 6 January 2025). The <a href="https://phd.leeds.ac.uk/funding/73-leeds-marshall-scholarship">Leeds Marshall Scholarship</a> is available to support US citizens. <a href="https://phd.leeds.ac.uk/funding/60-alumni-bursary">Alumni Bursary</a> is available to graduates of the University of Leeds. You will be responsible for paying the overtime fee in full in your writing up/overtime year (£320 in Session 2024/25), but the scholarship maintenance allowance will continue to be paid for up to 6 months in the final year of award. Important: Please note that that the award does not cover the costs associated with moving to the UK. All such costs (<a href="https://www.leeds.ac.uk/international-visas-immigration/doc/applying-student-visa">visa, Immigration Health Surcharge</a>, flights etc) would have to be met by yourself, or you will need to find an alternative funding source. Please refer to the <a href="https://www.ukcisa.org.uk/">UKCISA</a> website for information regarding Fee Status for Non-UK Nationals.

<h2 class="heading">Contact details</h2>

For further information about this project, please contact Dr Mantas Mikaitis by email to <a href="mailto:M.Mikaitis@leeds.ac.uk">M.Mikaitis@leeds.ac.uk</a> For further information about your application, please contact PGR Admissions by email to <a href="mailto:phd@engineering.leeds.ac.uk">phd@engineering.leeds.ac.uk</a>