Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » VIATRA » Exploding Recursive Pattern(Why does the network of this pattern explode?)
Exploding Recursive Pattern [message #1833185] Tue, 06 October 2020 06:02 Go to next message
Hans van der Laan is currently offline Hans van der LaanFriend
Messages: 34
Registered: February 2020
Member
Hey,

I'm having some scaling issues. Although my VIATRA-based solution works for small examples, when I try to load realistically sized models my computer fan starts to sound like an indoor-hurricane and VIATRA slowly but steadily eats my RAM before giving an "out of memory exception".

Luckily, I managed to find the culprit. I have recursive patterns which deals with reachability of which 2 Rete nodes explode. Unfortunately, I don't exactly know why they explode. I think it's because there is something about recursive graph patterns I do not know/understand.

The pattern:
pattern SecurityZoneAccessible( user: User, scenario: MyScenario, zone: SecurityZone) {
	SecurityZone.public(zone, true);
	find SecurityZoneAccessStatus(scenario, zone, 0);
	User(user);
} or {
	find USO(user, scenario, zone);
	SecurityZone.public(zone, true);
	find SecurityZoneAccessStatus(scenario, zone, 1);
} or {
	find SecurityZoneAccessStatus(scenario, zone, 0);
	SecurityZone.reachable(prev,zone);
	find SecurityZoneAccessible(user, scenario, prev);
} or {
	find USO(user, scenario, zone);
	find SecurityZoneAccessStatus(scenario, zone, 1);
	SecurityZone.reachable(prev,zone);
	find SecurityZoneAccessible(user, scenario, prev);
}


The network:
https://i.imgur.com/S0rF595.png
(original)


Does anyone know why these nodes blow up and how I could restructure my pattern as to prevent this blow up? In the case that this is because of recursive graph patterns, is there any resource I should read to better understand recursive graph patterns as to prevent these mistakes in the future?

Re: Exploding Recursive Pattern [message #1833379 is a reply to message #1833185] Mon, 12 October 2020 06:22 Go to previous messageGo to next message
Hans van der Laan is currently offline Hans van der LaanFriend
Messages: 34
Registered: February 2020
Member
I thought up of a work around this weekend! If I restructure the pattern like this, there is no underwater blow-up of one of the Rete nodes.

pattern SecurityZoneAccessible(user: User, scenario: MyScenario, zone: SecurityZone) {
	SecurityZone.public(zone, true);
	find SecurityZoneAccessStatus(scenario, zone, 0);
	User(user);
} or {
	find USO(user, scenario, zone);
	SecurityZone.public(zone, true);
	find SecurityZoneAccessStatus(scenario, zone, 1);
} or {
	find SecurityZoneAccessible(user, scenario, prev);
	find Foo(user, scenario, prev, zone);
} 

pattern Foo(user: User, scenario: MyScenario, prev: SecurityZone, zone: SecurityZone) {
	User(user);
	find SecurityZoneAccessStatus(scenario, zone, 0);
	SecurityZone.reachable(prev,zone);
} or {
	SecurityZone.reachable(prev,zone);
	find SecurityZoneAccessStatus(scenario, zone, 1);
	find USO(user, scenario, zone);
}



Re: Exploding Recursive Pattern [message #1833408 is a reply to message #1833379] Mon, 12 October 2020 13:10 Go to previous messageGo to next message
Zoltan Ujhelyi is currently offline Zoltan UjhelyiFriend
Messages: 392
Registered: July 2015
Senior Member
Hi Hans,

sorry for not sending my answer last week, I have started to write the answer multiple times, but I did not have time to finish it, but I am happy that you have managed to figure out a better way to formalize your patterns. My recommendation would have been along the lines you have found. For future reference (and possibly as an explanation) I will include my reasoning:

The part that seems to blow up is the left join operator in the 7th row from the bottom, where its inputs are 2964 and 626 tuples long, while after the join we have 927894 tuples then trimming it reduces the number of matches. If I understand the network correctly, this relates to the third body:

find USO(user, scenario, zone);
find SecurityZoneAccessStatus(scenario, zone, 1);
SecurityZone.reachable(prev,zone);
find SecurityZoneAccessible(user, scenario, prev);

Here the match set of the SecurityZoneAccessible pattern is joined to the SecurityZoneAccessStatus which seems really expensive - and it also makes sense to me as joining the status with the accessibility results seems close to some kind of . What I'd suggest is to help the planner to find out that it is better to filter the output of these patterns _before_ joining them together. Such ordering can be enforced by the creation of helper patterns that reduce the number of elements in one (or both) end of the join operator (something like your foo pattern).

This approach of ordering the query execution is general in the sense that in case you create a pattern the Rete network has to be constructed in a way that it's solution has to be available so you reduce the freedom of the planner to avoid problematic structures as you have seen.

Nonetheless, if your original case is available in a reproducible form, it might be interesting to see why has the Rete planner decided on a suboptimal pattern. However, don't put a lot of effort of creating a reproducible example (that might depend on the models as well), as I cannot promise when we will have time to have a more detailed look at it.

Best regards,
Zoltán
Re: Exploding Recursive Pattern [message #1833412 is a reply to message #1833408] Mon, 12 October 2020 13:54 Go to previous message
Hans van der Laan is currently offline Hans van der LaanFriend
Messages: 34
Registered: February 2020
Member
Hey Zoltán,

Thank you for your explanation. It makes it much clearer what was happening!

Quote:
Nonetheless, if your original case is available in a reproducible form, it might be interesting to see why has the Rete planner decided on a suboptimal pattern. However, don't put a lot of effort of creating a reproducible example (that might depend on the models as well), as I cannot promise when we will have time to have a more detailed look at it.


I'm planning to release my VIATRA-based solution as well as the model(s) along side my master thesis. Thus, it's not too much effort for me to also make a small reproducible example of this blow up. However, I think will not come around to this until after I've finished my thesis.

Kind regards,

Hans
Previous Topic:Initial Rete Network Construction
Next Topic:Deep Copy of Engine, Resource and Pattern Matches
Goto Forum:
  


Current Time: Wed Nov 06 03:09:43 GMT 2024

Powered by FUDForum. Page generated in 0.03032 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software

Back to the top