Exploiting wavefront parallelism on large-scale shared-memorymultiprocessors

Wavefront parallelism, in which parallelism is limited to hyperplanes in an iteration space, can arise when compilers apply tiling to loop nests to enhance locality. Previous approaches for scheduling wavefront parallelism focused on maximizing parallelism; balancing workloads, and reducing synchronization. In this paper, we show that on large-scale shared-memory multiprocessors, locality is a crucial factor. We make the distinction between intratile and intertile locality and show that as the number of processors grows, intertile locality becomes more important. We consider and experimentally evaluate existing strategies for scheduling wavefront parallelism. We show that dynamic self-scheduling can be efficiently used on a small number of processors, but performs poorly at large scale because it does not enhance intertile locality. By contrast, static scheduling strategies enhance intertile locality for small tiles, maintaining parallelism and resulting in better performance at large scale. Results from a Convex SPP1000 multiprocessor demonstrate the importance of taking intertile locality into account. Static scheduling outperforms dynamic self-scheduling by a factor of up to 2.3 on 30 processors     

HIV positive tests at Coronial Services in Victoria 1989-1996: lessons for HIV surveillance

Results of routine testing at other sites can supplement surveillance of the HIV epidemic in Australia which is largely based upon voluntary testing. Since 1989, systematic onsite HIV testing has been undertaken on all bodies taken to the Victorian Institute of Forensic Medicine (VIFM). Information was collected on all cases of HIV infection detected at VIFM between 1989 and 1996, and matched to surveillance databases. In 8 years, 75 people were diagnosed with HIV; all except one were male. The age range was 14-70 years, mean 37.4 years. The major causes of death were suicide 35%, AIDS 21%, drug toxicity 16%, natural causes 12% and injury 7%. The major exposure categories were male homosexual 51%, male bisexual 11%, homosexual/bisexual IDU 16%, IDU other 8%, and haemophiliac 7%. For only two was exposure information unavailable. Seropositivity for anti-HCV and HBsAg was 37% and 11% respectively. The deceased was recorded as having HIV/AIDS on the police report in 73% of cases, and at least 90% of subjects had been diagnosed with HIV prior to their death. The study suggests there is relatively little undiagnosed HIV infection in Victoria, that HIV infection has not moved outside traditional risk groups, and that many tests for HIV are undertaken using false namecodes. Many patients could not be matched on the HIV/AIDS databases, identifying a problem with HIV surveillance systems in Victoria, and the need to capture all information on HIV positives detected at VIFM.     

Fusion of loops for parallelism and locality

Loop fusion improves data locality and reduces synchronization in data-parallel applications. However, loop fusion is not always legal. Even when legal, fusion may introduce loop-carried dependences which prevent parallelism. In addition, performance losses result from cache conflicts in fused loops. In this paper, we present new techniques to: (1) allow fusion of loop nests in the presence of fusion-preventing dependences, (2) maintain parallelism and allow the parallel execution of fused loops with minimal synchronization, and (3) eliminate cache conflicts in fused loops. We describe algorithms for implementing these techniques in compilers. The techniques are evaluated on a 56-processor KSR2 multiprocessor and on a 18-processor Convex SPP-1000 multiprocessor. The results demonstrate performance improvements for both kernels and complete applications. The results also indicate that careful evaluation of the profitability of fusion is necessary as more processors are used