<p>We are given a sequence of jobs on a single machine, and each job has a weight, processing time and a due date. A job is early when it finishes before or on its due date and its earliness is the amount of time between its completion time and its due date. A job is tardy when it finishes after its due date and its tardiness is the amount of time between its due date and its completion time. The TWET problem is to find a schedule which minimizes the total weighted earliness and tardiness. We are focusing on the TWET problem with a constant number of distinct due dates and polynomially related weights. This problem has been proven to be NP-hard. In this thesis, we present a dynamic programming algorithm for our TWET problem first and then convert it into an FPTAS by adopting a rounding scheme.</p> <p>There are several important points in our algorithm: we observe the importance of the straddlers and guess them at the beginning through exhaustive enumeration, and insert them back at the very end by solving a linear problem; we know a series of structural properties of the optimal schedule to shrink the state space of the DP; we increase each due date to get a new problem and adopt a rounding scheme of the DP for the new problem to avoid preemption. Finally we move the due dates back to get the final schedule for the original TWET problem without changing the objective value much.</p> / Master of Science (MSc)

Cloud is becoming the most popular computing infrastructure because it can attract more and more traditional companies due to flexibility and cost-effectiveness. However, privacy concern is the major issue that prevents users from deploying on public clouds. My research focuses on protecting user's privacy in cloud computing. I will present a hardware-based and a migration-based approach to protect user's privacy. The root cause of the privacy problem is current cloud privilege design gives too much power to cloud providers. Once the control virtual machine (installed by cloud providers) is compromised, external adversaries will breach users’ privacy. Malicious cloud administrators are also possible to disclose user’s privacy by abusing the privilege of cloud providers. Thus, I develop two cloud architectures – MyCloud and MyCloud SEP to protect user’s privacy based on hardware virtualization technology. I eliminate the privilege of cloud providers by moving the control virtual machine (control VM) to the processor’s non-root mode and only keep the privacy protection and performance crucial components in the Trust Computing Base (TCB). In addition, the new cloud platform can provide rich functionalities on resource management and allocation without greatly increasing the TCB size. Besides the attacks to control VM, many external adversaries will compromise one guest VM or directly install a malicious guest VM, then target other legitimate guest VMs based on the connections. Thus, collocating with vulnerable virtual machines, or ”bad neighbors” on the same physical server introduces additional security risks. I develop a migration-based scenario that quantifies the security risk of each VM and generates virtual machine placement to minimize the security risks considering the connections among virtual machines. According to the experiment, our approach can improve the survivability of most VMs.

No description available.

In today's aggressively scaled technology nodes, billions of transistors are packaged into a single integrated circuit. Electronic Design Automation (EDA) tools are needed to automatically assemble the transistors into a functioning system. One of the most important design steps in the physical synthesis is the design of the clock network. The clock network delivers a synchronizing clock signal to each sequential element. The clock signal is required to be delivered meeting timing constraints under variations and in multiple operating modes. Synthesizing such clock networks is becoming increasingly difficult with the complex power management methodologies and severe manufacturing variations. Clock network synthesis is an important problem because it has a direct impact on the functional correctness, the maximum operating frequency, and the overall power consumption of each synchronous integrated circuit. In this dissertation, we proposed synthesis methodologies for robust and reconfigurable clock networks. We have made three contributions to this topic. First, we have proposed a clock network optimization framework that can achieve better timing quality than previous frameworks. Our proposed framework improves timing quality by reducing the propagation delay on critical paths in a clock network using buffer sizing and layer assignment. Second, we have proposed a clock tree synthesis methodology that integrates the clock tree synthesis with the clock tree optimization. The methodology improves timing quality by avoiding to synthesize clock trees with topologies that are sensitive to variations. Third, we have proposed a clock network that can reconfigure the topology based on the active mode of operation. Lastly, we conclude the dissertation with future research directions.

For decades, innovations to surmount the processor versus memory gap and move beyond conventional von Neumann architectures continue to be sought and explored. Recent machine learning models still expend orders of magnitude more time and energy to access data in memory in addition to merely performing the computation itself. This phenomenon referred to as a memory-wall bottleneck, is addressed herein via a completely fresh perspective on logic and memory technology design. The specific solutions developed in this dissertation focus on utilizing intrinsic switching behaviors of embedded MRAM devices to design cross-layer and energy-efficient Compute-in-Memory (CiM) architectures, accelerate the computationally-intensive operations in various Artificial Neural Networks (ANNs), achieve higher density and reduce the power consumption as crucial requirements in future Internet of Things (IoT) devices. The first cross-layer platform developed herein is an Approximate Generative Adversarial Network (ApGAN) designed to accelerate the Generative Adversarial Networks from both algorithm and hardware implementation perspectives. In addition to binarizing the weights, further reduction in storage and computation resources is achieved by leveraging an in-memory addition scheme. Moreover, a memristor-based CiM accelerator for ApGAN is developed. The second design is a biologically-inspired memory architecture. The Short-Term Memory and Long-Term Memory features in biology are realized in hardware via a beyond-CMOS-based learning approach derived from the repeated input information and retrieval of the encoded data. The third cross-layer architecture is a programmable energy-efficient hardware implementation for Recurrent Neural Network with ultra-low power, area-efficient spin-based activation functions. A novel CiM architecture is proposed to leverage data-level parallelism during the evaluation phase. Specifically, we employ an MRAM-based Adjustable Probabilistic Activation Function (APAF) via a low-power tunable activation mechanism, providing adjustable accuracy levels to mimic ideal sigmoid and tanh thresholding along with a matching algorithm to regulate neuronal properties. Finally, the APAF design is utilized in the Long Short-Term Memory (LSTM) network to evaluate the network performance using binary and non-binary activation functions. The simulation results indicate up to 74.5 x 215; energy-efficiency, 35-fold speedup and ~11x area reduction compared with the similar baseline designs. These can form basis for future post-CMOS based non-Von Neumann architectures suitable for intermittently powered energy harvesting devices capable of pushing intelligence towards the edge of computing network.

REpresentational State Transfer or REST is the software architecture style most commonly used for Web Application Programming Interfaces (APIs) and was first defined in 2000 by Roy Thomas Fielding in his PhD dissertation Styles and the Design of Network-based Software Architectures and became a standard for the design of the early World Wide Web and Web-based software. The REST standard continues to be influential in the design of Web systems today, however, it was defined over 15 years ago when the Web was still in its infancy. This paper analyzes REST as it was originally defined by Fielding in 2000 and investigates the validity of its original principles in the modern Internet and Web APIs by sampling a number of prominent APIs and their use of REST. REST definitely has drawbacks for certain types of APIs as evidenced by deviations in the majority of sampled APIs. It is not popular with services that are difficult to represent in REST's resource model. However, REST’s popularity has not noticeably decreased since it was defined rather it has most likely increased. Additionally, each use case that is unsupported by REST goes against some REST constraints that crucial in other areas of it implementation. In conclusion, RESTful properties were not only relevant in the late 1990s and early 2000s but continue to be relevant today as evidenced by its continued widespread use by reputable Web APIs.

The current trend toward chip multiprocessor architectures has placed great pressure on programmers and compilers to generate thread-parallel programs. Improved execution performance can no longer be obtained via traditional single-thread instruction level parallelism (ILP), but, instead, via multithreaded execution. One notable technique that facilitates the extraction of parallel threads from sequential applications is thread-level speculation (TLS). This technique allows programmers/compilers to generate threads without checking for inter-thread data and control dependences, which are then transparently enforced by the hardware. Most prior work on TLS has concentrated on thread selection and mechanisms to efficiently support the main TLS operations, such as squashes, data versioning, and commits. This thesis seeks to enhance TLS functionality by combining it with other speculative multithreaded execution models. The main idea is that TLS already requires extensive hardware support, which when slightly augmented can accommodate other speculative multithreaded techniques. Recognizing that for different applications, or even program phases, the application bottlenecks may be different, it is reasonable to assume that the more versatile a system is, the more efficiently it will be able to execute the given program. As mentioned above, generating thread-parallel programs is hard and TLS has been suggested as an execution model that can speculatively exploit thread-level parallelism (TLP) even when thread independence cannot be guaranteed by the programmer/ compiler. Alternatively, the helper threads (HT) execution model has been proposed where subordinate threads are executed in parallel with a main thread in order to improve the execution efficiency (i.e., ILP) of the latter. Yet another execution model, runahead execution (RA), has also been proposed where subordinate versions of the main thread are dynamically created especially to cope with long-latency operations, again with the aim of improving the execution efficiency of the main thread (ILP). Each one of these multithreaded execution models works best for different applications and application phases. We combine these three models into a single execution model and single hardware infrastructure such that the system can dynamically adapt to find the most appropriate multithreaded execution model. More specifically, TLS is favored whenever successful parallel execution of instructions in multiple threads (i.e., TLP) is possible and the system can seamlessly transition at run-time to the other models otherwise. In order to understand the tradeoffs involved, we also develop a performance model that allows one to quantitatively attribute overall performance gains to either TLP or ILP in such combined multithreaded execution model. Experimental results show that our combined execution model achieves speedups of up to 41.2%, with an average of 10.2%, over an existing state-of-the-art TLS system and speedups of up to 35.2%, with an average of 18.3%, over a flavor of runahead execution for a subset of the SPEC2000 Integer benchmark suite. We then investigate how a common ILP-enhancingmicroarchitectural feature, namely branch prediction, interacts with TLS.We show that branch prediction for TLS is even more important than it is for single core machines. Unfortunately, branch prediction for TLS systems is also inherently harder. Code partitioning and re-executions of squashed threads pollute the branch history making it harder for predictors to be accurate. We thus propose to augment the hardware, so as to accommodate Multi-Path (MP) execution within the existing TLS protocol. Under the MP execution model, all paths following a number of hard-to-predict conditional branches are followed. MP execution thus, removes branches that would have been otherwise mispredicted helping in this way the processor to exploit more ILP. We show that with only minimal hardware support, one can combine these two execution models into a unified one, which can achieve far better performance than both TLS and MP execution. Experimental results show that our combied execution model achieves speedups of up to 20.1%, with an average of 8.8%, over an existing state-of-the-art TLS system and speedups of up to 125%, with an average of 29.0%, when compared with multi-path execution for a subset of the SPEC2000 Integer benchmark suite. Finally, Since systems that support speculative multithreading usually treat all threads equally, they are energy-inefficient. This inefficiency stems from the fact that speculation occasionally fails and, thus, power is spent on threads that will have to be discarded. We propose a profitability-based power allocation scheme, where we “steal” power from non-profitable threads and use it to speed up more useful ones. We evaluate our techniques for a state-of-the-art TLS system and show that, with minimalhardware support, we achieve improvements in ED of up to 25.5% with an average of 18.9%, for a subset of the SPEC 2000 Integer benchmark suite.

Many optimisations in modern compilers have been traditionally based around using analysis to examine certain aspects of the code; the compiler heuristics then make a decision based on this information as to what to optimise, where to optimise and to what extent to optimise. The exact contents of these heuristics have been carefully tuned by experts, using their experience, as well as analytical tools, to produce solid performance. This work proposes an alternative approach – that of using proper statistical analysis to drive these optimisation goals instead of human intuition, through the use of machine learning. This work shows how, by using a probabilistic search of the optimisation space, we can achieve a significant speedup over the baseline compiler with the highest optimisation settings, on a number of different processor architectures. Additionally, there follows a further methodology for speeding up this search by being able to transfer our knowledge of one program to another. This thesis shows that, as is the case in many other domains, programs can be successfully represented by program features, which can then be used to gauge their similarity and thus the applicability of previously learned off-line knowledge. Employing this method, we are able to gain the same results in terms of performance, reducing the time taken by an order of magnitude. Finally, it is demonstrated how statistical analysis of programs allows us to learn additional important optimisation information, purely by examining the features alone. By incorporating this additional information into our model, we show how good results can be achieved in just one compilation. This work is tested on real hardware, for both the embedded and general purpose domain, showing its wide applicability.

Very often when we are looking to buy new IT equipment in an online store, we face the problem that certain parts of our order are not compatible with others or sometimes one part needs additional components. From another point of view in this process, when an online store owner wants to manage the products available in stock, assign prices, set conditions to make an order, or manage customer information, he or she must often rely on information from different systems, physical files, or other sources. EpicConfigurator simplifies and solves the issues mentioned above. EpicConfigurator makes it easy for User Customers to configure computer products by making the process of product selection more straightforward. It can actively gather customer requirements and map them to a set of products and service options. These capabilities will guide users towards an optimal solution for their needs. EpicConfigurator also allows User Customers to keep track and edit saved product configurations. This system also includes a user administrator perspective that allows Store Owners to act as User Admins helping them to manage and load new products, set configuration rules for products and manage all users. Following open source technologies, EpicConfigurator is an application easy to enhance, expand and integrate with newer technologies. This is a configurator tool and does not provide any purchasing feature. To purchase, the configuration results should be provided to the local reseller or sales representative to get an official quote.

This project focuses on applying Extract, Transform and Load (ETL) operations on the relational data exchanged via emails. An Email is an important form of communication by both personal and corporate means as it enables reliable and quick exchange. Many useful files are shared as a form of attachments which contains transactional/ relational data. This tool allows a user to write the filter conditions and lookup conditions on attachments; define the attribute map for attachments to the database table. The Data Cleansing for each attribute can be performed writing rules and their matching state. A user can add custom functions for the data transformation. The aggregation of the data is done in the form of reports after the operation of data loading into the database is complete. The tool needs one-time setup per file template and its automated from that point.