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 Running (outside MeCoSim).
As a result of running Sevilla Carpets option for a given instance of a problem a carpet as the following is shown:
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 Running with MeCoSim.
Running (outside MeCoSim)¶
Run command ./sevilla_carpets.sh myexample.pli, from Linux, or sevilla_carpets.bat myexample.pli from Windows, for a given example myexample.pli.
Running with MeCoSim¶
After performing steps 0 and 1 above...
[Install MeCoSim] if not installed.
[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.
- Close MeCoSim, and set properties for running Sevilla Carpets as a plugin:
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 Running (outside MeCoSim) some P-Lingua examples are provided:
- 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:
- 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.
