Independence in CLP Languages

Studying independence of goals has proven very useful in the context of logic programming. In particular, it has provided a formal basis for powerful automatic parallelization tools, since independence ensures that two goals may be evaluated in parallel while preserving correctness and eciency. We extend the concept of independence to constraint logic programs (CLP) and prove that it also ensures the correctness and eciency of the parallel evaluation of independent goals. Independence for CLP languages is more complex than for logic programming as search space preservation is necessary but no longer sucient for ensuring correctness and eciency. Two additional issues arise. The rst is that the cost of constraint solving may depend upon the order constraints are encountered. The second is the need to handle dynamic scheduling. We clarify these issues by proposing various types of search independence and constraint solver independence, and show how they can be combined to allow dierent optimizations, from parallelism to intelligent backtracking. Sucient conditions for independence which can be evaluated \a priori" at run-time are also proposed. Our study also yields new insights into independence in logic programming languages. In particular, we show that search space preservation is not only a sucient but also a necessary condition for ensuring correctness and eciency of parallel execution.

Exploiting goal independence in the analysis of logic programs

This paper illustrates the use of a top-down framework to obtain goal independent analyses of logic programs, a task which is usually associated with the bottom-up approach. While it is well known that the bottomup approach can be used, through the magic set transformation, for goal dependent analysis, it is less known that the top-down approach can be used for goal independent analysis. The paper describes two ways of doing the latter. We show how the results of a goal independent analysis can be used to speed up subsequent goal dependent analyses. However this speed-up may result in a loss of precisión. The influence of domain characteristics on this precisión is discussed and an experimental evaluation using a generic top-down analyzer is described.

Effectiveness of global analysis in strict independence-based automatic program parallelization

This paper presents a study of the effectiveness of global analysis in the parallelization of logic programs using strict independence. A number of well-known approximation domains are selected and tlieir usefulness for the application in hand is explained. Also, methods for using the information provided by such domains to improve parallelization are proposed. Local and global analyses are built using these domains and such analyses are embedded in a complete parallelizing compiler. Then, the performance of the domains (and the system in general) is assessed for this application through a number of experiments. We argüe that the results offer significant insight into the characteristics of these domains, the demands of the application, and the tradeoffs involved.

Independence in constraint logic programs

Studying independence of literals, variables, and substitutions has proven very useful in the context of logic programming (LP). Here we study independence in the broader context of constraint logic programming (CLP). We show that a naive extrapolation of the LP definitions of independence to CLP is unsatisfactory (in fact, wrong) for two reasons. First, because interaction between variables through constraints is more complex than in the case of logic programming. Second, in order to ensure the efUciency of several optimizations not only must independence of the search space be considered, but also an orthogonal issue - "independence of constraint solving." We clarify these issues by proposing various types of search independence and constraint solver independence, and show how they can be combined to allow different independence-related optimizations, from parallelism to intelligent backtracking. Sufficient conditions for independence which can be evaluated "a-priori" at run-time are also proposed. Our results suggest that independence, provided a suitable definition is chosen, is even more useful in CLP than in LP.

Conditional parallelization of nonStrict independence. Procedures and assessmen

This paper presents a conditional parallelization process for and-parallelism based on the notion of non-strict independence, a more relaxed notion than the traditional of strict independence. By using this notion, a parallelism annotator can extract more parallelism from programs. On the other hand, the intrinsic complexity of non-strict independence poses new challenges to this task. We report here on the implementation we have accomplished of an annotator for non-strict independence, capable of producing both static and dynamic execution graphs. This implementation, along with the also implemented independence checker and their integration in our system, have resulted what is, to the best of our knowledge, the first parallelizing compiler based on nonstrict independence which produces dynamic execution graphs. The paper also presents a preliminary assessment of the implemented tools, comparing them with the existing ones for strict independence, which shows encouraging results.

Independence and search space preservation in dynamically scheduled constraint logic languages

This paper performs a further generalization of the notion of independence in constraint logic programs to the context of constraint logic programs with dynamic scheduling. The complexity of this new environment made necessary to first formally define the relationship between independence and search space preservation in the context of CLP languages. In particular, we show that search space preservation is, in the context of CLP languages, not only a sufficient but also a necessary condition for ensuring that both the intended solutions and the number of transitions performed do not change. These results are then extended to dynamically scheduled languages and used as the basis for the extension of the concepts of independence. We also propose several a priori sufficient conditions for independence and also give correctness and efficiency results for parallel execution of constraint logic programs based on the proposed notions of independence.

Independence, Global analysis, and parallelism, in dinamically scheduled constraint logic programming.

El punto de vista de muchas otras aplicaciones que modifican las reglas de computación. En segundo lugar, y una vez generalizado el concepto de independencia, es necesario realizar un estudio exhaustivo de la efectividad de las herramientas de análisis en la tarea de la paralelizacion automática. Los resultados obtenidos de dicha evaluación permiten asegurar de forma empírica que la utilización de analizadores globales en la tarea de la paralelizacion automática es vital para la consecución de una paralelizarían efectiva. Por último, a la luz de los buenos resultados obtenidos sobre la efectividad de los analizadores de flujo globales basados en la interpretación abstracta, se presenta la generalización de las herramientas de análisis al contexto de los lenguajes lógicos restricciones y planificación dinámica.

Apoprotein B100 has a prolonged interaction with the translocon during which its lipidation and translocation change from dependence on the microsomal triglyceride transfer protein to independence

When lipid synthesis is limited in HepG2 cells, apoprotein B100 (apoB100) is not secreted but rapidly degraded by the ubiquitin-proteasome pathway. To investigate apoB100 biosynthesis and secretion further, the physical and functional states of apoB100 destined for either degradation or lipoprotein assembly were studied under conditions in which lipid synthesis, proteasomal activity, and microsomal triglyceride transfer protein (MTP) lipid-transfer activity were varied. Cells were pretreated with a proteasomal inhibitor (which remained with the cells throughout the experiment) and radiolabeled for 15 min. During the chase period, labeled apoB100 remained associated with the microsomes. Furthermore, by crosslinking sec61β to apoB100, we showed that apoB100 remained close to the translocon at the same time apoB100–ubiquitin conjugates could be detected. When lipid synthesis and lipoprotein assembly/secretion were stimulated by adding oleic acid (OA) to the chase medium, apoB100 was deubiquitinated, and its interaction with sec61β was disrupted, signifying completion of translocation concomitant with the formation of lipoprotein particles. MTP participates in apoB100 translocation and lipoprotein assembly. In the presence of OA, when MTP lipid-transfer activity was inhibited at the end of pulse labeling, apoB100 secretion was abolished. In contrast, when the labeled apoB100 was allowed to accumulate in the cell for 60 min before adding OA and the inhibitor, apoB100 lipidation and secretion were no longer impaired. Overall, the data imply that during most of its association with the endoplasmic reticulum, apoB100 is close to or within the translocon and is accessible to both the ubiquitin-proteasome and lipoprotein-assembly pathways. Furthermore, MTP lipid-transfer activity seems to be necessary only for early translocation and lipidation events.

Independence of metastatic ability and extravasation: metastatic ras-transformed and control fibroblasts extravasate equally well.

Escape of cancer cells from the circulation (extravasation) is thought to be a major rate-limiting step in metastasis, with few cells being able to extravasate. Furthermore, highly metastatic cells are believed to extravasate more readily than poorly metastatic cells. We assessed in vivo the extravasation ability of highly metastatic ras-transformed NIH 3T3 cells (PAP2) versus control nontumorigenic nontransformed NIH 3T3 cells and primary mouse embryo fibroblasts. Fluorescently labeled cells were injected intravenously into chicken embryo chorioallantoic membrane and analyzed by intravital videomicroscopy. The chorioallantoic membrane is an appropriate model for studying extravasation, since, at the embryonic stage used, the microvasculature exhibits a continuous basement membrane and adult permeability properties. The kinetics of extravasation were assessed by determining whether individual cells (n = 1481) were intravascular, extravascular, or in the process of extravasation, at 3, 6, and 24 h after injection. Contrary to expectations, our results showed that all three cell types extravasated with the same kinetics. By 24 h after injection > 89% of observed cells had completed extravasation from the capillary plexus. After extravasation, individual fibroblasts of all cell types demonstrated preferential migration within the mesenchymal layer toward arterioles, not to venules or lymphatics. Thus in this model and for these cells, extravasation is independent of metastatic ability. This suggests that the ability to extravasate in vivo is not necessarily predictive of subsequent metastasis formation, and that postextravasation events may be key determinants in metastasis.

"Viewers should not try this at home". Die Verfassungsgerichte Bosnien-Herzegowinas und Kosovos in deren Rolle als Schlichtungsinstanzen in ethnopolitischen Konflikten = The constitutional courts of Bosnia-Herzegovina and Kosovo in their role as arbitration bodies in ethno-political conflicts. EDAP 01/2014

The article analyzes the role of constitutional courts in Bosnia and Kosovo, both characterized by their partly internationalized membership, in the adjudication of cases that are highly controversial between the different ethno-political factions. The main focus is on the Constitutional Court of Bosnia, which presents one of the richest and most interesting examples of “lawfare” in divided societies. The concept of lawfare has been adapted to refer to the continuation of political battles by ethno-political actors through legal means, in this case, constitutional adjudication. In Kosovo, the Constitutional Court has been an important defender of diversity, albeit its primary focus and merit are to have contributed to the establishment of a concept of democracy close to the people of Kosovo. The article concludes that constitutional courts represent important institutions of internal conflict resolution in divided societies, which have been instrumental in shaping multiculturalism in these post-conflict societies divided by deep ethnic cleavages.