Parallel bandwidth characteristics calculations for thin avalanche photodiodes on a SGI Origin 2000 supercomputer

An important factor for high-speed optical communication is the availability of ultrafast and low-noise photodetectors. Among the semiconductor photodetectors that are commonly used in today’s long-haul and metro-area fiber-optic systems, avalanche photodiodes (APDs) are often preferred over p-i-n photodiodes due to their internal gain, which significantly improves the receiver sensitivity and alleviates the need for optical pre-amplification. Unfortunately, the random nature of the very process of carrier impact ionization, which generates the gain, is inherently noisy and results in fluctuations not only in the gain but also in the time response. Recently, a theory characterizing the autocorrelation function of APDs has been developed by us which incorporates the dead-space effect, an effect that is very significant in thin, high-performance APDs. The research extends the time-domain analysis of the dead-space multiplication model to compute the autocorrelation function of the APD impulse response. However, the computation requires a large amount of memory space and is very time consuming. In this research, we describe our experiences in parallelizing the code in MPI and OpenMP using CAPTools. Several array partitioning schemes and scheduling policies are implemented and tested. Our results show that the code is scalable up to 64 processors on a SGI Origin 2000 machine and has small average errors.

Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

The numerical simulation of enclosure fires using a Cfd fire field model coupled with a pyrolysis based solid fuel combustion submodel—a first approximation

In this paper, we present some early work concerned with the development of a simple solid fuel combustion model incorporated within a Computational Fluid Dynamics (CFD) framework. The model is intended for use in engineering applications of fire field modeling and represents an extension of this technique to situations involving the combustion of solid cellulosic fuels. A simple solid fuel combustion model consisting of a thermal pyrolysis model, a six flux radiation model and an eddy-dissipation model for gaseous combustion have been developed and implemented within the CFD code CFDS-FLOW3D. The model is briefly described and demonstrated through two applications involving fire spread in a compartment with a plywood lined ceiling. The two scenarios considered involve a fire in an open and closed compartment. The model is shown to be able to qualitatively predict behaviors similar to "flashover"—in the case of the open room—and "backdraft"— in the case of the initially closed room.

On approximate calculations

The ability to undertake approximate calcutations and to get a “rough feel” for data is an important skill which must not be overlooked.

Approximation Algorithms for a Symmetric Quadratic Knapsack Problem and its Scheduling Applications

We consider a knapsack problem to minimize a symmetric quadratic function. We demonstrate that this symmetric quadratic knapsack problem is relevant to two problems of single machine scheduling: the problem of minimizing the weighted sum of the completion times with a single machine non-availability interval under the non-resumable scenario; and the problem of minimizing the total weighted earliness and tardiness with respect to a common small due date. We develop a polynomial-time approximation algorithm that delivers a constant worst-case performance ratio for a special form of the symmetric quadratic knapsack problem. We adapt that algorithm to our scheduling problems and achieve a better performance. For the problems under consideration no fixed-ratio approximation algorithms have been previously known.

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.

An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables

An approximation algorithm for the two-machine flow shop with a single transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.

An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

Approximation results for flow shop scheduling problems with machine availability constraints

This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

Vibrational spectroscopy and DFT calculations of the di-amino acid peptide L-aspartyl-L-glutamic acid in the zwitterionic state

Solid state IR and Raman as well as aqueous solution state Raman spectra are reported for the linear di-amino acid peptide L-aspartyl-L-glutamic acid (L-Asp-L-Glu); the solution state Raman spectrum has also been obtained for the N,O-deuterated derivative. SCF-DFT calculations at the B3-LYP/cc-pVDZ level established that the structure and vibrational spectra of L-Asp-L-Glu can be interpreted using a model of the peptide with ten hydrogen-bonded water molecules, in conjunction with the conductor-like polarizable continuum solvation method. The DFT calculations resulted in the computation of a stable zwitterionic structure, which displays trans-amide conformation. The vibrational spectra were computed at the optimised molecular geometry, enabling normal coordinate analysis, which yielded satisfactory agreement with the experimental IR and Raman data. Computed potential energy distributions of the normal modes provided detailed vibrational assignments.

Vibrational spectroscopy and DFT calculations of di-amino acid cyclic peptides. Part I: cyclo(Gly-Gly), cyclo(L-Ala-L-Ala) and cyclo(L-Ala-Gly) in the solid state and in aqueous solution

Investigations of the vibrational spectra of cyclo(Gly-Gly), cyclo(L-Ala-L-Ala) and cyclo(t-Ala-Gly) are reported. Raman scattering and Fourier transform infrared (FTIR) spectra of solid-state and aqueous protonated samples, as well as their corresponding N-deuterated isotopomers, have been examined. In addition, density functional theory (DFT) (B3-LYP/cc-pVDZ) calculations of molecular structures and their associated vibrational modes were carried out. In each case, the calculated structures of lowest energy for the isolated gas-phase molecules have boat conformations. Assignments have been made for the observed Raman and FTIR vibrational bands of the cyclic di-amino acid peptides (CDAPs) examined. Raman polarization studies of aqueous phase samples are consistent with C-2 and C-1 symmetries for the six-membered rings of cyclo(L-Ala-L-Ala) and cydo(L-Ala-Gly), respectively. There is a good correlation between experimental and calculated vibrational bands for the three CDAPs. These data are in keeping with boat conformations for cydo(L-Ala-L-Ala) and cyclo(L-Ala-Gly) molecules, predicted by the ab initio calculations, in both the solid and aqueous solution states. However, Raman spectroscopic results might infer that cyclo(L-AlaGly) deviates only slightly from planarity in the solid state. The potential energy distributions of the amide I and II modes of a cis-peptide linkage are shown to be significantly different from those of the trans-peptides. For example, deuterium shifts have shown that the cis-amide I vibrations found in cyclo(Gly-Gly), cyclo(L-Ala-L-Ala), and cyclo(L-Ala-Gly) have larger N-H contributions compared to their trans-amide counterparts. Compared to trans-amide II vibrations, cis-amide II vibrations show a considerable decrease in N-H character.

IR/Raman spectroscopy and DFT calculations of cyclic di-amino acid peptides. Part III: comparison of solid state and solution structures of cyclo(L-Ser-L-Ser)

B3-LYP/cc-pVDZ calculations of the gas-phase structure and vibrational spectra of the isolated molecule cyclo(L-Ser-L-Ser), a cyclic di-amino acid peptide (CDAP), were carried out by assuming C-2 symmetry. It is predicted that the minimum-energy structure is a boat conformation for the diketopiperazine (DKP) ring with both L-Beryl side chains being folded slightly above the ring. An additional structure of higher energy (15.16 kJ mol(-1)) has been calculated for a DKP ring with a planar geometry, although in this case two fundamental vibrations have been calculated with imaginary wavenumbers. The reported X-ray crystallographic structure of cyclo(L-Ser-L-Ser), shows that the DKP ring displays a near-planar conformation, with both the two L-Beryl side chains being folded above the ring. It is hypothesized that the crystal packing forces constrain the DKP ring in a planar conformation and it is probable that the lower energy boat conformation may prevail in the aqueous environment. Raman scattering and Fourier-transform infrared (FT-IR) spectra of solid state and aqueous solution samples of cyclo(L-Ser-L-Ser) are reported and discussed. Vibrational band assignments have been made on the basis of comparisons with the calculated vibrational spectra and band wavenumber shifts upon deuteration of labile protons. The experimental Raman and IR results for solid-state samples show characteristic amide I vibrations which are split (Raman:1661 and 1687 cm(-1), IR:1666 and 1680 cm(-1)), possibly due to interactions between molecules in a crystallographic unit cell. The cis amide I band is differentiated by its deuterium shift of ~ 30 cm(-1), which is larger than that previously reported for trans amide I deuterium shifts. A cis amide II mode has been assigned to a Raman band located at 1520 cm(-1). The occurrence of this cis amide II mode at a wavenumber above 1500 cm(-1) concurs with results of previously examined CDAP molecules with low molecular weight substituents on the C-alpha atoms, and is also indicative of a relatively unstrained DKP ring.