The thesis investigates deployment of a Peer-to-Peer storage system in a cluster environment, in which machines have good and persist network connection, in order to provide the functionality of a data centre. For various reasons, the implementation is based on the Peer-to-Peer system known as Chord. Chord naturally provides storage load-balancing, especially if its virtual node scheme is used, but this needs to be improved if Chord is used to implement a storage system. A novel, threshold-based storage load-balancing scheme is proposed. Each machine in the system contributes a fixed amount of disk storage space to the Peer-to-Peer storage system. The system commences operation in the normal Chord manner except that two distinct sets of tables are initialised, one to maintain the usual Chord Ring, and one to maintain proximity information about the machines in the system. As files are inserted, the collective storage space gradually fills up. When any machine reaches the threshold for usage of its contributed space, the system behaviour is modified. Attempts are made, repeatedly if necessary, to migrate virtual nodes from heavily loaded machines to less-heavily loaded machines elsewhere in the system. The proximity information is used so as to minimise the costs of this migration. The nature of the proximity information is complex, and a Space-Filling Curve is utilised to reduce the complexity. For reasons of effectiveness, demonstrated by an evaluation against other kinds of Space-Filling Curve, the Hilbert curve is specifically chosen. The performance of the resulting implementation is evaluated in a practical experimental environment which consists of five teaching laboratories in the author’s school. Under the specific conditions of the experiments, the new system achieves significantly better distribution of storage utilisation across the participating machines and also defers the onset of unreliable behaviour in the system. In one experiment, the amount of the total storage space available that is actually utilised by the system increased from ∼ 43% to ∼ 62% using the proposed mechanism. The parameters used in the experiments have been chosen somewhat arbitrarily, so it is possible that even better results might be feasible.

The advent of multi-core processors, particularly with projections that numbers of cores will continue to increase, has focused attention on parallel programming. It is widely recognized that current programming techniques, including those that are used for scientific parallel programming, will not allow the easy formulation of general purpose applications. An area which is receiving interest is the use of programming styles which do not have side-effects. Previous work on parallel functional programming demonstrated the potential of this to permit the easy exploitation of parallelism. This thesis investigates a dynamic load balancing system for shared memory Chip Multiprocessors. This system is based on a parallel computing model called SLAM (Spreading Load with Active Messages), which makes use of functional language evaluation techniques. A novel hardware/software mechanism for exploiting fine grain parallelism is presented. This mechanism comprises a runtime system which performs dynamic scheduling and synchronization automatically when executing parallel applications. Additionally the interface for using this mechanism is provided in the form of an API. The proposed system is evaluated using cycle-level models and multithreaded applications running in a full system simulation environment.

Masivní vývoj Internetu vedl ke zvýšeným požadavkům na spolehlivou síťovou infrastrukturu. Efektivita komunikace v síti závisí na schopnosti směrovačů určit nejlepší cestu pro odesílání a přeposílání paketů ke koncovému zařízení. Jelikož OSPF v současné době představuje jeden z nejpoužívanějších směrovacích protokolů, jakýkoli přínos, který by pomohl udržet krok s rychle se měnícím prostředí Internetu, je velmi vítán. Významným omezením OSPF protokolu je, mimo jiné, absence informovanosti algoritmu pro výpočet metriky o aktuálním vytížení linky. Tato vlastnost představuje tzv. slabé místo, což má negativní vliv na výkonnost sítě. Z tohoto důvodu byla navržena nová metoda založená na dynamické adaptaci měnících se síťových podmínek a alternativní strategii OSPF metrik. Navržená metoda řeší problém neinformovanosti OSPF metriky o síťovém provozu a nevhodně vytížených linek, které snižují výkonnost sítě. Práce rovněž přináší praktickou realizaci, kdy vlastnosti nové metody jsou testovány a ověřeny spuštěním testů algoritmu v reálných zařízeních.

Currently systems of virtual machines are load balanced statically which can create load imbalances for systems where the load changes dynamically over time. For throughput and response time of a system to be maximized it is necessary for load to be evenly distributed among each part of the system. We implement a prototype policy engine for the Xen virtual machine monitor which can dynamically load balance virtual machines. We compare the throughput and response time of our system using the cpu2000 and the WEB2005 benchmarks from SPEC. Under the loads we tested, dynamic load balancing had 5%-8% higher throughput than static load balancing.

A thesis based around saving response time costs as well as respecting electrical costs of a homogenous multi-server system. / In this thesis we consider the impacts of energy costs as they relate to Size Interval Task Assignment Equally--loaded (SITA-E) systems. We find that given systems which have small and large jobs being processed (high variance systems) we could in some cases find savings in terms of energy costs and in terms of lowering the mean response times of the system. How we achieve this is by first working from SITA-E, wherein servers are always on to Electrically Aware SITA-E (EA-SITA-E) by seeing if it is beneficial to make any of our servers rotate between being on and being off as needed. When most beneficial to do so we will turn off some of the servers in question, after this is completed we reallocate some of the jobs that are on the servers that we decide will be cycling to servers that will remain on indefinitely to better use their idle time. This also lowers the mean response time below what we originally saw with SITA-E, by lowering the variance in the sizes of jobs seen by the servers with the longest jobs. These long--job servers are by far the most impacted by the variance of the sizes of the jobs, so it is very desirable to lower this variance. The algorithm contained here can provide benefits in terms of both energy costs and mean response time under some specific conditions. Later we discuss the effect of errors in our assumed knowledge of task sizes. This research contributes methodology that may be used to expand on EA-SITA-E system design and analysis in the future. / Thesis / Master of Science (MSc) / The intention of this research is to be able to improve on existing size interval task-based assignment policies. We try to improve by turning servers off at key times to save energy costs, while not sacrificing too greatly in terms of mean response time of the servers, and in some cases even improving the mean response time through an intelligent re-balancing of the server loads.

Load imbalance is a major source of performance degradation in parallel scientific applications. Load balancing increases the efficient use of existing resources and improves performance of parallel applications running in distributed environments. At a coarse level of granularity, advances in runtime systems for parallel programs have been proposed in order to control available resources as efficiently as possible by utilizing idle resources and using task migration. At a finer granularity level, advances in algorithmic strategies for dynamically balancing computational loads by data redistribution have been proposed in order to respond to variations in processor performance during the execution of a given parallel application. Algorithmic and systemic load balancing strategies have complementary set of advantages. An integration of these two techniques is possible and it should result in a system, which delivers advantages over each technique used in isolation. This thesis presents a design and implementation of a system that combines an algorithmic fine-grained data parallel load balancing strategy called Fractiling with a systemic coarse-grained task-parallel load balancing system called Hector. It also reports on experimental results of running N-body simulations under this integrated system. The experimental results indicate that a distributed runtime environment, which combines both algorithmic and systemic load balancing strategies, can provide performance advantages with little overhead, underscoring the importance of this approach in large complex scientific applications.

Scientific and engineering problems are often large, complex, irregular and data-parallel. The performance of many parallel applications is affected by factors such as irregular nature of the problem, the difference in processor characteristics and runtime loads, the non-uniform distribution of data, and the unpredictable system behavior. These factors give rise to load imbalance. In general, in order to achieve high performance, dynamic load balancing strategies are embedded into solution algorithms. Over time, a number of dynamic load balancing algorithms have been implemented into software tools and successfully used in scientific applications. However, most of these dynamic load balancing tools use an iterative static approach that does not address irregularities during the application execution, and the scheduling overhead incurred is high. During the last decade, a number of dynamic loop scheduling strategies have been proposed to address causes of load imbalance in scientific applications running in parallel and distributed environments. However, there is no single strategy that works well for all scientific applications, and it is up to the user to select the best strategy and integrate it into the application. In most applications using dynamic load balancing, the load balancing algorithm is directly embedded in the application, with close coupling between the data structures of the application and the load balancing algorithm. This typical approach leads to two disadvantages. First, the integration of each newly developed load balancing algorithm into the application needs to be performed from scratch. Second, it is unlikely that the user has incorporated the optimal load balancing algorithm into the application. Moreover, in a certain application (of various problem sizes and number of processors), it is difficult to assess in advance the advantage of incorporating one load balancing algorithm versus another. To overcome these drawbacks, there is a need for developing an application programming interface (API) for dynamic load balancing scientific applications using the recently developed dynamic loop scheduling algorithms. This thesis describes the design and development of such an API, called ProLAS, which is scalable, and independent of data structures of a host application. ProLAS performance is evaluated theoretically and experimentally (after being used in scientific applications). A qualitative and quantitative analysis of ProLAS is presented by comparing its performance with the state of the art technology in dynamic load balancing tools (e.g. CHARM++ library) for parallel applications. The analysis of the experimental results of using ProLAS in a few scientific aplications indicate that it consistently outperforms the existing technology in dynamic load balancing.

Parallel and distributed environments are used to solve large scientific and engineering problems that often are irregular and data parallel. However, performance of many parallel applications is affected by computation overheads, communication time and load imbalance. Among these factors, load imbalance is caused by the irregular nature of the problem, its algorithm, the difference in processor characteristics, and runtime loads. A number of applications achieve load balancing by one-time assignment of task. However, a number of applications have workloads that are unpredictable, and vary over the course of their execution. For such type of applications, load balancing is achieved by dynamic assignment of tasks at runtime. A large group of scientific applications has parallel loops as major source of concurrency. However, due to the irregular execution times of the loops, it is difficult to achieve optimal performance without dynamic load balancing. There are number of dynamic load balancing tools and libraries have been developed for different kind of applications. However these libraries fail to address all three degradation factors i.e. problem, algorithmic, and systemic. In this thesis a dynamic load balancing library called LB_Migrate is presented which addresses the degradation factors in application with parallel loops. The library provides a range of dynamic scheduling techniques and data migration strategies to achieve effective load balancing. It is designed to be independent of the host application data structure hence providing the flexibility to be used with different applications. The analysis of the experimental results using LB_Migrate with different applications indicates consistent performance improvement, and low overhead cost by the use of the library.

GPU computing can significantly improve performance by taking advantage of massive parallelism of GPUs for data parallel applications. Computation in visualization applications is suitable for parallelization on the GPU, which can improve performance and interactivity in these applications. If used effectively, multiple GPUs can lead to a significant speedup over a single GPU. However, the use of multiple GPUs requires memory management, scheduling, and load balancing to ensure that a program takes full advantage of available processors. This work presents methods for data-driven and dynamic multi-GPU load balancing using a pipelined approach and a framework for use with different applications. Data-driven load balancing can improve utilization for applications by taking into account past performance for different combinations of input parameters. The dynamic load balancing method based on buffer fullness can adjust to workload changes at runtime to gain an additional performance improvement. This work provides a framework for load balancing to account for differing characteristics of applications. Implementation of a multi-GPU data structure allows for use of these load balancing methods in the framework. The effectiveness of the framework is demonstrated with performance results from interactive visualization that shows a significant speedup due to load balancing. / Master of Science

A single-chip, hybrid, heterogeneous, and dynamic shared memory multiprocessor architecture is being developed which may be used for real-time and non-real-time applications. This architecture can execute any application described by a dataflow (process flow) graph of any topology; it can also dynamically reconfigure its structure at the node and processor architecture levels and reallocate its resources to maximize performance and to increase reliability and fault tolerance. Dynamic change in the architecture is triggered by changes in parameters such as application input data rates, process execution times, and process request rates. The architecture is a Hybrid Data/Command Driven Architecture (HDCA). It operates as a dataflow architecture, but at the process level rather than the instruction level. This thesis focuses on the development, testing and evaluation of a new graphic software (hdca) developed to first do a static resource allocation for the architecture to meet timing requirements of an application and then hdca simulates the architecture executing the application using statically assigned resources and parameters. While simulating the architecture executing an application, the software graphically and dynamically displays parameters and mechanisms important to the architectures operation and performance. The new graphical software is able to show system and node level dynamic capability of the HDCA. The newly developed software can model a fixed or varying input data rate. The model also allows fault tolerance analysis of the architecture.