High performance for numerical linear algebra often comes at the expense of stability. Computing the LU decomposition of a matrix via Gaussian Elimination can be organized so that the computation involves regular and efficient data access. However, maintaining numerical stability via partial pivoting involves row interchanges that lead to inefficient data access patterns.

关键词：数据布局；高斯消元；有效通信

查看摘要 索取原文[17页]

There is an entire ecosystem of tools, techniques, and processes designed to improve software security by preventing, nding, mitigating, and/or eliminating software vulnerabilities. Software vendors have this entire ecosystem to choose from during each phase of the software development lifecycle, which begins when someone identi es a software need, ends when the software vendor decides to halt support for the software, and includes everything in between. Unfortunately, guidance regarding which of these tools to choose is often non-existent or based solely on anecdotal evidence. In this dissertation, we present three studies to demonstrate that empirical studies can be used to enhance our understanding of the e ectiveness of various tools and techniques intended to improve software security.

关键词：软件安全；软件漏洞；信息安全

查看摘要 索取原文[102页]

In this work, we used a high accuracy synchrotron-based reflectometer to experimentally determine the effects of angular bandwidth limitations on high- NA EUV mask performance. We collected the scatterometry data of both the mask blank and absorber field, as well as mask pattern diffraction performance as a function of illumination angle, scatter angle, and wavelength. Gratings down to 44 nm half pitch on mask, up to 16° angle of incidence (AOI), and wavelength ranging from 13.3 to 13.7 nm were considered. Rigorous Coupled- Wave Analysis (RCWA) was used to model scatterometry results which were compared with measurement. The experimental measurements on a mask with a multilayer reflectivity of over 60% at 13.5 nm wavelength that peaked about 10° showed that computing the large area reflectivity as a function of wavelength and incident angle from 0 to 14° resulted in root mean square errors in reflectivity unacceptably as high as 13% and 0.8% of the incident beam for the multilayer and absorber respectively. This dropped to 5% and 0.7% respectively when interdiffusion and wavelength-dependent refractive indices were taken into account. Calibration by fitting to the measured data reduced the errors to 0.8% and 0.08% respectively.

关键词：带宽限制；纳米波长；函数

查看摘要 索取原文[19页]

This document introduces the syntax of BLOG, a probabilistic programming language, for describing random variables and their probabilistic dependencies. BLOG defines probabilistic generative models over first-order structures. For example, all Bayesian networks can be easily described by BLOG. BLOG has the following features: (a) it employs open-universe semantics; (b) it can describe relational uncertainty; (c) it can handle identity uncertainty; and (d) it is empowered by first-order logic. The syntax as described in this document corresponds to BLOG version 0.6. The current version represents a significant redesign and extension to previous versions of BLOG, based on the principles of usability and implementation efficiency.

关键词：博客；语言；语法

查看摘要 索取原文[21页]

Maximum constraint satisfaction problem (Max-CSP) is a rich class of combinatorial optimization problems. In this dissertation, we show optimal (up to a constant factor) NPhardness for maximum constraint satisfaction problem with k variables per constraint (Max- k-CSP), whenever k is larger than the domain size. This follows from our main result concerningCSPs given by a predicate: a CSP is approximation resistant if its predicate containsa subgroup that is balanced pairwise independent. Our main result is related to previous works conditioned on the Unique-Games Conjecture and integrality gaps in sum-of squares semide nite programming hierarchies.

关键词：最大约束满意度问题；组合最优问题；编程

查看摘要 索取原文[57页]

Communication, i.e., moving data, between levels of a memory hierarchy or between parallel processors on a network, can greatly dominate the cost of computation, so algorithms that minimize communication can run much faster (and use less energy) than algorithms that do not. Motivated by this, attainable communication lower bounds were established in [12, 13, 4] for a variety of algorithms including matrix computations.The resultapplies to recursive programs, irregular iteration spaces, sparse matrices, and other data structures as long asthe computation can be logically mapped to loops and indexed data structure accesses. We also discuss whenoptimal algorithms exist that attain the lower bounds; this leads to new asymptotically faster algorithms forseveral problems.

关键词：通讯；最优算法；程序；最小通信；矩阵乘法

查看摘要 索取原文[45页]

This thesis mainly explores two fully integrated terahertz transceivers for sensing and communication applications in well matured 0.13 μm BiCMOS and 65 nm digital CMOS technology. Since antenna size shrinks quadratically as radiation frequency increases for a given gain, on-chip antennas have great potential in terahertz range by eliminating packaging issues for cost-effective, compact terahertz transceivers.

关键词：传感和通信；硅设备；太赫兹收发器

查看摘要 索取原文[134页]

In this paper we introduce CARRQR, a communication avoiding rank revealing QR factorization with tournament pivoting. We show that CARRQR reveals the numerical rank of a matrix in an analogous way to QR factorization with column pivoting (QRCP). Although the upper bound of a quantity involved in the characterization of a rank revealing factorization is worse for CARRQR than for QRCP, our numerical experiments on a set of challenging matrices show that this upper bound is very pessimistic, and CARRQR is an e ective tool in revealing the rank in practical problems.Our main motivation for introducing CARRQR is that it minimizes data transfer, modulo poly-logarithmic factors, on both sequential and parallel machines, while previous factorizations as QRCP are communication sub-optimal and require asymptotically more communication than CARRQR.Hence CARRQR is expected to have a better performance on current and future computers, where commmunication is a major bottleneck that highly impacts the performance of an algorithm.

关键词：数据传输；算法；QR；CARRQR；数值等级

查看摘要 索取原文[42页]

In this work, we present a succinct derivation for the Square-Root model based on an explicit model from optimal control theory. Our derivation is intuitive and exact, makes fewer assumptions, and requires far fewer steps than the two-submovement derivation presented in Meyer et al. [MAK+88]. To compare the Square-Root model with statistical signi cance, we performed two extensive experiments with homogeneous and heterogeneous targets that appear in sequence on a plane. Later, we extend the two-parameter model to a more accurate three-parameter that increases the accuracy of the model over the two-parameter formulation. The succinct and intuitive derivation and new experimental results may enhance the appeal of the Square-Root model for design of systems and interfaces with heterogeneous targets.

关键词：平方根模型；异构系统；接口

查看摘要 索取原文[66页]

Cyclops (cyclic-operations) Tensor Framework (CTF) 1 is a distributed library for tensor contractions. CTF aims to scale high-dimensional tensor contractions such as those required in the Coupled Cluster (CC) electronic structure method to massively-parallel supercomputers. The framework preserves tensor structure by subdividing tensors cyclically, producing a regular parallel decomposition. An internal virtualization layer provides completely general mapping support while maintaining ideal load balance. The mapping framework decides on the best mapping for each tensor contraction at run-time via explicit calculations of memory usage and communication volume. CTF employs a general redistribution kernel, which transposes tensors of any dimension between arbitrary distributed layouts, yet touches each piece of data only once. Sequential symmetric contractions are reduced to matrix multiplication calls via tensor index transpositions and partial unpacking. The user-level interface elegantly expresses arbitrary-dimensional generalized tensor contractions in the form of a domain specific language. We demonstrate performance of CC with single and double excitations on 8192 nodes of Blue Gene/Q and show that CTF outperforms NWChem on Cray XE6 supercomputers for benchmarked systems.

关键词：并行收缩；计算机内存；内核

查看摘要 索取原文[13页]