What does partition do?

[MahdiNazemi]

I have written a top-level function which calls a few helper functions in order to implement an algorithm. Based on https://github.com/ysshao/ALADDIN/issues/7, I added every function's name to the WORKLOAD variable. However, I haven't partitioned any of my 1D or 2D arrays. Can you please explain what partitioning does (cyclic in particular)? What is the benefit of doing it?

The reason I am asking this question is that I get the following error when I start the simulation Unknown partition : m@inst: 9 and I guess it has something to do with the partitioning.

Excuse me if the question is trivial. I am not from the architecture community and not very familiar with low-level details.

Thanks, Matt

[xyzsam]

Hi Matt,

Thanks for your questions. A few clarifications:

1. You don't need to add every function to WORKLOAD anymore. If there's just one function in WORKLOAD, LLVM-Tracer assumes it is the top level one and will trace every function called by that function.
2. There are several reasons why you could be getting that error, but the most common is that you didn't declare m in your Aladdin configuration file. If m is a function argument of your top level function or is declared inside the top level function, this is required.

Sam

[MahdiNazemi]

Hi Sam,

Thanks a lot for your prompt reply. m was in fact the function parameter of one of the helper functions. Now that I have removed the helper functions from WORKLOAD, I get a similar error for the arrays declared inside the top level function.

Can you please explain why this is required? A pointer to a paper or an article would be great.

The reason I am asking this is that I partitioned all the necessary arrays to registers, but I get a segmentation fault when scheduling begins. I would like to know if partitioning can affect scheduling.

[xyzsam]

Partitioning absolutely affects scheduling - the more you partition an array, the more memory bandwidth you are provisioning for your accelerator, and more concurrent memory accesses leads to faster execution (which means a different schedule).

You have to declare the arrays in the configuration file because that's how Aladdin knows about them in the first place. All of the fields are important - name, size, word size, and partitioning factor - and getting one of them wrong could potentially lead to unexpected behavior.

As a side note, generally, you only want to partition very small arrays completely into registers, as they are much more expensive to build than SRAMs.

For more information, I suggest you read the original Aladdin paper.

[MahdiNazemi]

Thanks a lot for your thorough explanation. I had read the paper a couple of times, but I still had issues understanding partitions. I guess the concept is clear now.

By the way, the reason for segmentation fault was loop unrolling configuration. It looks like I have to explicitly mention loop unrolling factor even if I do not want to unroll any of the loops (unroll once).

[xyzsam]

Yes, that is correct. Aladdin's loop unrolling optimization is actually a loop rolling operation, because we start with the idealistic DDDG that only has true memory dependences, so at the beginning, all loops are completely unrolled (aka flattened). In order to model loop unrolling, we then add additional dependences to the loops. So if you don't mention loop unrolling for a loop, then Aladdin wouldn't know that loop exists at all, and then that loop would remain flattened - it's not so trivial to set a default to 1 because we don't know a priori where all the loops are in the dynamic trace to begin with.