Constructs and evaluation strategies for intelligent speculative parallelism - armageddon revisited

This report addresses speculative parallelism (the assignment of spare processing resources to tasks which are not known to be strictly required for the successful completion of a computation) at the user and application level. At this level, the execution of a program is seen as a (dynamic) tree —a graph, in general. A solution for a problem is a traversal of this graph from the initial state to a node known to be the answer. Speculative parallelism then represents the assignment of resources to múltiple branches of this graph even if they are not positively known to be on the path to a solution. In highly non-deterministic programs the branching factor can be very high and a naive assignment will very soon use up all the resources. This report presents work assignment strategies other than the usual depth-first and breadth-first. Instead, best-first strategies are used. Since their definition is application-dependent, the application language contains primitives that allow the user (or application programmer) to a) indícate when intelligent OR-parallelism should be used; b) provide the functions that define "best," and c) indícate when to use them. An abstract architecture enables those primitives to perform the search in a "speculative" way, using several processors, synchronizing them, killing the siblings of the path leading to the answer, etc. The user is freed from worrying about these interactions. Several search strategies are proposed and their implementation issues are addressed. "Armageddon," a global pruning method, is introduced, together with both a software and a hardware implementation for it. The concepts exposed are applicable to áreas of Artificial Intelligence such as extensive expert systems, planning, game playing, and in general to large search problems. The proposed strategies, although showing promise, have not been evaluated by simulation or experimentation.

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.

Estimación del coste de almacenamiento de una solución de preservación de la privacidad en archivos BAM reales

A menudo los científicos secuencian el ADN de un gran número de personas con el objetivo de determinar qué genes se asocian con determinadas enfermedades. Esto permite meóon del genoma humano. El precio de un perfil genómico completo se ha posicionado por debajo de los 200 dólares y este servicio lo ofrecen muchas compañías, la mayor parte localizadas en EEUU. Como consecuencia, en unos pocos a~nos la mayoría de las personas procedentes de los países desarrollados tendrán los medios para tener su ADN secuenciado. Alrededor del 0.5% del ADN de cada persona (que corresponde a varios millones de nucleótidos) es diferente del genoma de referencia debido a variaciones genéticas. Así que el genoma contiene información altamente sensible y personal y representa la identidad biológica óon sobre el entorno o estilo de vida de uno (a menudo facilmente obtenible de las redes sociales), sería posible inferir el fenotipo del individuo. Multiples GWAS (Genome Wide Association Studies) realizados en los últimos a~nos muestran que la susceptibilidad de un paciente a tener una enfermedad en particular, como el Alzheimer, cáncer o esquizofrenia, puede ser predicha parcialmente a partir de conjuntos de sus SNP (Single Nucleotide Polimorphism). Estos resultados pueden ser usados para medicina genómica personalizada (facilitando los tratamientos preventivos y diagnósticos), tests de paternidad genéticos y tests de compatibilidad genética para averiguar a qué enfermedades pueden ser susceptibles los descendientes. Estos son algunos de los beneficios que podemos obtener usando la información genética, pero si esta información no es protegida puede ser usada para investigaciones criminales y por compañías aseguradoras. Este hecho podría llevar a discriminaci ón genética. Por lo que podemos concluir que la privacidad genómica es fundamental por el hecho de que contiene información sobre nuestra herencia étnica, nuestra predisposición a múltiples condiciones físicas y mentales, al igual que otras características fenotópicas, ancestros, hermanos y progenitores, pues los genomas de cualquier par de individuos relacionados son idénticos al 99.9%, contrastando con el 99.5% de dos personas aleatorias. La legislación actual no proporciona suficiente información técnica sobre como almacenar y procesar de forma segura los genomas digitalizados, por lo tanto, es necesaria una legislación mas restrictiva ---ABSTRACT---Scientists typically sequence DNA from large numbers of people in order to determine genes associated with particular diseases. This allows to improve the modern healthcare and to provide a better understanding of the human genome. The price of a complete genome profile has plummeted below $200 and this service is ofered by a number of companies, most of them located in the USA. Therefore, in a few years, most individuals in developed countries will have the means of having their genomes sequenced. Around 0.5% of each person's DNA (which corresponds to several millions of nucleotides) is diferent from the reference genome, owing to genetic variations. Thus, the genome contains highly personal and sensitive information, and it represents our ultimate biological identity. By combining genomic data with information about one's environment or lifestyle (often easily obtainable from social networks), could make it possible to infer the individual's phenotype. Multiple Genome Wide Association Studies (GWAS) performed in recent years have shown that a patient's susceptibility to particular diseases, such as Alzheimer's, cancer, or schizophrenia, can be partially predicted from sets of his SNPs. This results can be used for personalized genomic medicine (facilitating preventive treatment and diagnosis), genetic paternity tests, ancestry and genealogical testing, and genetic compatibility tests in order to have knowledge about which deseases would the descendant be susceptible to. These are some of the betefts we can obtain using genoma information, but if this information is not protected it can be used for criminal investigations and insurance purposes. Such issues could lead to genetic discrimination. So we can conclude that genomic privacy is fundamental due to the fact that genome contains information about our ethnic heritage, predisposition to numerous physical and mental health conditions, as well as other phenotypic traits, and ancestors, siblings, and progeny, since genomes of any two closely related individuals are 99.9% identical, in contrast with 99.5%, for two random people. The current legislation does not ofer suficient technical information about safe and secure ways of storing and processing digitized genomes, therefore, there is need for more restrictive legislation.