Browsing by Subject "Efficiency"

Scarce resources are oftentimes allocated in a centralized clearinghouse based on individuals' reported preferences and objects' priorities. Prominent examples include public school assignment, allocation of dormitories, office spaces, allocation of organs to patients waiting for organ transplantation, and most recently, administration of COVID-19 vaccines. This dissertation develops and studies equitable and efficient allocation mechanisms without monetary transfers.

Chapter 2, which is a joint work with Atila Abdulkadiroglu, addresses the trade-off between efficiency and respecting priorities. We show that finding an efficient allocation that minimizes priority violations is an NP-hard problem when objects have weak priority rankings. Consequently, we focus on finding priority violations minimal mechanisms in subsets of efficient mechanisms, namely, sequential dictatorships and hierarchical exchange rules. Both classes are widely studied in the literature and applied in real-life resource allocation problems. We provide polynomial-time mechanisms that minimize priority violations in each of these classes. %Additionally, we study the possibility of minimizing priority violations in the entire class of efficient and strategyproof mechansims. We show that none of the well-known efficient and strategyproof mechanisms, such as hierarchical exchange rules or trading cycles mechanisms minimize priority violations in that class.

Chapter 3, which is also a joint work with Atila Abdulkadiroglu, studies diversity and distributional objectives in allocation problems. First, we study a single school's problem of choosing a set of applicants to be assigned to the school. We provide an axiomatic characterization of a general class of choice rules where distributional objectives are met through type-specific reserves and quotas. We show that a particular intuitive implementation of a reserves- and quotas-based rule, which we call the regular reserves-and-quotas rule, uniquely minimizes priority violations in this class. Next, we study a general setup with multiple schools. We show that when all schools use the regular reserves-and-quotas rule, the Deferred Acceptance mechanism minimizes priority violations in a large class of mechanisms that satisfy the distributional constraints.

Chapter 4 evaluates the welfare and distributional outcomes of the Deferred Acceptance mechanism in a unified framework with school choice and a housing market. In my model, families' strategically choose where to live before going through a school admission process. I show that when families receive higher priorities at neighborhood schools, the Deferred Acceptance mechanism improves aggregate or average welfare compared to neighborhood assignment. Additionally, under general conditions, the Deferred Acceptance mechanism improves the welfare of lowest-income families, both with and without neighborhood priorities. To the best of my knowledge, my work provides the first theoretical justification for using the Deferred Acceptance mechanism on the grounds of welfare and equity in a general matching model with residential choices.

Emerging technologies, such as resistive random-access memory (ReRAM), have proven their potential in in-memory computing for deep learning applications. My dissertation work focuses on improving the efficiency and robustness of in-memory computing in emerging technologies.

Existing ReRAM-based processing-in-memory (PIM) designs can support the inferencing and the training of neural networks, such as convolutional neural networks and recurrent neural networks. However, these designs suffer from the re-writing procedure for the self-attention calculation. Therefore, I propose an architecture that enables the efficient self-attention mechanism in PIM design. The optimized calculation procedure and finer granularity pipeline design improve efficiency. The contributions lie in enabling feasible and efficient ReRAM-based PIM designs for attention-based models.

Inferencing with ReRAM-based design has one severe problem: the inferencing accuracy can be degraded due to the non-idealities in hardware devices. The robustness of the previous method is not validated under the combination of device stochastic noise. With the proposed hardware-aware training method, the robustness of inferencing accuracy can be improved. Besides, with hardware efficiency and inferencing robustness targets, the multi-objective optimization method is developed to explore the design space and generate high-quality Pareto-optimal design configurations with minimal cost. This work integrates attributes from the design space and the evaluation space and develops efficient hardware-software co-design methods.

Training with ReRAM-based design has one challenging endurance problem due to the frequent weight updates for neural network training. The expectation for endurance management is to decrease the number of weight updates and balance the write accesses. The proposed endurance-aware training method utilizes gradient structure pruning and dynamically structurally adjusts the write probabilities. This method can expand the life cycle for ReRAM during the training process.

In summary, the research above targets realizing efficient self-attention mechanisms and solving accuracy degradation and endurance problems for the inferencing and training processes. Besides, the efforts lie in figuring out the challenging parts of each topic and developing hardware-software co-design considering efficiency and robustness. The developed designs are the potential solutions for the challenging problems of in-memory computing in emerging technologies.

The basic scaling laws that govern both turbomachinery and permanent magnet generator power density are presented. It is shown for turbomachinery, that the power density scales indirectly proportional with the characteristic length of the system. For permanent magnet generators, power density is shown to be scale independent at a constant current density, but scale favorably in reality as a result of the scaling laws of heat dissipation.

The challenges that have affected micro-turbogenerators in the past are presented. Two of the most important challenges are the efficiency of micro-turbomachinery and the power transfer capabilities of micro-generators.

The basic operating principles of turbomachinery are developed with emphasis on the different mechanisms of energy transfer and how the ratio of these mechanisms in a turbine design relates to efficiency. Loss models are developed to quantify entropy creation from tip leakage, trailing edge mixing, and viscous boundary layers over the surface of the blades. The total entropy creation is related to lost work and turbine efficiency. An analysis is done to show turbine efficiency and power density as a function of system parameters such as stage count, RPM, reaction, and size. The practice of multi-staging is shown to not be as beneficial at small scales as it is for large scales. Single stage reaction turbines display the best efficiency and power density, but require much higher angular velocities. It is also shown that for any configuration, there exists a peak power density as a result of competing effects between the scaling laws and viscous losses at small sizes.

The operating principles of generators and power electronics are presented as are the scaling laws for both permanent magnet generators and electro-magnetic induction generators. This analysis shows that permanent magnet generators should have higher power densities at small sizes. The basic concepts of permanent magnet operation and magnetic circuits are explained, allowing the estimation of system voltage as a function of design parameters. The relationship between generator voltage, internal resistance, and load power is determined.

Models are presented for planar micro-generators to determine output voltage,internal resistance, electrical losses, and electromagnetic losses as a function of geometry and key design parameters. A 3 phase multi-layer permanent magnet generator operating at 175,000 RPM with an outer diameter of 1 cm is then designed. The device is shown to operate at an efficiency of 64\%. A second device is designed using improved geometries and system parameters and operates at an efficiency of 93%.

Lastly, an ejector driven turbogenerator is designed, built, and tested. A thermodynamic cycle for the system is presented in order to estimate system efficiency as a function of design parameters. The turbo-generator was run at 27,360 RPM and demonstrated a DC power output of 7.5 mW.

Recently, deep neural network (DNN) models have shown beyond-human performance in multiple tasks. However, DNN models still exhibit outstanding issues on efficiency and robustness that hinder their applications in the real world. For efficiency, modern DNN architectures often contain millions of parameters and require billions of operations to process a single input, making it hard to deploy these models on mobile and edge devices. For robustness, recent research on adversarial attack shows that most DNN models can be misled by tiny perturbations added on the input, leaving doubts on the robustness of DNNs in security-related tasks. To tackle these challenges, this dissertation aims to advance and incorporate techniques from both fields of DNN efficiency and robustness, leading towards efficient and robust DNN models.

My research first advances model compression techniques including pruning, low-rank decomposition, and quantization to push the boundary of efficiency-accuracy tradeoff in DNN models. For pruning, I propose DeepHoyer, a new sparsity-inducing regularizer that is both scale-invariant and differentiable. For decomposition, I apply the sparsity-inducing regularizer on the decomposed singular values of DNN layers, together with an orthogonality regularization on the singular vectors. For quantization, I propose BSQ to achieve optimal mixed-precision quantization scheme by exploring bit-level sparsity, mitigating the costly search through the large design space of quantization precision. All these works successfully achieve DNN models that are both more accurate and more efficient than state-of-the-art methods. For robustness improvement, I change the previously undesired accuracy-robustness tradeoff of a single DNN model into an efficiency-robustness tradeoff of a DNN ensemble, without hurting the clean accuracy. The method, DVERGE, combines a vulnerability diversification objective and previously investigated model compression techniques, leading to an efficient ensemble whose robustness increases with the number of sub-models. Finally, I propose to unify the pursuit of accuracy and efficiency as an optimization towards robustness against weight perturbation. Thus, I introduce Hessian-Enhanced Robust Optimization to achieve highly accurate model that are robust to post-training quantization. The accomplish of my dissertation research paves way towards controlling the tradeoff between accuracy, efficiency and robustness, and leads to efficient and robust DNN models.