Electrical linewidth test structures fabricated in monocrystallinefilms for reference-material applications

The physical widths of reference features incorporated into electrical linewidth test structures patterned in films of monocrystalline silicon have been determined from Kelvin voltage measurements. The films in which the test structures are patterned are electrically insulated from the bulk-silicon substrate by a layer of silicon dioxide provided by SIMOX (Separation by the IMplantation of OXygen) processing. The motivation is to facilitate the development of linewidth reference materials for critical-dimension (CD) metrology-instrument calibration. The selection of the (110) orientation of the starting silicon and the orientation of the structures' features relative to the crystal lattice enable a lattice-plane-selective etch to generate reference-feature properties of rectangular cross section and atomically planar sidewalls. These properties are highly desirable for CD applications in which feature widths are certified with nanometer-level uncertainty for use by a diverse range of CD instruments. End applications include the development and calibration of new generations of CD instruments directed at controlling processes for manufacturing devices having sub-quarter-micrometer features     

Transmission capacity of optical path overhead transfer schemeusing pilot tone for optical path network

Photonic networks based on the optical path concept and wavelength division multiplexing (WDM) technology require unique operation, administration, and maintenance (OAM) functions. In order to realize the required OAM functions, the optical path network must support an effective management information transfer method. The method that superimposes a pilot tone on the optical signal appears very interesting for optical path overhead transfer. The pilot tone transmission capacity is determined by the carrier to noise ratio which depends on the power spectral density of the optical signal. The pilot tone transmission capacity of an optical path network employing WDM technology is elucidated; 4.5 kb/s transmission can be realized when the pilot tone modulation index is set at 3%     

Presupposition failure — A comedy of errors

Presuppositions of utterances are the pieces of information you convey with an utterance no matter whether your utterance is true or not. We first study presupposition in a very simple framework of updating propositional information, with examples of how presuppositions of complex propositional updates can be calculated. Next we move on to presuppositions and quantification, in the context of a dynamic version of predicate logic, suitably modified to allow for presupposition failure. In both the propositional and the quantificational case, presupposition failure can be viewed as error abortion of procedures. Thus, a dynamic assertion logic which describes the preconditions for error abortion is the suitable tool for analysing presupposition.     

Prolog/Rex-a way to extend Prolog for better knowledgerepresentation

Prolog/Rex represents a powerful amalgamation of the latest techniques for knowledge representation and processing, rich in semantic features that ease the difficult task of encoding heterogeneous knowledge of real-world applications. The Prolog/Rex concept mechanism lets a user represent domain entities in terms of their structural and behavioral properties, including multiple inheritance, arbitrary user-defined relations among entities, annotated values (demons), incomplete knowledge, etc. A flexible rule language helps the knowledge engineer capture human expertise and provide flexible control of the reasoning process. Additional Prolog/Rex strength that cannot be found in any other hybrid language made on top of Prolog is language level support for keeping many potentially contradictory solutions to a problem, allowing possible solutions and their implications to be automatically generated and completely explored before they are committed. The same mechanism is used to model time-states, which are useful in planning and scheduling applications of Prolog/Rex     

Partial indexing for nonuniform data distributions in relationalDBMS's

It is well known that the effectiveness of relational database systems is greatly dependent on the efficiency of the data access strategies. For this reason, much work has been devoted to the development of new access techniques, supported by adequate access structures such as the B⁺trees. The effectiveness of the B ⁺tree also depends on the data distribution characteristics; in particular, poor performance results when the data show strong key value distribution unbalancing. The aim of this paper is to present the partial index: a new access structure that is useful in such cases of unbalancing, as an alternative to the B⁺tree unclustered indexes. The access structures are built in the physical design phase, and at execution (or compilation) time, the optimizer chooses the most efficient access path. Thus, integration of the partial indexing technique in the design and in the optimization process are also described     

Evaluation of a parallel branch-and-bound algorithm on a class ofmultiprocessors

We propose and evaluate a parallel “decomposite best-first” search branch-and-bound algorithm (dbs) for MIN-based multiprocessor systems. We start with a new probabilistic model to estimate the number of evaluated nodes for a serial best-first search branch-and-bound algorithm. This analysis is used in predicting the parallel algorithm speed-up. The proposed algorithm initially decomposes a problem into N subproblems, where N is the number of processors available in a multiprocessor. Afterwards, each processor executes the serial best-first search to find a local feasible solution. Local solutions are broadcasted through the network to compute the final solution. A conflict-free mapping scheme, known as the step-by-step spread, is used for subproblem distribution on the MIN. A speedup expression for the parallel algorithm is then derived using the serial best-first search node evaluation model. Our analysis considers both computation and communication overheads for providing realistic speed-up. Communication modeling is also extended for the parallel global best-first search technique. All the analytical results are validated via simulation. For large systems, when communication overhead is taken into consideration, it is observed that the parallel decomposite best-first search algorithm provides better speed-up compared to other reported schemes     

Constant-time parallel algorithms for image labeling on areconfigurable network of processors

A constant-time algorithm for labeling the connected components of an N×N image on a reconfigurable network of N³ processors is presented. The main contribution of the algorithm is a novel constant-time technique for determining the minimum-labeled PE in each component. The number of processors used by the algorithm can be reduced to N/sup 2+(1/d/), for any 1⩽d⩽log N, if O(d) time is allowed     

Processor membership in asynchronous distributed systems

Presents protocols for determining processor membership in asynchronous distributed systems that are subject to processor and communication faults. These protocols depend on the placement of a total order on broadcast messages. The types of systems for which each of these protocols is applicable are characterized by the properties of the communication mechanisms and by the availability of stable storage. In the absence of stable storage or of a mechanism for distinguishing promptly delivered messages, the authors show that no membership protocol can exist. They also discuss their experience in implementing these membership protocols     

Unicast-based multicast communication in wormhole-routed networks

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log ₂ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given