Dense, efficient chip-to-chip communication at the extremes of computing

The scalability of CMOS technology has driven computation into a diverse range of applications across the power consumption, performance and size spectra. Communication is a necessary adjunct to computation, and whether this is to push data from node-to-node in a high-performance computing cluster or from the receiver of wireless link to a neural stimulator in a biomedical implant, interconnect can take up a significant portion of the overall system power budget. Although a single interconnect methodology cannot address such a broad range of systems efficiently, there are a number of key design concepts that enable good interconnect design in the age of highly-scaled CMOS: an emphasis on highly-digital approaches to solving ‘analog’ problems, hardware sharing between links as well as between different functions (such as equalization and synchronization) in the same link, and adaptive hardware that changes its operating parameters to mitigate not only variation in the fabrication of the link, but also link conditions that change over time. These concepts are demonstrated through the use of two design examples, at the extremes of the power and performance spectra.

A novel all-digital clock and data recovery technique for high-performance, high density interconnect has been developed. Two independently adjustable clock phases are generated from a delay line calibrated to 2 UI. One clock phase is placed in the middle of the eye to recover the data, while the other is swept across the delay line. The samples produced by the two clocks are compared to generate eye information, which is used to determine the best phase for data recovery. The functions of the two clocks are swapped after the data phase is updated; this ping-pong action allows an infinite delay range without the use of a PLL or DLL. The scheme's generalized sampling and retiming architecture is used in a sharing technique that saves power and area in high-density interconnect. The eye information generated is also useful for tuning an adaptive equalizer, circumventing the need for dedicated adaptation hardware.

On the other side of the performance/power spectra, a capacitive proximity interconnect has been developed to support 3D integration of biomedical implants. In order to integrate more functionality while staying within size limits, implant electronics can be embedded onto a foldable parylene (‘origami’) substrate. Many of the ICs in an origami implant will be placed face-to-face with each other, so wireless proximity interconnect can be used to increase communication density while decreasing implant size, as well as facilitate a modular approach to implant design, where pre-fabricated parylene-and-IC modules are assembled together on-demand to make custom implants. Such an interconnect needs to be able to sense and adapt to changes in alignment. The proposed array uses a TDC-like structure to realize both communication and alignment sensing within the same set of plates, increasing communication density and eliminating the need to infer link quality from a separate alignment block. In order to distinguish the communication plates from the nearby ground plane, a stimulus is applied to the transmitter plate, which is rectified at the receiver to bias a delay generation block. This delay is in turn converted into a digital word using a TDC, providing alignment information.

Pattern formation during Caenorhabditis Elegans vulval development

Pattern formation during animal development involves at least three processes: establishment of the competence of precursor cells to respond to intercellular signals, formation of a pattern of different cell fates adopted by precursor cells, and execution of the cell fate by generating a pattern of distinct descendants from precursor cells. I have analyzed the fundamental mechanisms of pattern formation by studying the development of Caenorhabditis elegans vulva.

In C. elegans, six multipotential vulval precursor cells (VPCs) are competent to respond to an inductive signal LIN-3 (EGF) mediated by LET- 23 (RTK) and a lateral signal via LIN-12 (Notch) to form a fixed pattern of 3°-3°-2°-1°-2°-3°. Results from expressing LIN-3 as a function of time in animals lacking endogenous LIN-3 indicate that both VPCs and VPC daughters are competent to respond to LIN-3. Although the daughters of VPCs specified to be 2° or 3° can be redirected to adopt the 1°fate, the decision to adopt the 1° fate is irreversible. Coupling of VPC competence to cell cycle progression reveals that VPC competence may be periodic during each cell cycle and involve LIN-39 (HOM-C). These mechanisms are essential to ensure a bias towards the 1° fate, while preventing an excessive response.

After adopting the 1° fate, the VPC executes its fate by dividing three rounds to form a fixed pattern of four inner vulF and four outer vulE descendants. These two types of descendants can be distinguished by a molecular marker zmp-1::GFP. A short-range signal from the anchor cell (AC), along with signaling between the inner and outer 1° VPC descendants and intrinsic polarity of 1° VPC daughters, patterns the 1° lineage. The Ras and the Wnt signaling pathways may be involved in these mechanisms.

The temporal expression pattern of egl-17::GFP, another marker ofthe 1° fate, correlates with three different steps of 1° fate execution: the commitment to the 1° fate, as well as later steps before and after establishment of the uterine-vulval connection. Six transcription factors, including LIN-1(ETS), LIN-39 (HOM-C), LIN-11(LIM), LIN-29 (zinc finger), COG-1 (homeobox) and EGL-38 (PAX2/5/8), are involved in different steps during 1° fate execution.

Experimental and theoretical studies of Notch signaling-mediated spatial pattern

Notch signaling acts in many diverse developmental spatial patterning processes. To better understand why this particular pathway is employed where it is and how downstream feedbacks interact with the signaling system to drive patterning, we have pursued three aims: (i) to quantitatively measure the Notch system's signal input/output (I/O) relationship in cell culture, (ii) to use the quantitative I/O relationship to computationally predict patterning outcomes of downstream feedbacks, and (iii) to reconstitute a Notch-mediated lateral induction feedback (in which Notch signaling upregulates the expression of Delta) in cell culture. The quantitative Notch I/O relationship revealed that in addition to the trans-activation between Notch and Delta on neighboring cells there is also a strong, mutual cis-inactivation between Notch and Delta on the same cell. This feature tends to amplify small differences between cells. Incorporating our improved understanding of the signaling system into simulations of different types of downstream feedbacks and boundary conditions lent us several insights into their function. The Notch system converts a shallow gradient of Delta expression into a sharp band of Notch signaling without any sort of feedback at all, in a system motivated by the Drosophila wing vein. It also improves the robustness of lateral inhibition patterning, where signal downregulates ligand expression, by removing the requirement for explicit cooperativity in the feedback and permitting an exceptionally simple mechanism for the pattern. When coupled to a downstream lateral induction feedback, the Notch system supports the propagation of a signaling front across a tissue to convert a large area from one state to another with only a local source of initial stimulation. It is also capable of converting a slowly-varying gradient in parameters into a sharp delineation between high- and low-ligand populations of cells, a pattern reminiscent of smooth muscle specification around artery walls. Finally, by implementing a version of the lateral induction feedback architecture modified with the addition of an autoregulatory positive feedback loop, we were able to generate cells that produce enough cis ligand when stimulated by trans ligand to themselves transmit signal to neighboring cells, which is the hallmark of lateral induction.

Information-theoretic Studies and Capacity Bounds: Group Network Codes and Energy Harvesting Communication Systems

Network information theory and channels with memory are two important but difficult frontiers of information theory. In this two-parted dissertation, we study these two areas, each comprising one part. For the first area we study the so-called entropy vectors via finite group theory, and the network codes constructed from finite groups. In particular, we identify the smallest finite group that violates the Ingleton inequality, an inequality respected by all linear network codes, but not satisfied by all entropy vectors. Based on the analysis of this group we generalize it to several families of Ingleton-violating groups, which may be used to design good network codes. Regarding that aspect, we study the network codes constructed with finite groups, and especially show that linear network codes are embedded in the group network codes constructed with these Ingleton-violating families. Furthermore, such codes are strictly more powerful than linear network codes, as they are able to violate the Ingleton inequality while linear network codes cannot. For the second area, we study the impact of memory to the channel capacity through a novel communication system: the energy harvesting channel. Different from traditional communication systems, the transmitter of an energy harvesting channel is powered by an exogenous energy harvesting device and a finite-sized battery. As a consequence, each time the system can only transmit a symbol whose energy consumption is no more than the energy currently available. This new type of power supply introduces an unprecedented input constraint for the channel, which is random, instantaneous, and has memory. Furthermore, naturally, the energy harvesting process is observed causally at the transmitter, but no such information is provided to the receiver. Both of these features pose great challenges for the analysis of the channel capacity. In this work we use techniques from channels with side information, and finite state channels, to obtain lower and upper bounds of the energy harvesting channel. In particular, we study the stationarity and ergodicity conditions of a surrogate channel to compute and optimize the achievable rates for the original channel. In addition, for practical code design of the system we study the pairwise error probabilities of the input sequences.

Feedback communication using orthogonal signals

This research is concerned with block coding for a feedback communication system in which the forward and feedback channels are independently disturbed by additive white Gaussian noise and average power constrained. Two coding schemes are proposed in which the messages to be coded for transmission over the forward channel are realized as a set of orthogonal waveforms. A finite number of forward and feedback transmissions (iterations) per message is made. Information received over the feedback channel is used to modify the waveform transmitted on successive forward iterations in such a way that the expected value of forward signal energy is zero on all iterations after the first. Similarly, information is sent over the feedback channel in such a way that the expected value of feedback signal energy is also zero on all iterations after the first. These schemes are shown to achieve a lower probability of error than the best one-way coding scheme at all rates up to the forward channel capacity, provided only that the feedback channel capacity be greater than the forward channel capacity. These schemes make more efficient use of the available feedback power than existing feedback coding schemes, and therefore require less feedback power to achieve a given error performance.

Steady surface wave pattern in a shear flow

The subject under investigation concerns the steady surface wave patterns created by small concentrated disturbances acting on a non-uniform flow of a heavy fluid. The initial value problem of a point disturbance in a primary flow having an arbitrary velocity distribution (U(y), 0, 0) in a direction parallel to the undisturbed free surface is formulated. A geometric optics method and the classical integral transformation method are employed as two different methods of solution for this problem. Whenever necessary, the special case of linear shear (i.e. U(y) = 1+ϵy)) is chosen for the purpose of facilitating the final integration of the solution.

The asymptotic form of the solution obtained by the method of integral transforms agrees with the leading terms of the solution obtained by geometric optics when the latter is expanded in powers of small ϵ r.

The overall effect of the shear is to confine the wave field on the downstream side of the disturbance to a region which is smaller than the wave region in the case of uniform flows. If U(y) vanishes, and changes sign at a critical plane y = y_cr (e.g. ϵy_cr = -1 for the case of linear shear), then the boundary of this asymmetric wave field approaches this critical vertical plane. On this boundary the wave crests are all perpendicular to the x-axis, indicating that waves are reflected at this boundary.

Inside the wave field, as in the case of a point disturbance in a uniform primary flow, there exist two wave systems. The loci of constant phases (such as the crests or troughs) of these wave systems are not symmetric with respect to the x-axis. The geometric optics method and the integral transform method yield the same result of these loci for the special case of U(y) = U_o(1 + ϵy) and for large Kr (ϵr ˂˂ 1 ˂˂ Kr).

An expression for the variation of the amplitude of the waves in the wave field is obtained by the integral transform method. This is in the form of an expansion in small ϵr. The zeroth order is identical to the expression for the uniform stream case and is thus not applicable near the boundary of the wave region because it becomes infinite in that neighborhood. Throughout this investigation the viscous terms in the equations of motion are neglected, a reasonable assumption which can be justified when the wavelengths of the resulting waves are sufficiently large.

Distributed Control and Optimization for Communication and Power Systems

We are at the cusp of a historic transformation of both communication system and electricity system. This creates challenges as well as opportunities for the study of networked systems. Problems of these systems typically involve a huge number of end points that require intelligent coordination in a distributed manner. In this thesis, we develop models, theories, and scalable distributed optimization and control algorithms to overcome these challenges.

This thesis focuses on two specific areas: multi-path TCP (Transmission Control Protocol) and electricity distribution system operation and control. Multi-path TCP (MP-TCP) is a TCP extension that allows a single data stream to be split across multiple paths. MP-TCP has the potential to greatly improve reliability as well as efficiency of communication devices. We propose a fluid model for a large class of MP-TCP algorithms and identify design criteria that guarantee the existence, uniqueness, and stability of system equilibrium. We clarify how algorithm parameters impact TCP-friendliness, responsiveness, and window oscillation and demonstrate an inevitable tradeoff among these properties. We discuss the implications of these properties on the behavior of existing algorithms and motivate a new algorithm Balia (balanced linked adaptation) which generalizes existing algorithms and strikes a good balance among TCP-friendliness, responsiveness, and window oscillation. We have implemented Balia in the Linux kernel. We use our prototype to compare the new proposed algorithm Balia with existing MP-TCP algorithms.

Our second focus is on designing computationally efficient algorithms for electricity distribution system operation and control. First, we develop efficient algorithms for feeder reconfiguration in distribution networks. The feeder reconfiguration problem chooses the on/off status of the switches in a distribution network in order to minimize a certain cost such as power loss. It is a mixed integer nonlinear program and hence hard to solve. We propose a heuristic algorithm that is based on the recently developed convex relaxation of the optimal power flow problem. The algorithm is efficient and can successfully computes an optimal configuration on all networks that we have tested. Moreover we prove that the algorithm solves the feeder reconfiguration problem optimally under certain conditions. We also propose a more efficient algorithm and it incurs a loss in optimality of less than 3% on the test networks.

Second, we develop efficient distributed algorithms that solve the optimal power flow (OPF) problem on distribution networks. The OPF problem determines a network operating point that minimizes a certain objective such as generation cost or power loss. Traditionally OPF is solved in a centralized manner. With increasing penetration of volatile renewable energy resources in distribution systems, we need faster and distributed solutions for real-time feedback control. This is difficult because power flow equations are nonlinear and kirchhoff's law is global. We propose solutions for both balanced and unbalanced radial distribution networks. They exploit recent results that suggest solving for a globally optimal solution of OPF over a radial network through a second-order cone program (SOCP) or semi-definite program (SDP) relaxation. Our distributed algorithms are based on the alternating direction method of multiplier (ADMM), but unlike standard ADMM-based distributed OPF algorithms that require solving optimization subproblems using iterative methods, the proposed solutions exploit the problem structure that greatly reduce the computation time. Specifically, for balanced networks, our decomposition allows us to derive closed form solutions for these subproblems and it speeds up the convergence by 1000x times in simulations. For unbalanced networks, the subproblems reduce to either closed form solutions or eigenvalue problems whose size remains constant as the network scales up and computation time is reduced by 100x compared with iterative methods.