| EPSRC Reference: |
GR/L92150/01 |
| Title: |
NEW PARADIGMS IN DATA STRUCTURE DESIGN: WORD - LEVEL PARALLELISM AND SELF - ADJUSTMENT |
| Principal Investigator: |
Raman, Professor R |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Kings College London |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
17 August 1998 |
Ends: |
31 January 2001 |
Value (£): |
152,104
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
We will consider data structuring problems which involve maintaining dynamically changing data, such as sets of integer or floating-point keys and networks (graphs). The data structuring problems to be considered include fundamental and ubiquitous ones such as searching and priority queue operations, as well as dynamic tree operations. We aim to obtain significant practical and theoretical efficiency gains for these problems by using two new paradigms: (I) exploiting the parallelism at the level of hardware circuits which enables a sequential CPU to operate on word-sized (e.g. 64-bit) data in unit time, referred to as word-level parallelism (WLP) (ii) self-adjusting data structures (SADS), which by means of simple local modifications, effectively learn to process a sequence of operations optimally.To demonstrate the practical efficiency gains of data structures based on WLP and SADS, we will use them in a number of network algorithms, including shortest paths, network flows and local search methods (simulated annealing genetic algorithms) for NP-complete network optimisation problems. These algorithms are used to solve computationally-intensive problems which arise in computer networking, network design, telecoms, scheduling and routing, transporation and financial analysis, and end-users need to handle ever-larger networks, often within stringent time constraints (e.g. in the financial sector).
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
|