Re: [GridSim-developers] [GridSim-users] simulation fails(OOME)with 1000 resources

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Hi Alex,

 > So do you mean that the monster that eats up all JVM memory is the  
event
 > queue containing close to 1 million events?

No, I am not saying that. That's because there are other things in  
GridSim that may be using too much memory. You are right about the  
thread pool for example. I don't think that the way simjava manages  
the threaded entities is ideal either. For example, at each clock  
tick Sim_system scans the future event queue and puts all events with  
the same time either in the deferred queue or in the buffer of the  
entities:

// If there are more future events then deal with them
if (future.size() > 0) {
	queue_empty = false;
	Sim_event first = future.pop();
	process_event(first);
	// Check if next events are at same time...
	boolean trymore = (future.size() > 0);
	while (trymore) {
		Sim_event next = future.top();
		if (next.event_time() == first.event_time()) {
			process_event(future.pop());
			trymore = (future.size() > 0);
		} else
			trymore = false;
		}
	}
}

After that, in the next clock tick Sim_system will restart all  
threads and let them process the events in the deferred queue. I am  
just wondering what would happen on a multi-core machine when all  
entities are and they race to process events. I mean, although there  
are some synchronisations, I don't know in which order the entities  
will process the events:

int entities_size = entities.size();
for (int i=0; i < entities_size; i++) {
    ent = (Sim_entity)entities.get(i);
       if (ent.get_state() == Sim_entity.RUNNABLE) {
	ent.restart();
	num_started++;
       }
  }

Regarding the use of memory, GridSim 4.1 had a small bug in the  
Workload/Gridlet class:

http://sourceforge.net/tracker/index.php? 
func=detail&aid=1871718&group_id=94592&atid=608392

Which means that by default each Gridlet came with a StringBuffer of  
1000 bytes to store the history of the job. In the simulations I have  
been performing, I simulate 2 months in which a Grid with 5 clusters  
processes approximately 92,000 jobs. In that case, I would need close  
to 92MB of RAM only to store the information about the jobs.

 > It seems that your library is more efficient. Have you tested it  
against
 > the original one? Would you like to share your modified simjava2  
library
 > such that we can all benefit?

As simjava does not iterate much of the event queue at each clock  
tick, a TreeSet does a good job. I have put the modified version of  
simjava at www.cs.mu.oz.au/~marcosd/files/simjava.zip

Also, I have a branch (branch 3) of GridSim at sourceforge where a  
created a different monster to eat memory. I have stripped a few  
things from simjava and worked with ranges of processing elements and  
availability profiles for the resources instead of having one PE  
object for each processing element in a  resource. The source code is  
available at branch 3. Moreover, In the version I am using I have  
made other changes to Simjava/GridSim which are not there in the  
sourceforge. Basically, I have converted the simulation times to  
longs, made simjava single threaded (with the provision to use a  
thread pool) and created a data structure for managing PEs which can  
be used to create other allocation policies. However, I am cannot  
make this available right now because I will need to document it first.

We would be happy to know your thoughts about GridSim or any changes  
you might have made to it. I think we can improve the tool, this way.

Regards,

Marcos

On 23/09/2008, at 10:38 PM, Shuo Yang wrote:

> Dear Marcos,
>
> Many thanks for your reply and contribution.
>
> So do you mean that the monster that eats up all JVM memory is the  
> event
> queue containing close to 1 million events?
>
> It seems that your library is more efficient. Have you tested it  
> against
> the original one? Would you like to share your modified simjava2  
> library
> such that we can all benefit?
>
>
> Alex
>
> On Tue, 2008-09-23 at 15:11 +1000, Marcos Dias de Assuncao wrote:
>> Hi Shuo,
>>
>> I was cleaning my inbox after a few days without reading e-mails and
>> found this one. :-)
>>
>> I have made some changes in SimJava because I also face some problems
>> about scalability. As discussed beforehand, GridSim uses SimJava 2.
>> The event queue in SimJava 2 is a linked list:
>>
>> public class Evqueue extends LinkedList
>>
>> Also, please note that when an event is inserted in the queue,
>> SimJava does only a silly optimisation. That is, an Evqueue instance
>> maintains an attribute called max_time, which is the time of the last
>> event that would be processed. Evqueue will not iterate the list when
>> it adds an event to the queue only if the event's time is greater
>> than max_time:
>>
>> public void add_event(Sim_event new_event) {
>>   double new_event_time = new_event.event_time();
>>      if (new_event_time >= max_time) {
>>        add(new_event);
>>        max_time = new_event_time;
>>        return;
>>      }
>>      ListIterator iterator = listIterator();
>>      Sim_event event;
>>      while (iterator.hasNext()) {
>>        event = (Sim_event)iterator.next();
>>        if (event.event_time() > new_event_time) {
>>          iterator.previous();
>>          iterator.add(new_event);
>>          return;
>>        }
>>      }
>>      add(new_event);
>> }
>>
>> You can see what is going to happen if things in the simulator are
>> not managed properly. If you consider the Workload class for example,
>> it reads a job trace file and creates job submissions (events)
>> according to this trace. If you have only one Workload entity in your
>> simulation creating events and reading, let's say, 1000 jobs, you
>> will have 1000 events in the future queue right when you start the
>> simulation. Also, consider that one of these jobs is to be submitted
>> (i.e. received by the resource) far in the future. All events created
>> from the start until the end of the simulation (i.e. job completion,
>> internal messages, packets, etc) will probably lead to the iteration
>> of the event queue because of one event that was created at the start
>> of the simulation and changed max_time. If you are simulating a Grid,
>> it is very likely that you will have multiple Workloads dispatching
>> jobs, changing max_time and making one another's events to iterate
>> the queue. The deferred event queue is not a problem because you will
>> hardly have a very long deferred queue.
>>
>> In some simulations I have run, the future event queue can contain
>> close to 1 million events at a particular time. This way, I've
>> changed the future event queue to use a modified version of TreeMap.
>> TreeMaps are quicker to insert an object into, but one may argue that
>> they are costly to iterate. In that sense, I modified the Java's
>> implementation of TreeMap to keep a double linked list between the
>> siblings nodes. This way, the iterator uses the list to iterate and
>> not the java's red-black tree.
>>
>> Moreover, the event  this is not the only scalability issue of
>> SimJava. Each simulation entity is a Thread and SimJava puts them to
>> wait and notifies entities at each clock tick, that is, each time the
>> simulation clock is changed.
>>
>> Regards,
>>
>> Marcos
>>
>>
>> On 06/09/2008, at 12:55 AM, Shuo Yang wrote:
>>
>>> All,
>>>
>>> I think the problem also lies in the scalability of the underlying
>>> simjava
>>> package. Simjava uses an event queue to manage all internal events
>>> flying
>>> between entities. The event queue is a Vector. If you refer to
>>> eduni.simjava.Evqueue.java, you can see the doc:
>>>
>>> /**
>>>  * This class implements an event queue used internally by the
>>> Sim_system to
>>>  * manage
>>>  * the list of future and deferred Sim_events. It should not be
>>> needed in
>>>  * a user simulation. It works like a normal FIFO
>>>  * queue, but during insertion events are kept in order from the
>>> smallest
>>> time
>>>  * stamp to the largest. This means the next event to occur will be
>>> at the
>>> top
>>>  * of the queue. <P>
>>>  * The current implementation
>>>  * is uses a Vector to store the queue and is inefficient for  
>>> popping
>>>  * and inserting elements because the rest of the array has to be
>>>  * moved down one space. A better method would be to use a circular
>>> array.
>>>  * @see		eduni.simjava.Sim_system
>>>  * @version     0.1, 25 June 1995
>>>  * @author      Ross McNab
>>>  */
>>>
>>> Also, the event queue in Sim_system is accessed using
>>> 'synchronized' to
>>> ensure consistency and the simulation clock. Therefore when there
>>> are a huge
>>> amount of entities/messages, the event queue becomes the system
>>> bottleneck -
>>> only one entity/thread can write to event queue while the others
>>> will wait,
>>> and wait, and wait, and wait...
>>>
>>> It may have problem with java's handling large memories. But a re-
>>> design and
>>> re-implemenation of the underlying thread pool is ideal, which is
>>> exactly
>>> what I'm doing now.
>>>
>>> Cheers,
>>>
>>> Shuo 'Alex' Yang
>>> University of Manchester
>>>
>>>
>>> ----- Original Message -----
>>> From: "Agustín Caminero Herráez" <ag...@ds...>
>>> To: "ye" <hua...@gm...>
>>> Cc: <gri...@li...>;
>>> <gri...@li...>
>>> Sent: Friday, September 05, 2008 3:35 PM
>>> Subject: Re: [GridSim-developers] [GridSim-users] simulation fails
>>> (OOME)with
>>> 1000 resources
>>>
>>>
>>> Hi Ye,
>>>
>>> I've also suffered the problems u describe, and I'm afraid there  
>>> is no
>>> solution for them. The only suggestion I can give to u is to scale
>>> down
>>> your simulations.
>>>
>>> The problem comes from Java's inability to handle more than 1.5  
>>> GB of
>>> memory, so there is nothing u can do.
>>>
>>> Just one thing, are u using Sun Java? Because using another  
>>> different
>>> java may cause problems... The java I us is Sun  v1.4.2
>>>
>>> Regards,
>>>
>>> Agustin
>>>
>>> ye escribió:
>>>> Hi, Dear all:
>>>> Although I have asked a similar question in gridsim-user maillist,
>>>> there seems no similar experience from other developers. Since
>>>> it's an
>>>> crucial problem for me, I'd to make the scenario much clear and beg
>>>> for help.
>>>>
>>>> For brief, is there any scale limit for simulation created via
>>>> GridSim?
>>>>
>>>> I was trying to set up a gridsim simulation with 1000 resource;  
>>>> each
>>>> resource contains one machine, each machine has two PEs. Then, I
>>>> wrote
>>>> a user to retrieve resource list within its body(), and print the
>>>> total size. However, the program halts with an OutOfMemoryError,
>>>> every
>>>> time before "Entities started" was printed. The user's body() was
>>>> never visited.
>>>>
>>>> I am working on a mac 10.5, 2GB 667 Mhz memory, mac JVM 1.5;
>>>> meanwhile, I already adjust the vm parameter into "-Xms512m -
>>>> Xmx1024m".
>>>>
>>>> Later, I tried the same program on my server (ubuntu 8.04, 3.2GB).
>>>> Fortunately, it works... but, it halts again with OOME while i  
>>>> decide
>>>> create 1100 resources.
>>>>
>>>> I am not sure the problem is caused by lacking of memory? Is there
>>>> any
>>>> limit for gridsim simulation scale, or just for GridSim  
>>>> Resource? Or
>>>> it's bug derived from simjava?
>>>>
>>>> Finally, is it possible to solve it?
>>>>
>>>> Thank you guys a lot!!
>>>>
>>>> regards
>>>> ye
>>>>
>>>> -- 
>>>> Ye Huang, Department of Informatics
>>>> University of Fribourg / Pérolles 2 - Bld de Pérolles 90
>>>> 1700 Fribourg, Switzerland
>>>>
>>>> e-mail: ye....@he..., ye....@un...
>>>> http://diuf.unifr.ch/people/huangy/
>>>> Office: +41 26 429 65 95
>>>> ------------------------------------------------------------------- 
>>>> --
>>>> ---
>>>>
>>>> ------------------------------------------------------------------- 
>>>> --
>>>> ----
>>>> This SF.Net email is sponsored by the Moblin Your Move Developer's
>>>> challenge
>>>> Build the coolest Linux based applications with Moblin SDK & win
>>>> great
>>>> prizes
>>>> Grand prize is a trip for two to an Open Source event anywhere  
>>>> in the
>>>> world
>>>> http://moblin-contest.org/redirect.php?banner_id=100&url=/
>>>> ------------------------------------------------------------------- 
>>>> --
>>>> ---
>>>>
>>>> _______________________________________________
>>>> Gridsim-users mailing list
>>>> Gri...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/gridsim-users
>>>>
>>>
>>> -- 
>>> ===============================================
>>> Agustin Caminero
>>> Research Assistant.
>>> Computing Systems Department.
>>> Albacete Research Institute of Informatics (I3A).
>>> The University of Castilla La Mancha.
>>> Campus Universitario s/n, 02071, Albacete. Spain.
>>> Phone: +34 967 599 200 Ext. 2693. Fax: +34 967 599 343
>>> http://www.i3a.uclm.es/
>>> ===============================================
>>>
>>>
>>>
>>>
>>> -------------------------------------------------------------------- 
>>> --
>>> ----------
>>>
>>>
>>>> ------------------------------------------------------------------- 
>>>> --
>>>> ----
>>>> This SF.Net email is sponsored by the Moblin Your Move Developer's
>>>> challenge
>>>> Build the coolest Linux based applications with Moblin SDK & win
>>>> great
>>>> prizes
>>>> Grand prize is a trip for two to an Open Source event anywhere  
>>>> in the
>>>> world
>>>> http://moblin-contest.org/redirect.php?banner_id=100&url=/
>>>
>>>
>>> -------------------------------------------------------------------- 
>>> --
>>> ----------
>>>
>>>
>>>> _______________________________________________
>>>> Gridsim-developers mailing list
>>>> Gri...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/gridsim-developers
>>>>
>>>
>>>
>>> -------------------------------------------------------------------- 
>>> --
>>> ---
>>> This SF.Net email is sponsored by the Moblin Your Move Developer's
>>> challenge
>>> Build the coolest Linux based applications with Moblin SDK & win
>>> great prizes
>>> Grand prize is a trip for two to an Open Source event anywhere in
>>> the world
>>> http://moblin-contest.org/redirect.php?banner_id=100&url=/
>>> _______________________________________________
>>> Gridsim-users mailing list
>>> Gri...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gridsim-users
>>
>> Marcos Dias de Assuncao
>> Grid Computing and Distributed Systems (GRIDS) Laboratory
>> Department of Computer Science and Software Engineering
>> The University of Melbourne, Australia
>> Email: ma...@cs...
>>
>> -------------
>> "No serious sociologist any longer believes that the voice of the
>> people expresses any divine or specially wise idea. The voice of the
>> people expresses the mind of the people, and that mind is made up for
>> it by the group leaders in whom it believes and by those persons who
>> understand the manipulation of the public opinion. It is composed of
>> inherited prejudices and symbols and cliché's and verbal formulas
>> supplied to them by the leaders."
>> Edward L. Bernays
>>
>

Marcos Dias de Assuncao
Grid Computing and Distributed Systems (GRIDS) Laboratory
Department of Computer Science and Software Engineering
The University of Melbourne, Australia
Email: ma...@cs...

-------------
"No serious sociologist any longer believes that the voice of the  
people expresses any divine or specially wise idea. The voice of the  
people expresses the mind of the people, and that mind is made up for  
it by the group leaders in whom it believes and by those persons who  
understand the manipulation of the public opinion. It is composed of  
inherited prejudices and symbols and cliché's and verbal formulas  
supplied to them by the leaders."
Edward L. Bernays