Distributed models in P-Systems architectures to reduce computation time

Membrane systems are computational equivalent to Turing machines. However, their distributed and massively parallel nature obtains polynomial solutions opposite to traditional non-polynomial ones. At this point, it is very important to develop dedicated hardware and software implementations exploiting those two membrane systems features. Dealing with distributed implementations of P systems, the bottleneck communication problem has arisen. When the number of membranes grows up, the network gets congested. The purpose of distributed architectures is to reach a compromise between the massively parallel character of the system and the needed evolution step time to transit from one configuration of the system to the next one, solving the bottleneck communication problem. The goal of this paper is twofold. Firstly, to survey in a systematic and uniform way the main results regarding the way membranes can be placed on processors in order to get a software/hardware simulation of P-Systems in a distributed environment. Secondly, we improve some results about the membrane dissolution problem, prove that it is connected, and discuss the possibility of simulating this property in the distributed model. All this yields an improvement in the system parallelism implementation since it gets an increment of the parallelism of the external communication among processors. Proposed ideas improve previous architectures to tackle the communication bottleneck problem, such as reduction of the total time of an evolution step, increase of the number of membranes that could run on a processor and reduction of the number of processors.

Membrane Dissolution in Distributed Architectures of P-Systems

The goal of this paper is twofold. Firstly, to survey in a systematic and uniform way the main results regarding the way membranes can be placed on processors in order to get a software/hardware simulation of P-Systems in a distributed environment. Secondly, we improve some results about the membrane dissolution problem, prove that it is connected, and discuss the possibility of simulating this property in the distributed model. All this yields an improvement in the system parallelism implementation since it gets an increment of the parallelism of the external communication among processors. Also, the number of processors grows in such a way that is notorious the increment of the parallelism in the application of the evolution rules and the internal communica-tionsstudy because it gets an increment of the parallelism in the application of the evolution rules and the internal communications. Proposed ideas improve previous architectures to tackle the communication bottleneck problem, such as reduction of the total time of an evolution step, increase of the number of membranes that could run on a processor and reduction of the number of processors

Algoritmos de distribución de cargas de proceso en computación con membranas

Con el surgir de los problemas irresolubles de forma eficiente en tiempo polinomial en base al dato de entrada, surge la Computación Natural como alternativa a la computación clásica. En esta disciplina se trata de o bien utilizar la naturaleza como base de cómputo o bien, simular su comportamiento para obtener mejores soluciones a los problemas que los encontrados por la computación clásica. Dentro de la computación natural, y como una representación a nivel celular, surge la Computación con Membranas. La primera abstracción de las membranas que se encuentran en las células, da como resultado los P sistemas de transición. Estos sistemas, que podrían ser implementados en medios biológicos o electrónicos, son la base de estudio de esta Tesis. En primer lugar, se estudian las implementaciones que se han realizado, con el fin de centrarse en las implementaciones distribuidas, que son las que pueden aprovechar las características intrínsecas de paralelismo y no determinismo. Tras un correcto estudio del estado actual de las distintas etapas que engloban a la evolución del sistema, se concluye con que las distribuciones que buscan un equilibrio entre las dos etapas (aplicación y comunicación), son las que mejores resultados presentan. Para definir estas distribuciones, es necesario definir completamente el sistema, y cada una de las partes que influyen en su transición. Además de los trabajos de otros investigadores, y junto a ellos, se realizan variaciones a los proxies y arquitecturas de distribución, para tener completamente definidos el comportamiento dinámico de los P sistemas. A partir del conocimiento estático –configuración inicial– del P sistema, se pueden realizar distribuciones de membranas en los procesadores de un clúster para obtener buenos tiempos de evolución, con el fin de que la computación del P sistema sea realizada en el menor tiempo posible. Para realizar estas distribuciones, hay que tener presente las arquitecturas –o forma de conexión– de los procesadores del clúster. La existencia de 4 arquitecturas, hace que el proceso de distribución sea dependiente de la arquitectura a utilizar, y por tanto, aunque con significativas semejanzas, los algoritmos de distribución deben ser realizados también 4 veces. Aunque los propulsores de las arquitecturas han estudiado el tiempo óptimo de cada arquitectura, la inexistencia de distribuciones para estas arquitecturas ha llevado a que en esta Tesis se probaran las 4, hasta que sea posible determinar que en la práctica, ocurre lo mismo que en los estudios teóricos. Para realizar la distribución, no existe ningún algoritmo determinista que consiga una distribución que satisfaga las necesidades de la arquitectura para cualquier P sistema. Por ello, debido a la complejidad de dicho problema, se propone el uso de metaheurísticas de Computación Natural. En primer lugar, se propone utilizar Algoritmos Genéticos, ya que es posible realizar alguna distribución, y basada en la premisa de que con la evolución, los individuos mejoran, con la evolución de dichos algoritmos, las distribuciones también mejorarán obteniéndose tiempos cercanos al óptimo teórico. Para las arquitecturas que preservan la topología arbórea del P sistema, han sido necesarias realizar nuevas representaciones, y nuevos algoritmos de cruzamiento y mutación. A partir de un estudio más detallado de las membranas y las comunicaciones entre procesadores, se ha comprobado que los tiempos totales que se han utilizado para la distribución pueden ser mejorados e individualizados para cada membrana. Así, se han probado los mismos algoritmos, obteniendo otras distribuciones que mejoran los tiempos. De igual forma, se han planteado el uso de Optimización por Enjambres de Partículas y Evolución Gramatical con reescritura de gramáticas (variante de Evolución Gramatical que se presenta en esta Tesis), para resolver el mismo cometido, obteniendo otro tipo de distribuciones, y pudiendo realizar una comparativa de las arquitecturas. Por último, el uso de estimadores para el tiempo de aplicación y comunicación, y las variaciones en la topología de árbol de membranas que pueden producirse de forma no determinista con la evolución del P sistema, hace que se deba de monitorizar el mismo, y en caso necesario, realizar redistribuciones de membranas en procesadores, para seguir obteniendo tiempos de evolución razonables. Se explica, cómo, cuándo y dónde se deben realizar estas modificaciones y redistribuciones; y cómo es posible realizar este recálculo. Abstract Natural Computing is becoming a useful alternative to classical computational models since it its able to solve, in an efficient way, hard problems in polynomial time. This discipline is based on biological behaviour of living organisms, using nature as a basis of computation or simulating nature behaviour to obtain better solutions to problems solved by the classical computational models. Membrane Computing is a sub discipline of Natural Computing in which only the cellular representation and behaviour of nature is taken into account. Transition P Systems are the first abstract representation of membranes belonging to cells. These systems, which can be implemented in biological organisms or in electronic devices, are the main topic studied in this thesis. Implementations developed in this field so far have been studied, just to focus on distributed implementations. Such distributions are really important since they can exploit the intrinsic parallelism and non-determinism behaviour of living cells, only membranes in this case study. After a detailed survey of the current state of the art of membranes evolution and proposed algorithms, this work concludes that best results are obtained using an equal assignment of communication and rules application inside the Transition P System architecture. In order to define such optimal distribution, it is necessary to fully define the system, and each one of the elements that influence in its transition. Some changes have been made in the work of other authors: load distribution architectures, proxies definition, etc., in order to completely define the dynamic behaviour of the Transition P System. Starting from the static representation –initial configuration– of the Transition P System, distributions of membranes in several physical processors of a cluster is algorithmically done in order to get a better performance of evolution so that the computational complexity of the Transition P System is done in less time as possible. To build these distributions, the cluster architecture –or connection links– must be considered. The existence of 4 architectures, makes that the process of distribution depends on the chosen architecture, and therefore, although with significant similarities, the distribution algorithms must be implemented 4 times. Authors who proposed such architectures have studied the optimal time of each one. The non existence of membrane distributions for these architectures has led us to implement a dynamic distribution for the 4. Simulations performed in this work fix with the theoretical studies. There is not any deterministic algorithm that gets a distribution that meets the needs of the architecture for any Transition P System. Therefore, due to the complexity of the problem, the use of meta-heuristics of Natural Computing is proposed. First, Genetic Algorithm heuristic is proposed since it is possible to make a distribution based on the premise that along with evolution the individuals improve, and with the improvement of these individuals, also distributions enhance, obtaining complexity times close to theoretical optimum time. For architectures that preserve the tree topology of the Transition P System, it has been necessary to make new representations of individuals and new algorithms of crossover and mutation operations. From a more detailed study of the membranes and the communications among processors, it has been proof that the total time used for the distribution can be improved and individualized for each membrane. Thus, the same algorithms have been tested, obtaining other distributions that improve the complexity time. In the same way, using Particle Swarm Optimization and Grammatical Evolution by rewriting grammars (Grammatical Evolution variant presented in this thesis), to solve the same distribution task. New types of distributions have been obtained, and a comparison of such genetic and particle architectures has been done. Finally, the use of estimators for the time of rules application and communication, and variations in tree topology of membranes that can occur in a non-deterministic way with evolution of the Transition P System, has been done to monitor the system, and if necessary, perform a membrane redistribution on processors to obtain reasonable evolution time. How, when and where to make these changes and redistributions, and how it can perform this recalculation, is explained.

Evaluación de la calidad funcional y sensorial en cultivares de Triticum aestivum ssp. vulgare y ssp. spelta en cultivo ecológico

En esta Tesis Doctoral se ha estudiado la influencia del cultivar sobre el comportamiento reológico y panadero de cinco cultivares de trigo sembrados en el mismo año y en el mismo ambiente, en condiciones de cultivo ecológico. Tres de ellos eran de trigo panadero (Triticum aestivum ssp. vulgare), ‘Bonpain’, ‘Craklin’ y ‘Sensas’ y los otros dos de trigo espelta (Triticum aestivum ssp. spelta), ‘Espelta Álava’ y ‘Espelta Navarra’. Actualmente, el alohexaploide trigo panadero (2n=6x=42 genomio AABBDD) supone en torno al 90% del trigo cultivado en el mundo. En cambio, el cultivo del trigo alohexaploide espelta (2n=6x=42 genomio AABBDD) se limita a pequeñas regiones de Europa y de América del Norte. En España, el cultivo de trigo espelta se ha mantenido durante años ligado a la región de Asturias, aunque en la actualidad su cultivo está empezando a diversificarse hacia otras regiones. Esto se debe, fundamentalmente, a su potencial nutricional y a su adaptabilidad a condiciones de agricultura sostenible. El reciente resurgimiento de la espelta en productos de panificación, se debe, en gran parte, a la percepción del consumidor de que se trata de un producto ”más saludable” y “más natural” y con menor requerimiento de insumos que los trigos modernos. A medida que el consumo de alimentos a base de harina de espelta aumenta, se plantea la necesidad de evaluar su calidad harino-panadera, nutricional y sensorial en comparación con los productos elaborados con variedades de trigo común. Se caracterizaron las gluteninas de alto peso molecular (HMW) y las puroindolinas de los cinco cultivares. Se evaluó la calidad del grano, la reología de sus masas y se analizó la calidad instrumental y sensorial de sus panes. Para tal fin se ha puesto a punto un protocolo de panificación adecuado a las características particulares de los trigos espelta y se ha propuesto para el análisis sensorial de los panes un protocolo de selección, entrenamiento y validación de jueces. Teniendo en cuenta la composición en gluteninas HMW de los cultivares, se comprobó su influencia en el volumen de sedimentación y en la fuerza panadera. La composición en puroindolinas se vió reflejada en el parámetro dureza del endospermo. Los resultados indicaron que hay diferencias entre trigo panadero y trigo espelta en parámetros como, la tenacidad y el equilibrio de sus masas, la capacidad de absorción de agua de la harina y el comportamiento de la masa durante el amasado. Los trigos espeltas mostraron menor valor en el tiempo en alcanzar la presión máxima y la tolerancia al amasado, mientras que presentaron valores superiores en el decaimiento a los 250 y 450 segundos respectivamente. Respecto a la calidad de los panes elaborados, los trigos espeltas tenían mayor elasticidad en la miga y mayores valores en el área y en el diámetro de sus alveolos. Estas diferencias en la estructura y textura de la miga fueron también detectadas a nivel sensorial por el panel de jueces. Mediante el perfil sensorial descriptivo, se determinó que uno de los dos panes elaborado con trigo espelta (‘Espelta Navarra’) fue el pan más complejo considerando conjuntamente los atributos de aroma y flavor. En este trabajo no se apreciaron diferencias entre ambos tipos de trigo ni en el contenido en proteína, ni en minerales, ni en la viscosidad de su almidón. ABSTRACT In this Doctoral Thesis, the influence of various cultivars on rheological and baking behavior was studied. Five wheat cultivars were used, all planted in the same year and same organic farming environment. Three were bread wheat (Triticum aestivum ssp. vulgare), 'Bonpain', 'Craklin' and 'Sensas' and the other two were spelt wheat (Triticum aestivum ssp. spelta) , 'Espelta Álava' and 'Espelta Navarra' . Currently, the allohexaploid bread wheat (2n=6x=42 genome AABBDD) represents about 90% of global wheat production. On the other hand, allohexaploid spelt wheat (2n=6x=42 genome AABBDD) is merely produced in small areas of Europe and North America. For many years, the cultivation of spelt wheat in Spain was limited to the region of Asturias, although nowadays its production has begun to spread into other regions. This is owing to its nutritional potential and adaptability to conditions of sustainable agriculture. The recent resurgence of spelt in baking products is mainly due to consumers perception of it, as "healthier" and "more natural", and to the fewer agricultural input requirements compared to modern wheat products. As the consumption of foods made from spelt flour increases, there is a need to assess its baking, nutritional and sensory quality, compared to products made with common varieties of wheat. High molecular weight glutenins and puroindolines from the five cultivars were characterized. The quality of the grain and the rheology of the dough were evaluated and the instrumental and sensory quality of its breads were analyzed. To this end it a baking protocol was appropriately developed to the particular characteristics of spelt wheat and a selection protocol was proposed for the sensory analysis of breads, after proper training and validation of judges. Considering the HMW glutenin composition of the cultivars, the influence on the sedimentation volume and the baking strength was proven. The composition of puroindolines was reflected in the endosperm hardness parameter. The results show that there are differences between bread wheat and spelt wheat on parameters such as the tenacity and tenacity/elasticity ratio of their masses, the water absorption capacity of the flour and the behavior of the dough during kneading. The values for total time to reach maximum pressure and tolerance to mixing were lower for spelt wheat, and higher values were found for the drop at 250 s and 450 s. Regarding the quality of manufactured bread, spelt wheat had the greatest elasticity of the crumb and higher values in the area and diameter of the cells. These differences in the structure and texture of the crumb were also noticed at a sensory level by the panel of judges. It was determined by a descriptive sensory profile that one of the two loaves of bread made with spelt ('Espelta Navarra') was the most complex in the sense of its attributes of scents and flavors altogether. In this study, no differences were appreciated between the two types of wheat or the protein composition, or minerals or viscosity of the starch.