Sevilla Carpets ======================= Introduction ------------ Sevilla Carpets were first presented in the **First Brainstorming Week on Membrane Computing** (see `proceedings `_) as a tool to describe somehow the size of a computation in a P system. They provide an extension of the notion of the Szilard language from grammars to the case when several rules (computing agents) are used (active) at the same time. This leads to a two-dimensional **carpet** which indicates the *used rules per step of computation*, thus evaluating the space-complexity of the computation. More details in *Sevilla Carpets Associated with P systems*, included in the indicated url. Sevilla Carpets Revisited: Enriching the Membrane Computing Toolbox ------------------------------------------------------------------- Sevilla Carpets have already been used to compare different solutions of the Subset Sum problem: either designed in the framework of P systems with active membranes and in the framework of tissue-like P systems with cell division. Recently, the degree of parallelism and other descriptive complexity details have been found to be relevant when designing parallel simulators running on GPUs. A new work will be presented soon providing a new way to use the information provided by Sevilla carpets, but for the time being we provide here a script that allows to generate them automatically from P-Lingua files. Sevilla carpets can **run directly** outside MeCoSim by following the instructions in section :ref:`running_out`. As a result of running Sevilla Carpets option for a given instance of a problem a carpet as the following is shown: .. image:: images/sevilla_carpet_sat.jpg :width: 50% :align: center This script can also be easily **integrated with MeCoSim** by providing some settings to one of the pre-existing plugins. Please find the instructions below in section :ref:`running`. .. _running_out: Running (outside MeCoSim) ------------------------- .. container:: boldlink 0. Preconditions (they should be properly installed, with their paths in PATH environment variable): * **Python** (can be downloaded `here `_). * **gnuplot** (available in this `url `_). 1. Download Sevilla Carpets files: * Executables: * [:download:`Windows`] [:download:`Linux`]. * :download:`Examples`. 2. Run command *./sevilla_carpets.sh myexample.pli*, from Linux, or *sevilla_carpets.bat myexample.pli* from Windows, for a given example *myexample.pli*. .. Make sure executable files sevilla_carpets.sh, plingua_sim and simu_a_puntos.py have execution permission (if not, type *chmod +x myfile* in order to give that permission to each file). .. _running: Running with MeCoSim -------------------- After performing steps 0 and 1 above... .. container:: boldlink 2. [**Install** `MeCoSim `_] *if not installed*. 3. [Run MeCoSim and **install MeCoSim Processes plugin**] *if not installed* (from MeCoSim main window, Settings > Manage repositories > Plugins, first rep. in combo box (*http://www.p-lingua.org/mecosim/jnlp/plugins*) then ProcessesPlugin in the list and press install or double click. 4. Close MeCoSim, and set properties for running Sevilla Carpets as a plugin: * Download **Properties** file: [:download:`Windows`] [:download:`Linux`], and copy and paste contents at the end of plugins-properties file inside **prop** folder of MeCoSim. * :download:`Examples`, ready to unzip anywhere and use it with the default general app of MeCoSim. 5. Run MeCoSim, run "General" app inside MeCoSim, select the model in menu **Model > Set Model**, [optional: if you want to simulate, set **Simulation > Options > number of cycles > 0** in order to simulate until a halting condition is reached], and go to menu Plugins > Sevilla Carpets. About the examples... --------------------- In section :ref:`running_out` some P-Lingua examples are provided: .. container:: boldlink * **SAT** (sat.pli): solving SAT problem for an instance <6,4> (6 clauses and 4 variables) * [Pérez-Jiménez, M.J.; Romero-Jiménez, A.; Sancho-Caparrini, F. A Polynomial Complexity Class in P systems Using Membrane Division, in E. Csuhaj–Varjú, C. Kintala, D.Wotschke, and Gy. Vaszyl (eds.), *Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems*, Budapest, Hungary, 2003, 284–294.] * **Knapsack** (knapsack.pli): solving Knapsack problem for an instance <4,8,20> (n=4, k=8, c=20) * [Pérez-Jiménez, M.J.; Riscos-Núñez, A. A Linear Solution for the Knapsack Problem Using Active Membranes. *Lecture Notes in Computer Science*, 2933 (2004), 250–268.] * **Partition** (partition.pli): solving Partition problem for an instance <4> (n=4) * [Gutiérrez-Naranjo, M.A.; Pérez-Jiménez, M.J.; Riscos-Núñez, A. A Fast P System for Finding a Balanced 2-Partition, *Soft Computing*, 9(9), (2005) 673–678.] * **Subset sum** (subsetsum.pli): solving Subset Sum problem for an instance <7,8> (n=7, k=8) * [Pérez-Jiménez, M.J.; Riscos-Núñez, A. Solving the Subset Sum Problem by Active Membranes, *New Generation Computing*, 23 (4), 2005, 367-384.] A different kind of example can be useful to study problems that seem more sound to be performed in parallel technologies: .. container:: boldlink * **GPU test** (gputest.pli): an example creating a number of objects inside a membrane, all of them with an associated rule to be replaced by themselves every step, and other rule implying the divission of the membrane containing these kind of objects. Thus, every step we double the number of membranes and objects, thus creating an exponential number of elements in linear time. * In this case, simulation does not halt, so we need to state the number of steps to simulate: * In Windows, in **sevilla_carpets.bat**: *java -jar plinguacore.jar plingua_sim -PLI %1 -o tmp/salida* should include *-st 10* at the end, given we want to run 10 steps. * In Linux, in **sevilla_carpets.sh**: *./plingua_sim -PLI $1 -o tmp/salida* should include *-st 10* at the end, given we want to run 10 steps. Plotting considerations ----------------------- * Plotting instructions are given inside **plotter** file inside executables zip. * Default options state **set dgrid3d 100, 100** to state the number of rows and columns in the graph generated by gnuplot. However, this graph can be easily improved by changed this instruction for each particular case, setting **set dgrid nrules, nsteps**, with *nrules* the number of rules in the system and *nsteps* the number of steps to reach the halting configuration. This values can be obtained by running a simulation by means of P-Lingua or by MeCoSim. * The previous command has an optional third parameter to normalize the results, avoiding some default behaviour of gnuplot. This parameter could be set for instance to 10, thus getting **set dgrid3d 169, 53, 10** for an instance of a problem resulting in a computation of 53 steps, with 169 rules being executed, and a norm of 10. **More info** at `this url `_.