The combination of high-performance parallel programming and multi-core processors is the dominant approach to meet the ever increasing demand for computing performance today. The thesis is centered around OpenMP, a popular parallel programming API standard that enables programmers to quickly get started with writing parallel programs. However, in contrast to the quickness of getting started, writing high-performance OpenMP programs requires high effort and saps productivity. Part of the reason for impeded productivity is OpenMP’s lack of abstractions and guidance to exploit the strong architectural locality exhibited in NUMA systems and manycore processors. The thesis contributes with data distribution abstractions that enable programmers to distribute data portably in NUMA systems and manycore processors without being aware of low-level system topology details. Data distribution abstractions are supported by the runtime system and leveraged by the second contribution of the thesis – an architecture-specific locality-aware scheduling policy that reduces data access latencies incurred by tasks, allowing programmers to obtain with minimal effort upto 69% improved performance for scientific programs compared to state-of-the-art work-stealing scheduling. Another reason for reduced programmer productivity is the poor support extended by OpenMP performance analysis tools to visualize, understand, and resolve problems at the level of grains– task and parallel for-loop chunk instances. The thesis contributes with a cost-effective and automatic method to extensively profile and visualize grains. Grain properties and hardware performance are profiled at event notifications from the runtime system with less than 2.5% overheads and visualized using a new method called theGrain Graph. The grain graph shows the program structure that unfolded during execution and highlights problems such as low parallelism, work inflation, and poor parallelization benefit directly at the grain level with precise links to problem areas in source code. The thesis demonstrates that grain graphs can quickly reveal performance problems that are difficult to detect and characterize in fine detail using existing tools in standard programs from SPEC OMP 2012, Parsec 3.0 and Barcelona OpenMP Tasks Suite (BOTS). Grain profiles are also applied to study the input sensitivity and similarity of BOTS programs. All thesis contributions are assembled together to create an iterative performance analysis and optimization work-flow that enables programmers to achieve desired performance systematically and more quickly than what is possible using existing tools. This reduces pressure on experts and removes the need for tedious trial-and-error tuning, simplifying OpenMP performance analysis. / <p>QC 20151221</p>

No description available.

Thesis (MEng)--Stellenbosch University, 2003. / ENGLISH ABSTRACT: The goal of this thesis is to provide a stepping-stone for the design and development of a software package that implements the Goal System Algorithm, based on the Theory of Constraints (TOC). This includes the complete description and explanation of the Goal System Algorithm (GS), as well as the partial implementation of this algorithm using Microsoft Access as a Database Management System (DBMS) and Microsoft Visual C++ as programming language. The main development effort was put into the development of a scheduling algorithm and the implementation of a data structure that lies at the core of this algorithm. The reason for the development of such a package is that it will aid a production manager, working in a small to medium size job-shop, in generating a schedule for production that will increase throughput, while simultaneously reducing both inventory and operating expense thereby generating profits and cash flow. With regard to this thesis and the overall project goal the following have been achieved. 1. The complete project has been researched, scoped and each step has been explained. 2. The complete program structure has been defined and broken into two separate modules; the Data Mining and Conversion Module and the TOC Scheduling Algorithm. 3. The database containing all the MRP data necessary for scheduling has been designed and implemented using a MS Access database with an ODBC connection. An ODBC connection to the database was used so that a smooth transmission to other database management systems can be made. 4. The TOC Scheduling Algorithm has been developed and the following have been implemented: • A basic user interface has been created for the insertion of all the user input and to display the constraint schedule. • A data structure called a linked list has been developed and used to store the scheduling data in memory. • The complete GS algorithm had been researched and explained. • The GS algorithm has been and implemented and tested up to the point where it schedules the constraint. • The pseudo code for the part of the GS algorithm that was not implemented has been documented and included in this report. More development needs to be done and a proper Graphical User Interface must also be created to complete this project, but after completion a Toe software package will exist that is completely unique in South Africa and the market potential for this package will be considerable. / AFRIKAANSE OPSOMMING: Die doel van hierdie tesis is om die grondslag te skep vir die ontwerp en ontwikkeling van 'n sagteware pakket wat Goldratt se Doel Sisteem Algoritme, gebasseer op die 'Theory of Constraints', implementeer. Dit sluit die gedetaileerde beskrywing van die Doel Sisteem Algoritme in en 'n gedeeltelike implementasie van die algortime, deur gebruik te maak van 'n Microsoft Access databasis as databasis bestuur sisteem en Microsoft Visual C++ as 'n programerings taal. Die hoof klem is gelê op die ontwikkeling van die skedulerings algortime en die implementasie van die strukture wat deel van die kern uitmaak van die algoritme. Die hoof rede vir die ontwikkeling van so 'n pakket is sodat dit 'n produksie bestuurder van 'n klein to medium grootte vervaardigings besigheid sal help om 'n skedule vir produksie the genereer wat die vloer se deurset sal verhoog, terwyl dit voorraad en operasionele kostes sal verlaag. Met ander woorde dit sal die besigheid help om meer geld te maak huidiglik en in die toekoms. Met betrekking tot die tesis en die algehele projek doel is die volgende bereik: 1. Die hele projek is nagevors, uit een gesit en verduidelik. 2. Die hele program struktuur is gedefinieer en opgebreek in twee aparte modules; nl. die 'Data Mining and Conversion Module' en die 'TOC Scheduling Algorithm'. 3. Die databasis wat al die nodige MRP inligting bevat wat benodig word vir skedulering is ontwerp en geimplementeer deur gebruil te maak van 'n MS Access databasis met 'n ODBC konneksie. Daar is van 'n ODBC konneksie gebruik gemaak sodat as die nodig is, daar sonder enige moeite na ander databasis bestuurs sisteme oorgeskakel kan word. 4. Die 'TOC Scheduling Algorithm' is onwikkel en die volgende is geimplementeer. • A basisse gebruikers vlak is ontwikkel sodat al die nodig invoer data in die program ingevoer kan word. • 'n Geskakelde lys is ontwikkel en gebruik as die data struktuur om al die skedulerings informasie in geheue te stoor. • Die Doel Sisteem algorimte is in sy geheel verduidelik en gedokumenteer. Die Doel Sisteem algoritme is geïmplementeer tot op die punt waar dit die primêre bottelnek skeduleer. • Die pseudo kode vir die deel van die GS algoritme wat nie geimplementeer is nie is uitgelê in ingesluit as deel van die verslag. Verdere ontwikkeling word nog benodig en 'n beter gebruikers vlak moet nog geskep word om die projek te finaal afte handel, maar na dit gedoen is sal daar 'n TOe skedulering pakket bestaan wat heeltemal uniek is tot Suid-Afrika en 'n groot mark potensiaal sal hê.

Thesis (MSc)--Stellenbosch University, 2015. / ENGLISH ABSTRACT: Profitability in the export driven South African blueberry industry is dependent on early spring harvests. The George region in the Western Cape accumulates too few chill-units to release buds of some southern highbush (SHB) blueberry cultivars from endodormancy. This causes problems like delayed budbreak and extended harvests. Growers of other temperate fruit crops are also affected by these problems and chemical rest breaking agents (RBAs) are applied in orchards in an attempt to overcome these. Application of the RBA hydrogen cyanamide (HC) occurs commonly in commercial pome and stone fruit orchards while thidiazuron (TDZ), another RBA is applied on a limited scale in apple orchards. The effect of RBA application on berry ripening, berry size and yield in SHB cultivars Bluecrisp, Emerald and Star was investigated for two seasons in an orchard near George, in order to determine to what extent harvest scheduling with RBAs is possible. Following Dormex® (HC, 520 g L-1) application during 2010, when a warm winter was experienced, the berry ripening of ‘Bluecrisp’ was accelerated. Dormex® application before reproductive bud scales opened, but after some chilling, resulted in acceptable yield and berry size without damage to reproductive buds. A 1% rate gave similar results as a 2% rate, but at a lower risk of reproductive bud damage. Lift® (TDZ, 3 g L-1) application reduced the number of days to 75% harvest in ‘Star’ during 2010. Lower yielding plants produced larger berries than those from higher yielding plants. Lift® application after reproductive buds scales have opened caused malformed and damaged flowers. Delaying the initiation of reproductive buds could delay spring reproductive budbreak until after new leaves had formed. In turn, this should induce a faster berry ripening rate in some SHB cultivars than would otherwise be the case following unseasonably warm winters. Reproductive bud initiation in SHB blueberries occurs under long (16 hours) nights with the mediation of phytochrome. It is possible in a controlled environment to suppress SHB blueberry reproductive bud initiation by night interruption (NI). The effect of NI on berry ripening, berry size and yield in ‘Emerald’ and ‘Snowchaser’ was investigated for two seasons, to determine what degree of harvest scheduling is possible with this technique. NI did not suppress reproductive bud development under these trial conditions, since both cultivars flowered and produced fruit. The effect on berry size and yield was cultivar specific. During 2011 NI decreased the number of berries harvested and total yield per plant in ‘Emerald’, and this decrease was linear the longer the NI lasted. / AFRIKAANSE OPSOMMING: Winsgewendheid in die uitvoer-gedrewe Suid-Afrikaanse bloubessie-bedryf is van vroeë lente oeste afhanklik. In die George-omgewing in die Wes-Kaap bou te min winterkoue op om die endodormansie van sommige ‘southern highbush’ (SHB) bloubessie kultivars natuurlik op te hef, wat probleme soos vertraagde bot en uitgerekte oestye veroorsaak. Produsente van ander gematigde vrugtesoorte, word ook deur hierdie probleme geraak en chemiese rusbreekmiddels (RBs) word in boorde aangewend in ’n poging om dit te oorkom. In kern- en steenvrugboorde vind aanwending van die RB waterstofsianamied (WS) algemeen plaas. Thidiazuron (TDZ), ’n ander RB word op beperkte skaal in appelboorde aangewend. Die uitwerking van RBs op bessierypwording, -grootte en opbrengs van SHB kultivars Bluecrisp, Emerald en Star is oor twee seisoene in ’n boord naby George ondersoek, om vas te stel tot watter mate bloubessie-oesskedulering met behulp van RB aanwending moontlik is. Na Dormex® (WS, 520 g L-1) aanwending in 2010, waarin ’n warm winter ondervind is, is die bessierypwording van ‘Bluecrisp’ versnel. Dormex® aanwendingstye voordat blomknopskubblare oopmaak, maar nadat winterkoue opgebou het, het ’n aanvaarbare opbrengs en bessiegrootte met geen blomknopskade tot gevolg gehad nie. ’n 1% Konsentrasie gee soortgelyke reaksies as ’n 2% aanwending maar teen ’n laer risiko vir blomknopskade. Lift® (TDZ, 3 g L-1) aanwending het die aantal dae tot 75% oesinsameling van ‘Star’ in 2010 verminder. Plante wat ’n laer opbrengs lewer produseer groter bessies as die wat ’n hoër opbrengs lewer. Lift® aanwending nadat blomknopskubblare oopgemaak het, het misvormde en beskadigde blomme tot gevolg gehad. Vertraging van blomknopinisiasie kan die oopmaak van blomknoppe uitstel tot na nuwe blare in die lente gevorm het. Dit kan vinniger bessie rypwording meebring as wat die geval vir sommige SHB kultivars na warm winters is. Die aanvang van blomknopontwikkeling in SHB bloubessies vind tydens lang nagte (16 ure) plaas en staan onder beheer van fitochroom. Onder beheerde toestande kan bloubessie blomknopinisiasie deur onderbreking van die lang donker (nag) tydperk (ON) in ’n lig-donker siklus onderdruk word. Die uitwerking van ON op bessierypwording, -grootte en opbrengs van ‘Emerald’ en ‘Snowchaser’ is oor twee seisoene ondersoek, om die mate waartoe oesskedulering met hierdie tegniek in ’n boord moontlik is aan te spreek. ON het nie die blomknopinisiasie onder hierdie eksperimentele toestande onderdruk nie, aangesien beide kultivars in albei seisoene kon blom en opbrengste lewer. Die effek op bessiegrootte en opbrengs was kultivar spesifiek. In 2011 is die totale opbrengs en hoeveelheid bessies per plant geoes van ‘Emerald’, deur ON verminder en dié vermindering was liniêr met toename in aantal ON siklusse.

This study examines the impact of successive versus non-successive scheduling of mathematics courses on the achievement of ninth-grade students in a suburban Oregon high school. The Oregon Assessment of Knowledge and Skills and student performance on the geometry course final exam were employed to compare the achievement of intact groups of students who had geometry scheduled for two successive trimesters and students who had geometry in two non-successive trimesters. An ANCOVA provides a comparison of students on pre-test and post-test performance. The results show no differences in student mathematics achievement as a result of scheduling differences after the covariate pre-test is examined. The implications are that schools may choose schedules for reasons other than improving student achievement and that scheduling does not impact student achievement.

In this thesis, we propose a number of distributed schemes for wireless communications in the cross layer design context, considering an uplink random access network in which multiple users communicate with a common base station. In addition, we perform a comprehensive study on a splitting based multiuser selection algorithm which is simple, effective, and scales with the network size. First, we investigate a reservation-type protocol in a channel aware ALOHA system. Various Markovian models are used to describe the system and to capture the temporal correlation of the channel evolution. The average throughput of the system is obtained using the Markov Analysis technique and we show that the reservation protocol can achieve better performance than the original channel-aware ALOHA by reducing the collision probability. Second, for better resource utilization in the Opportunistic Multichannel ALOHA scheme, we propose a simple extension to the transmission policy that exploits the idle channels. Performance analysis shows that, theoretically, the maximum system throughput can be improved by up to 63% in the asymptotic case. Through numerical results, it can be seen that a significant gain is achieved even when the system consists of a small number of users. Third, we consider a splitting based multiuser selection algorithm in a probabilistic view. Asymptotic analysis leads to a functional equation, similar to that encountered in the analysis of the collision resolution algorithm. Subject to some conditions, the solution of the functional equation can be obtained, which provides the approximations for the expected number of slots and the expected number of transmissions required by the algorithm in a large system. These results shed light on open design problems in choosing parameters for the algorithm when considering the delay and the overhead jointly. A typical example is to optimize the parameters that minimize the weighted sum of these measures of interest.

Master of Science / Department of Industrial and Manufacturing Systems Engineering / Todd W. Easton / Jessica L. Heier Stamm / Locomotives in the U.S. use over 3 billion gallons of fuel each year and faster refueling can increase rail network capacity without the infrastructure cost associated with new terminals or tracks. This thesis introduces the locomotive refueling system configuration problem (LRSCP), which seeks to improve efficiency in refueling yards through new technologies or policies. This research also creates two new methods to solve LRSCP. The first method uses an integer program to solve the off-line LRSCP and develop a static refueling policy. The train refueling integer program, TRIP, maximizes the weighted number of train combinations that can be refueled without delay. TRIP is optimized and its outputs are used as inputs to a simulation developed in Simio® for testing and validation. The second method creates an integrated integer program and simulation to solve the on-line LRSCP and produces a dynamic refueling policy. This tool, built in Python, incorporates a different integer program, the strike line integer program (SLIP), into the simulation. SLIP determines the optimal refueling assignment for each incoming train. The simulation incorporates SLIP’s solution for testing and validation. This tool is truly integrated and requires approximately 300 instances of SLIP to simulate a single day. Based on experimental results, solving either TRIP or SLIP and incorporating the optimal refueling policy improves railyard operations by 10 to 30%. This impact is statistically significant and increases the capacity of a railyard. Additionally, it impacts other important parameters such as time spent in the yard and the maximum queue for the railyard. Furthermore, there is a significant decrease in wasted time and an improvement to railyard efficiency. Implementing either method should increase a railyard’s capacity and significantly increase revenue opportunities.

The LOIS project aims at building a radio sensor and IT infrastructure in the south of Sweden, primarily with but not limited to the goal of space observations. Signals received produce a gigantic stream of data that has to be processed in real time. Our purpose is scheduling stream computations to computation nodes in such a way that the performance requirements are met. We built a framework where different local and global scheduling algorithms can be executed and tested including a number of benchmarking programs, comparing the performances. We will try to use a method as simple as possible. Given the results of the different local schedules as input – mapping parallel computations (tasks) to processors – along with some parameters such as the algorithm to apply and machine parameters, the framework will compute a global schedule. Moreover, the framework will visualize the results. We understand that framework as a graphic interface able to simulate the manipulation of different tasks, as well as different measurement groups. Showing the better performances is a big aid in order to improve the stream computation.

Com o aumento no uso de aglomerados e grades de computadores, cresce o interesse no estudo de comunicações entre processadores. Em um computador paralelo dedicado, ou em uma rede local homogênea, o tempo de comunicação é geralmente modelado de forma similar, independente de quais processadores estão se comunicando. Em uma rede onde os links entre os computadores são heterogêneos, computadores mais próximos tendem a apresentar menor latência e maior largura de banda do que computadores distantes. Além disso, a largura de banda agregada é diferente dependendo do número de conexões simultâneas existentes entre dois aglomerados distantes. Neste trabalho estudaremos a troca completa de mensagens de tamanhos diferentes entre aglomerados interligados por backbones. Proporemos um novo algoritmo de comunicação baseado em algoritmos conhecidos, apresentaremos simulações de escalonamentos dos algoritmos estudados para esta rede multi-aglomerado e analisaremos os resultados destas simulações. / The growth in popularity of clusters and computational grids caused an increase in the interest in studying interprocessors communications. The comunication time in a dedicated parallel computer or in a local homogeneous network is modeled in a similar way, regardless of which processors are communicating. In a network with heterogeneous links, closer computers generally have lower latency and larger bandwidth than wide area computers. Besides, the aggregated bandwidth depends on the number of simultaneous connections between two wide area clusters. In this work we study the complete exchange of messages of different sizes between interconnected clusters using a backbone. We propose a new comunication algorithm based on known algorithms, we present some scheduling simulations of the studied algorithms in this multi-cluster network and we present the results analysis of these simulations.

The significant growth in multimedia services and traffic (e.g. VoIP, video streaming and video gaming) in current and emerging mobile networks including the latest 4G Long-Term Evolution (LTE) networks and the rising user expectation for high Quality of Experience (QoE) for these services have posed real challenges to network operators and service providers. One of the key challenges is how to bring multimedia services to the end-user over resource-constrained mobile networks with a satisfactory QoE. Cost-effective solutions are needed for network operators to improve the bandwidth usage of these mobile networks. Therefore, scheduling schemes are of extreme importance in LTE, where scheduling algorithms are responsible for the overall efficiency of resource allocation in an LTE system. The aim of the project is to develop novel QoE-driven scheduling algorithms for improving system capacity in delivering multimedia services over downlink 3GPP LTE. This is to move away from traditional QoS-driven scheduling schemes to a QoE-driven scheme which guarantee end-user satisfaction in resource allocation. The main contributions of the thesis are threefold: 1. Performance of several existing scheduling algorithms for VoIP applications was evaluated thoroughly in terms of QoE metric (i.e. MOS), instead of QoS metrics (e.g. packet loss and delay). Using QoE metrics instead of QoS ones will facilitate the development of QoE-driven scheduling schemes in order to achieve optimised end-user experiences or optimised mobile system capacity. 2. A novel QoE-driven LTE downlink scheduling scheme for VoIP application was developed to maximize the number of users per cell at an acceptable MOS score. The proposed scheme achieved significant improvement in cell capacity at an acceptable quality (75% compared to MLWDF, and 250% compared to PF and EXP-PF in all three lower speed scenarios considered). 3. A QoE-driven LTE downlink scheduling scheme for multiservice multimedia applications was developed to improve the cell capacity with satisfactory QoE for both VoIP and video streaming services. The proposed algorithm performed well in a pedestrian scenario increasing cell capacity to double for video stream with ‘Rapid Movement’ (RM) content. For ‘Medium Movement’ (MM) video content, the capacity was increased about 20% compared to MLWDF and by 40% compared to EXP-PF. In a vehicular scenario, the proposed scheme managed to enhance the cell capacity for MM video stream case. The project has led to three publications (IEEE Globecom’12 – QoEMC Workshop, IEEE CCNC’15 and IEEE MMTC E-letter/May-2015). A journal paper is in preparation.