IDIOM: Integrating dependent and-, independent and-, and or-parallelism

Independent and-parallelism, dependent and-parallelism and or-parallelism are the three main forms of implicit parallelism present in logic programs. In this paper we present a model, IDIOM, which exploits all three forms of parallelism in a single framework. IDIOM is based on a combination of the Basic Andorra Model and the Extended And-Or Tree Model. Our model supports both Prolog as well as the fíat concurrent logic languages. We discuss the issues that arise in combining the three forms of parallelism, and our solutions to them. We also present an implementation scheme, based on binding arrays, for implementing IDIOM.

The CDG, UDG, and MEL methods for automatic compile-time parallelization of logic programs for independent and-parallelism

There has been significant interest in parallel execution models for logic programs which exploit Independent And-Parallelism (IAP). In these models, it is necessary to determine which goals are independent and therefore eligible for parallel execution and which goals have to wait for which others during execution. Although this can be done at run-time, it can imply a very heavy overhead. In this paper, we present three algorithms for automatic compiletime parallelization of logic programs using IAP. This is done by converting a clause into a graph-based computational form and then transforming this graph into linear expressions based on &-Prolog, a language for IAP. We also present an algorithm which, given a clause, determines if there is any loss of parallelism due to linearization, for the case in which only unconditional parallelism is desired. Finally, the performance of these annotation algorithms is discussed for some benchmark programs.

Non-strict independent and-parallelism

This paper presents and develops a generalized concept of Non-Strict Independent And Parallelism (NSIAP). NSIAP extends the applicability of Independent And- Parallelism (IAP) by enlarging the class of goals which are eligible for parallel execution. At the same time it maintains IAP's ability to run non-deterministic goals in parallel and to preserve the computational complexity expected in the execution of the program by the programmer. First, a parallel execution framework is defined and some fundamental correctness results, in the sense of equivalence of solutions with the sequential model, are discussed for this framework. The issue of efficiency is then considered. Two new definitions of NSI are given for the cases of puré and impure goals respectively and efficiency results are provided for programs parallelized under these definitions which include treatment of the case of goal failure: not only is reduction of execution time guaranteed (modulo run-time overheads) in the absence of failure but it is also shown that in the worst case of failure no speed-down will occur. In addition to applying to NSI, these results carry over and complete previous results shown in the context of IAP which did not deal with the case of goal failure. Finally, some practical examples of the application of the NSIAP concept to the parallelization of a set of programs are presented and performance results, showing the advantage of using NSI, are given.

&-prolog and its performance: exploiting independent and-parallelism

An Independent And-Parallel Prolog model and implementation, &-Prolog, are described. The description includes a summary of the system's architecture, some details of its execution model (based on the RAP-WAM model), and most importantly, its performance on sequential workstations and shared memory multiprocessors as compared with state-of-the-art Prolog systems. Speedup curves are provided for a collection of benchmark programs which demónstrate significant speed advantages over state-of the art sequential systems.

On the correctness and efficiency of independent and-parallelism in logic programs

This paper presents and proves some fundamental results for independent and-parallelism (IAP). First, the paper treats the issues of correctness and efficiency: after defining strict and non-strict goal independence, it is proved that if strictly independent goals are executed in parallel the solutions obtained are the same as those produced by standard sequential execution. It is also shown that, in the absence of failure, the parallel proof procedure doesn't genérate any additional work (with respect to standard SLDresolution) while the actual execution time is reduced. The same results hold even if non-strictly independent goals are executed in parallel, provided a trivial rewriting of such goals is performed. In addition, and most importantly, treats the issue of compile-time generation of IAP by proposing conditions, to be written at compile-time, to efficiently check strict and non-strict goal independence at run-time and proving the sufficiency of such conditions. It is also shown how simpler conditions can be constructed if some information regarding the binding context of the goals to be executed in parallel is available to the compiler trough either local or program-level analysis. These results therefore provide a formal basis for the automatic compile-time generation of IAP. As a corollary of such results, the paper also proves that negative goals are always non-strictly independent, and that goals which share a first occurrence of an existential variable are never independent.

Complete and efficient methods for supporting side effects in independent/restricted and-parallelism

It has been shown that it is possible to exploit Independent/Restricted And-parallelism in logic programs while retaining the conventional "don't know" semantics of such programs. In particular, it is possible to parallelize pure Prolog programs while maintaining the semantics of the language. However, when builtin side-effects (such as write or assert) appear in the program, if an identical observable behaviour to that of sequential Prolog implementations is to be preserved, such side-effects have to be properly sequenced. Previously proposed solutions to this problem are either incomplete (lacking, for example, backtracking semantics) or they force sequentialization of significant portions of the execution graph which could otherwise run in parallel. In this paper a series of side-effect synchronization methods are proposed which incur lower overhead and allow more parallelism than those previously proposed. Most importantly, and unlike previous proposals, they have well-defined backward execution behaviour and require only a small modification to a given (And-parallel) Prolog implementation.

A simulation study on parallel backtracking with solution memoing for independent and-parallelism

Goal-level Independent and-parallelism (IAP) is exploited by scheduling for simultaneous execution two or more goals which will not interfere with each other at run time. This can be done safely even if such goals can produce multiple answers. The most successful IAP implementations to date have used recomputation of answers and sequentially ordered backtracking. While in principle simplifying the implementation, recomputation can be very inefficient if the granularity of the parallel goals is large enough and they produce several answers, while sequentially ordered backtracking limits parallelism. And, despite the expected simplification, the implementation of the classic schemes has proved to involve complex engineering, with the consequent difficulty for system maintenance and expansion, and still frequently run into the well-known trapped goal and garbage slot problems. This work presents ideas about an alternative parallel backtracking model for IAP and a simulation studio. The model features parallel out-of-order backtracking and relies on answer memoization to reuse and combine answers. Whenever a parallel goal backtracks, its siblings also perform backtracking, but after storing the bindings generated by previous answers. The bindings are then reinstalled when combining answers. In order not to unnecessarily penalize forward execution, non-speculative and-parallel goals which have not been executed yet take precedence over sibling goals which could be backtracked over. Using a simulator, we show that this approach can bring significant performance advantages over classical approaches.

Automatic unrestricted independent and-parallelism in logic programs

We present new algorithms which perform automatic parallelization via source-to-source transformations. The objective is to exploit goal-level, unrestricted independent andparallelism. The proposed algorithms use as targets new parallel execution primitives which are simpler and more flexible than the well-known &/2 parallel operator, which makes it possible to generate better parallel expressions by exposing more potential parallelism among the literals of a clause than is possible with &/2. The main differences between the algorithms stem from whether the order of the solutions obtained is preserved or not, and on the use of determinacy information. We briefly describe the environment where the algorithms have been implemented and the runtime platform in which the parallelized programs are executed. We also report on an evaluation of an implementation of our approach. We compare the performance obtained to that of previous annotation algorithms and show that relevant improvements can be obtained.

Towards extracting non-strict independent and-parallelism using sharing and freeness information

Logic programming systems which exploit and-parallelism among non-deterministic goals rely on notions of independence among those goals in order to ensure certain efficiency properties. "Non-strict" independence (NSI) is a more relaxed notion than the traditional notion of "strict" independence (SI) which still ensures the relevant efficiency properties and can allow considerable more parallelism than SI. However, all compilation technology developed to date has been based on SI, presumably because of the intrinsic complexity of exploiting NSI. This is related to the fact that NSI cannot be determined "a priori" as SI. This paper fills this gap by developing a technique for compile-time detection and annotation of NSI. It also proposes algorithms for combined compile- time/run-time detection, presenting novel run-time checks for this type of parallelism. Also, a transformation procedure to eliminate shared variables among parallel goals is presented, attempting to perform as much work as possible at compiletime. The approach is based on the knowledge of certain properties about run-time instantiations of program variables —sharing and freeness— for which compile-time technology is available, with new approaches being currently proposed.

Experimenting with independent and-parallel prolog using standard prolog

This paper presents an approximation to the study of parallel systems using sequential tools. The Independent And-parallelism in Prolog is an example of parallel processing paradigm in the framework of logic programming, and implementations like

Effect of short-term fasting prior to slaughter on welfare and meat quality or rainbow trout (Oncorhynchus mykiss)

El manejo pre-sacrificio es de vital importancia en acuicultura, ya que afecta tanto a las reacciones fisiológicas como a los procesos bioquímicos post mortem, y por tanto al bienestar y a la calidad del producto. El ayuno pre-sacrificio se lleva a cabo de forma habitual en acuicultura, ya que permite el vaciado del aparato digestivo de restos de alimento y heces, reduciendo de esta manera la carga bacteriana en el intestino y la dispersión de enzimas digestivos y potenciales patógenos a la carne. Sin embargo, la duración óptima de este ayuno sin que el pez sufra un estrés innecesario no está clara. Además, se sabe muy poco sobre la mejor hora del día para realizar el sacrificio, lo que a su vez está regido por los ritmos diarios de los parámetros fisiológicos de estrés. Finalmente, se sabe que la temperatura del agua juega un papel muy importante en la fisiología del estrés pero no se ha determinado su efecto en combinación con el ayuno. Además, las actuales recomendaciones en relación a la duración óptima del ayuno previo al sacrificio en peces no suelen considerar la temperatura del agua y se basan únicamente en días y no en grados día (ºC d). Se determinó el efecto del ayuno previo al sacrificio (1, 2 y 3 días, equivalente a 11,1-68,0 grados día) y la hora de sacrificio (08h00, 14h00 y 20h00) en trucha arco iris (Oncorhynchus mykiss) de tamaño comercial en cuatro pruebas usando diferentes temperaturas de agua (Prueba 1: 11,8 ºC; Prueba 2: 19,2 ºC; Prueba 3: 11,1 ºC; y Prueba 4: 22,7 ºC). Se midieron indicadores biométricos, hematológicos, metabólicos y de calidad de la carne. En cada prueba, los valores de los animales ayunados (n=90) se compararon con 90 animales control mantenidos bajo condiciones similares pero nos ayunados. Los resultados sugieren que el ayuno tuvo un efecto significativo sobre los indicadores biométricos. El coeficiente de condición en los animales ayunados fue menor que en los controles después de 2 días de ayuno. El vaciado del aparato digestivo se produjo durante las primeras 24 h de ayuno, encontrándose pequeñas cantidades de alimento después de 48 h. Por otra parte, este vaciado fue más rápido cuando las temperaturas fueron más altas. El peso del hígado de los animales ayunados fue menor y las diferencias entre truchas ayunadas y controles fueron más evidentes a medida que el vaciado del aparato digestivo fue más rápido. El efecto del ayuno hasta 3 días en los indicadores hematológicos no fue significativo. Los niveles de cortisol en plasma resultaron ser altos tanto en truchas ayunadas como en las alimentadas en todas las pruebas realizadas. La concentración media de glucosa varió entre pruebas pero mostró una tendencia a disminuir en animales ayunados a medida que el ayuno progresaba. En cualquier caso, parece que la temperatura del agua jugó un papel muy importante, ya que se encontraron concentraciones más altas durante los días 2 y 3 de ayuno en animales mantenidos a temperaturas más bajas previamente al sacrificio. Los altos niveles de lactato obtenidos en sangre parecen sugerir episodios de intensa actividad muscular pero no se pudo encontrar relación con el ayuno. De la misma manera, el nivel de hematocrito no mostró efecto alguno del ayuno y los leucocitos tendieron a ser más altos cuando los animales estaban menos estresados y cuando su condición corporal fue mayor. Finalmente, la disminución del peso del hígado (índice hepatosomático) en la Prueba 3 no se vio acompañada de una reducción del glucógeno hepático, lo que sugiere que las truchas emplearon una estrategia diferente para mantener constantes los niveles de glucosa durante el periodo de ayuno en esa prueba. En relación a la hora de sacrificio, se obtuvieron niveles más bajos de cortisol a las 20h00, lo que indica que las truchas estaban menos estresadas y que el manejo pre-sacrificio podría resultar menos estresante por la noche. Los niveles de hematocrito fueron también más bajos a las 20h00 pero solo con temperaturas más bajas, sugiriendo que las altas temperaturas incrementan el metabolismo. Ni el ayuno ni la hora de sacrificio tuvieron un efecto significativo sobre la evolución de la calidad de la carne durante los 3 días de almacenamiento. Por el contrario, el tiempo de almacenamiento sí que parece tener un efecto claro sobre los parámetros de calidad del producto final. Los niveles más bajos de pH se alcanzaron a las 24-48 h post mortem, con una lata variabilidad entre duraciones del ayuno (1, 2 y 3 días) en animales sacrificados a las 20h00, aunque no se pudo distinguir ningún patrón común. Por otra parte, la mayor rigidez asociada al rigor mortis se produjo a las 24 h del sacrificio. La capacidad de retención de agua se mostró muy estable durante el período de almacenamiento y parece ser independiente de los cambios en el pH. El parámetro L* de color se incrementó a medida que avanzaba el período de almacenamiento de la carne, mientras que los valores a* y b* no variaron en gran medida. En conclusión, basándose en los resultados hematológicos, el sacrificio a última hora del día parece tener un efecto menos negativo en el bienestar. De manera general, nuestros resultados sugieren que la trucha arco iris puede soportar un período de ayuno previo al sacrificio de hasta 3 días o 68 ºC d sin que su bienestar se vea seriamente comprometido. Es probable que con temperaturas más bajas las truchas pudieran ser ayunadas durante más tiempo sin ningún efecto negativo sobre su bienestar. En cualquier caso, se necesitan más estudios para determinar la relación entre la temperatura del agua y la duración óptima del ayuno en términos de pérdida de peso vivo y la disminución de los niveles de glucosa en sangre y otros indicadores metabólicos. SUMMARY Pre-slaughter handling in fish is important because it affects both physiological reactions and post mortem biochemical processes, and thus welfare and product quality. Pre-slaughter fasting is regularly carried out in aquaculture, as it empties the viscera of food and faeces, thus reducing the intestinal bacteria load and the spread of gut enzymes and potential pathogens to the flesh. However, it is unclear how long rainbow trout can be fasted before suffering unnecessary stress. In addition, very little is known about the best time of the day to slaughter fish, which may in turn be dictated by diurnal rhythms in physiological stress parameters. Water temperature is also known to play a very important role in stress physiology in fish but the combined effect with fasting is unclear. Current recommendations regarding the optimal duration of pre-slaughter fasting do not normally consider water temperature and are only based on days, not degree days (ºC d). The effects of short-term fasting prior to slaughter (1, 2 and 3 days, between 11.1 and 68.0 ºC days) and hour of slaughter (08h00, 14h00 and 20h00) were determined in commercial-sized rainbow trout (Oncorhynchus mykiss) over four trials at different water temperatures (TRIAL 1, 11.8 ºC; TRIAL 2, 19.2 ºC; TRIAL 3, 11.1 ºC; and TRIAL 4, 22.7 ºC). We measured biometric, haematological, metabolic and product quality indicators. In each trial, the values of fasted fish (n=90) were compared with 90 control fish kept under similar conditions but not fasted. Results show that fasting affected biometric indicators. The coefficient of condition in fasted trout was lower than controls 2 days after food deprivation. Gut emptying occurred within the first 24 h after the cessation of feeding, with small traces of digesta after 48 h. Gut emptying was faster at higher water temperatures. Liver weight decreased in food deprived fish and differences between fasted and fed trout were more evident when gut clearance was faster. The overall effect of fasting for up to three days on haematological indicators was small. Plasma cortisol levels were high in both fasted and fed fish in all trials. Plasma glucose response to fasting varied among trials, but it tended to be lower in fasted fish as the days of fasting increased. In any case, it seems that water temperature played a more important role, with higher concentrations at lower temperatures on days 2 and 3 after the cessation of feeding. Plasma lactate levels indicate moments of high muscular activity and were also high, but no variation related to fasting could be found. Haematocrit did not show any significant effect of fasting, but leucocytes tended to be higher when trout were less stressed and when their body condition was higher. Finally, the loss of liver weight was not accompanied by a decrease in liver glycogen (only measured in TRIAL 3), suggesting that a different strategy to maintain plasma glucose levels was used. Regarding the hour of slaughter, lower cortisol levels were found at 20h00, suggesting that trout were less stressed later in the day and that pre-slaughter handling may be less stressful at night. Haematocrit levels were also lower at 20h00 but only at lower temperatures, indicating that higher temperatures increase metabolism. Neither fasting nor the hour of slaughter had a significant effect on the evolution of meat quality during 3 days of storage. In contrast, storage time seemed to have a more important effect on meat quality parameters. The lowest pH was reached 24-48 h post mortem, with a higher variability among fasting durations at 20h00, although no clear pattern could be discerned. Maximum stiffening from rigor mortis occurred after 24 h. The water holding capacity was very stable throughout storage and seemed to be independent of pH changes. Meat lightness (L*) slightly increased during storage and a* and b*-values were relatively stable. In conclusion, based on the haematological results, slaughtering at night may have less of a negative effect on welfare than at other times of the day. Overall, our results suggest that rainbow trout can cope well with fasting up to three days or 68 ºC d prior to slaughter and that their welfare is therefore not seriously compromised. At low water temperatures, trout could probably be fasted for longer periods without negative effects on welfare but more research is needed to determine the relationship between water temperature and days of fasting in terms of loss of live weight and the decrease in plasma glucose and other metabolic indicators.

Experimenting with independent and-parallel prolog using standard prolog

This paper presents an approximation to the study of parallel systems using sequential tools. The Independent And-parallelism in Prolog is an example of parallel processing paradigm in the framework of logic programming, and implementations like

Automatic motion compensation of free breathing acquired myocardial perfusion data by using independent component analysis

Images acquired during free breathing using first-pass gadolinium-enhanced myocardial perfusion magnetic resonance imaging (MRI) exhibit a quasiperiodic motion pattern that needs to be compensated for if a further automatic analysis of the perfusion is to be executed. In this work, we present a method to compensate this movement by combining independent component analysis (ICA) and image registration: First, we use ICA and a time?frequency analysis to identify the motion and separate it from the intensity change induced by the contrast agent. Then, synthetic reference images are created by recombining all the independent components but the one related to the motion. Therefore, the resulting image series does not exhibit motion and its images have intensities similar to those of their original counterparts. Motion compensation is then achieved by using a multi-pass image registration procedure. We tested our method on 39 image series acquired from 13 patients, covering the basal, mid and apical areas of the left heart ventricle and consisting of 58 perfusion images each. We validated our method by comparing manually tracked intensity profiles of the myocardial sections to automatically generated ones before and after registration of 13 patient data sets (39 distinct slices). We compared linear, non-linear, and combined ICA based registration approaches and previously published motion compensation schemes. Considering run-time and accuracy, a two-step ICA based motion compensation scheme that first optimizes a translation and then for non-linear transformation performed best and achieves registration of the whole series in 32 ± 12 s on a recent workstation. The proposed scheme improves the Pearsons correlation coefficient between manually and automatically obtained time?intensity curves from .84 ± .19 before registration to .96 ± .06 after registration

User-independent accelerometer-based gesture recognition for mobile devices

Many mobile devices embed nowadays inertial sensors. This enables new forms of human-computer interaction through the use of gestures (movements performed with the mobile device) as a way of communication. This paper presents an accelerometer-based gesture recognition system for mobile devices which is able to recognize a collection of 10 different hand gestures. The system was conceived to be light and to operate in a user -independent manner in real time. The recognition system was implemented in a smart phone and evaluated through a collection of user tests, which showed a recognition accuracy similar to other state-of-the art techniques and a lower computational complexity. The system was also used to build a human -robot interface that enables controlling a wheeled robot with the gestures made with the mobile phone.

Definition and study of the innovative façade Natura, made of independent pre-vegetated and water storage type panels

Definition and study of the innovative façade Natura, made of independent pre-vegetated and water storage type panels