Volume 20, 2001, No. 1

STRATEGIES OF STRUCTURAL SYNTHESIS OF PROGRAMS AND ITS EXTENSIONS

Mihhail MATSKIN, Enn TYUGU   Abstract Proof search for the structural synthesis of programs (SSP)- a deductive program synthesis method which is suited for compositional programming in large and is in practical use in a number of programming environments is explained. SSP is based on a decidable logical calculus where complexity of the proof search is still PSPACE. This requires paying special attention to the efficiency of search. The practice of application of SSP has given its several modifications and extensions. Besides the general case of SSP and its strategies, we present synthesis with independent subtasks, a number of heuristics used for speeding up the search and partial deduction in the framework of SSP.

 

TOMOGRAPHIC IMAGE RECONSTRUCTION ON THE INSTRUCTION SYSTOLIC ARRAY

Bertil SCHMIDT, Heiko SCHRÖDER, Manfred SCHIMMLER   Abstract Instruction systolic arrays (ISAs) have been developed in order to combine the speed and simplicity of systolic arrays with the flexibility of MIMD parallel computer systems. ISAs are available as square arrays of small RISC processors capable of performing integer and floating point arithmetic. In this paper we show that the systolic control flow can be used for an efficient reconstruction of images from its projections. The demand for fast image reconstruction arises in the field of computerized tomography. It is shown how the new parallel algorithm leads to a high-speed implementation on Systola 1024, the first commercial parallel computer with the ISA architecture.

 

ON THE CONNECTION BETWEEN NORMAL DEFAULT REASONING AND CONDITIONAL LOGIC

Nadim OBEID   Abstract Conditional logic plays an important role in recent attempts to investigate default reasoning. In this paper we show that normal default reasoning can be captured in the conditional logic CL: Reiter extensions of a normal default theory delta = <D, W> correspond to sets of sentences that are maximally CL-consistent with respect to Cond-E(delta) which is a set of conditional sentences constructed using defaults in D that are relevant to extensions. We also discuss Delgrande conditional approach to default reasoning and point out one of its weaknesses. In employing CL, we provide a semantic interpretation of defaults that is weaker than that of normality/typicality proposed by Delgrande and develop an approach that produces all the Reiter extensions of a normal default theory. We also show that there is a one-to-one correspondence between conditional proofs of sentences that belong to extensions and Reiter default proofs.

 

PREDICTING CPU UTILIZATION BY FUZZY STOCHASTIC PREDICTION

Yi-Fan WANG, Mei-Hua HSU, Yu-Liang CHUANG   Abstract In this paper, we use the fuzzy stochastic technique to predict the mainframe's CPU utilization from the given database of IBM's OS/390 system log at a specific time. Consequently, system programmers can tune the system to improve its performance by moving out the unimportant jobs during the peak time. To address this issue, we proposed an effective method, a fuzzy stochastic prediction (FSP), to predict the CPU utilization in a specific time. The fuzzy stochastic variable is a parameter in FSP, which is generated by the recent system behavior.

 

A FAST PARALLEL TREE CONTRACTION FOR THE RAY- OBJECT CALCULUS USING OPEN-MP

Zineb HABBAS, Francine HERRMANN, Michaël KRAJECKI   Abstract Ray tracing is a well known algorithm in the visualization area for its image quality and its simplicity. Unfortunately, it is computationally expensive. The basic operation of ray tracing is the calculus of the intersection points between rays and objects. This operation represents a large part of this algorithm. The goal of this work is mainly the proposition of an optimal parallel algorithm performing a ray-CSG intersection in O(log n log log n) time complexity and O(n) processors on a PRAM CREW model. It is based on the Contract tree algorithms developed in [1, 8] . Finally, the parallel tree contraction algorithm is implemented on a parallel machine.

 

Volume 20, 2001, No. 1