See attached PDF.

See attached PDF.

Discrete event systems (DESs) are today used to model and analyze a wide variety or real-world systems, such as multiprocessor operatin systems, computer networks, telecommunication networks, but also railway networks of manufacturing systems.

In general, DESs lead to a non-linear description in conventional algebra, which complicates their analysis. However, some DESs can be described as linear using the so-called max-plus algebra. Max-plus algebra is an algebraic structure, which replaces the addition and multiplication operations of conventional algebra with maximization and addition, respectively.

During this projet, the basics of max-plus algebra and its application in scheduling DESs.

Abstract:

Accurate and efficient power modeling techniques are crucial for
both design-time power optimization and runtime on-chip IC man-
agement. In prior research, different types of power modeling solu-
tions have been proposed, optimizing multiple objectives including
accuracy, efficiency, temporal resolution, and automation level,
targeting various power/voltage-related applications. Despite ex-
tensive prior explorations in this topic, new solutions still keep
emerging and achieve state-of-the-art performance. Considering
the increasing complexity and importance of the problem, this pa-
per aims at providing a review of the recent progress in power
modeling, with more focus on promising runtime on-chip power
meter (OPM) development techniques. It also serves as a vehicle for
discussing some general development techniques for the runtime
on-chip power modeling task.

Reference Paper:

Xie, Zhiyao. "Efficient Runtime Power Modeling with On-Chip Power Meters." Proceedings of the 2023 International Symposium on Physical Design. 2023.

Silicon photonics is the leading candidate technology for high-speed and low-energy-consumption networks. Thermal and process variations are the two main challenges of achieving high-reliability photonic networks. Thermal variation is due to the heat issues created by application, floorplan, and environment, while process variation is caused by fabrication variability in the deposition, masking, exposition, etching, and doping. Tuning techniques are then required to overcome the impact of the variations and efficiently stabilize the performance of silicon photonic networks. We extend our previous optical switch integration model, BOSIM, to support the variation and thermal analyses. Based on device properties, we propose indirect feedback tuning (IFT) to simultaneously alleviate thermal and process variations. IFT can improve the BER of silicon photonic networks to 10 -9 under different variation situations. Compared to state-of-the-art techniques, IFT can achieve an up to 1.52 ×10 8 times bit-error-rate improvement and 4.11X better heater energy efficiency. Indirect feedback does not require high-speed optical signal detection, and thus, the circuit design of IFT saves up to 61.4% of the power and 51.2% of the area compared to state-of-the-art designs.

Quantum computing (QC) is emerging as a new computing resource that could be superior to conventional computing (CC) for certain classes of optimization problems. However, in principle QC can only solve unconstrained binary programming problems, while mixed-integer linear programming (MIP) is of most interest in practice. We attempt to bridge the gap between the capability of QC and real-world applications by developing a new approach for MIP. The idea is decomposing the MIP into binary programming and linear programming (LP) problems, which are respectively solved by QC and conventional computing. We formalize a decomposition approach that ensures that with a sufficient number of back and forth iterations, the algorithm can reach the optimal solution of the original MIP problem. The algorithm is tested on a 2000Q D-Wave quantum processing units (QPU) and is shown to be effective for small-scaled test cases.

Progressive technology scaling makes computing systems more susceptible to soft errors. Soft errors might manifest as silent data corruption (SDC) where a fault propagates to in a way through the computing system altering the output without any detection. Usually fault injection analysis (FIA) is used to determine a system's susceptibility to such faults in the form of SDC rate. Another approach is to estimate the SDC probability through prediction which heavily deploy machine learning based techniques.

High-level synthesis (HLS) uses advanced automated toolchains with optimization algorithms to achieve shorter development cost for complex designs.
These optimization algorithms are for the HLS tools' backend stages, e.g., allocation, scheduling, and binding, and they are highly optimized for resources/latency constraints. Current HLS tools are unaware of a designs' security assets, such that their algorithms not always suitable for handling constraints to the design imposed by those security assets.

Exploring the scheduling methods used when deploying multiple
inference graphs/tasks onto a single, ideally heterogeneous, platform

Looking into currently used heuristic methods for finding
mappings from network inference tasks to hardware

The goal of this topic is to give an insight in how quantum algorithms can support in solving classical EDA problems, like logic function minimization.

Reference Paper:

GAO, Peng, et al. Novel quantum algorithms to minimize switching functions based on graph partitions. Cmc-Computers Materials & Continua, 2021, 70. Jg., Nr. 3, S. 4545.

Abstract:

After Google reported its realization of quantum supremacy, Solving the classical problems with quantum computing is becoming a valuable research topic. Switching function minimization is an important problem in Electronic Design Automation (EDA) and logic synthesis, most of the solutions are based on heuristic algorithms with a classical computer, it is a good practice to solve this problem with a quantum processer. In this paper, we introduce a new hybrid classic quantum algorithm using Grover’s algorithm and symmetric functions to minimize small Disjoint Sum of Product (DSOP) and Sum of Product (SOP) for Boolean switching functions. Our method is based on graph partitions for arbitrary graphs to regular graphs, which can
be solved by a Grover-based quantum searching algorithm we proposed. The Oracle for this quantum algorithm is built from Boolean symmetric functions and implemented with Lattice diagrams. It is shown analytically and verified
by simulations on a quantum simulator that our methods can find all solutions to these problems.

One of the most common approaches in optimization is to make use of first and second derivatives, in order to find a minimum of a target function. In many cases though, this is not a viable option, as derivatives might not be available, or the function might not be differentiable at all.
For such problems, we need algorithms, that work without derivatives. This can be achieved for example using finite differences or interpolation.
One important algorithm family are the algorithms NEWUOA and BOBYQA by M. J. D. Powell.
The goal of this seminar is to gather works, that evaluate the performance of those algorithms. Furthermore, we want to create a performance matrix that puts Powell’s algorithms into relation with traditional algorithms over a range of different optimization problems.

Paper for BOBYQA (Has not to be read enirely!):
www.damtp.cam.ac.uk/user/na/NA_papers/NA2009_06.pdf

Knowledge in optimization and basic linear algebra is recommended.

Abstract— Antenna problem is a phenomenon of plasma induced gate oxide degradation. It directly affects manufacturability of VLSI circuits, especially in deep-submicron technology using high density plasma. Diode insertion is a very effective way to solve this problem Ideally diodes are inserted directly under the wires that violate antenna rules. But in today's high-density VLSI layouts, there is simply not enough room for "under-the-wire" diode insertion for all wires. Thus it is necessary to insert many diodes at legal "off-wire" locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously only simple heuristic algorithms were available for this diode insertion and routing problem. In this paper we show that the diode insertion and routing problem for an arbitrary given number of routing layers can be optimally solved in polynomial time. Our algorithm guarantees to find a feasible diode insertion and routing solution whenever one exists. Moreover we can guarantee to find a feasible solution to minimize a cost function of the form /spl alpha/ /spl middot/ L + /spl beta/ /spl middot/ N where L is the total length of extension wires and N is the total number of Was on the extension wires. Experimental results show that our algorithm is very efficient.

Abstract— This paper presents a general multi-layer area router based on a novel grid construction scheme. The grid construction scheme produces more wiring tracks than the normal uniform grid scheme and accounts for differing design rules of the layers involved. Initial routing performed on the varying capacity grid is followed by a layer assignment stage. Routing completion is ensured by iterating local and global modifications in the layer assignment stage. Our router has been incorporated into the Custom Cell Synthesis project at MCC and has shown improved results for cell synthesis problems when compared with the router Mighty which was used in earlier versions of the project.

There is a global unmet need for rapid and cost-effective prognostic and diagnostic tools that can be used at the bedside or in the doctor’s office to reduce the impact of serious disease. Many cancers are diagnosed late, leading to costly treatment and reduced life expectancy. With prostate cancer, the absence of a reliable test has inhibited the adoption of screening programs. We report a microelectronic point-of-care metabolite biomarker measurement platform and use it for prostate cancer detection. The platform, using an array of photodetectors configured to operate with targeted, multiplexed, colorimetric assays confined in monolithically integrated passive microfluidic channels, completes a combined assay of 4 metabolites in a drop of human plasma in under 2 min. A preliminary clinical study using L-amino acids, glutamate, choline, and sarcosine was used to train a cross-validated random forest algorithm. The system demonstrated sensitivity to prostate cancer of 94% with a specificity of 70% and an area under the curve of 0.78. The technology can implement many similar assay panels and hence has the potential to revolutionize low-cost, rapid, point-of-care testing.

Dot and ripple nanopatterns on Si surfaces with defined symmetry and characteristic dot spacings of 50–70 nm were created by 1 keV Ar ion irradiation at normal incidence and simultaneous co-deposition of Fe atoms at grazing incidence. Fe was continuously supplied from different sputter targets surrounding the Si substrate, leading to a steady-state Fe content in the near-surface region of the substrates. The pattern formation is self-organized, most probably caused by ion-induced phase separation. Patterns were analyzed with atomic force microscopy and the Fe content in the irradiated layer was measured with Rutherford backscattering. The symmetries of the produced patterns are isotropic, four-fold symmetric, three-fold symmetric and various types of two-fold symmetric patterns, depending on the geometrical arrangement of the sputter targets. Pattern formation was studied for a steady-state coverage of Fe between 0.5 and 3.3 × 1015 Fe cm−2. The threshold coverage for the onset of pattern formation is about 0.5–1 × 1015 Fe cm−2. The coherence length of the patterns is comparable to the average dot spacing. Nevertheless, the autocorrelation analysis reveals a residual long-range periodicity of some patterns. The dot spacing can be adjusted between about 20 nm and several hundred nm depending on the ion species and ion energy.

Because of the increasing dominance of interconnect issues in advanced IC technology, placement has become a critical step in the IC design flow. To get accurate interconnect information during the placement process, it is desirable to incorporate global routing into it. However, previous global routers are computationally expensive. It is impractical to perform global routing repeatedly during placement.

In this paper, we present an extremely fast and high-quality global router called FastRoute. In traditional global routing approaches, congestion is not considered during Steiner tree construction. So they have to rely on the time-consuming maze routing technique to eliminate routing congestion. Different from traditional approaches, we proposed a congestion-driven Steiner tree topology generation technique and an edge shifting technique to determine the good Steiner tree topologies and Steiner node positions. Based on the congestion-driven Steiner trees, we only need to apply maze routing to a small percentage of the two-pin nets once to obtain high quality global routing solutions. We also proposed a new cost function based on logistic function to direct the maze routing.