help with algorithm

[electroRF]

Hi,
In my uC, I got 3 virtual memory banks.

Every time me and my colleagues add code or data to the project, we must map each code/data to a certain memory bank (we of course sometimes remove data/code to spare in memory).

Every few days, we combine all our additions / changes / removals, and we sometimes fail at linker stage since one (or more) of the memory banks cannot contain the entire code and/or data that were added.

I'd like to write a script which will see how much a certain memory bank is overfilled, and edit the mapping done in the source files so some code / data will be transferred to an available memory bank.

the main challenge is that the code / data are united into different groups.
So that actually the script will move groups.
That is a challenge because it'd make it harder for the script to find the exact amount of data/code it needs to transfer from an overfilled memory bank to an available memory bank.

Given to the script are:
- how much space is available in each memory bank (or how much a memory bank is overfilled), and their total size
- Size of each function / variable and where it's mapped

My goal is to:
- Move code / data from the overfilled Memory Bank(s) to the available Memory Banks in a way that they would be somewhat balanced.

For example, given to the script:
Bank A, size of 1MB, overfilled with 300KB
Bank B, size of 2MB, has an available 250KB
Bank C, size of 3MB, has an available 400KB

I'd ideally like to move 300KB from Bank A to Bank B and 100KB from Bank A to Bank B, in order to get a balanced result:

script's output:
Bank A --> Available 100KB
Bank B --> Available 150KB
Bank C --> Available 100KB

I'd love to hear guidelines or tips from you how to accomplish a balanced memory.

Thank you.


***
Currently, the Algorithm which I thought of is:
1. Find the Memory Bank which is overfilled
2. Find the Memory Bank which has the highest available amount of Memory
3. Balance these two Memory Banks equally (as possible)
4. Go back to 1) in case there was more than one bank which failed, and repeat the process.

In the case of the example I brought, it'd move 350KB from Bank A to Bank C, which would give a not-so-balanced memory result:
Bank A --> Available 50KB
Bank B --> Available 250KB
Bank C --> Available 50KB

 

[Ian Rogers]

Why not just learn C.... Problem solved..

What uC is it anyway...

 

[electroRF]

I did not understand your comment.

It's all written in C.

Forgive me, it's company's internal uC, which I cannot specify.

 

[nsaspook]

It sounds to me you guys just need to talk to each other more than once every few days. More code design instead of code writing. Your script idea is just hiding a problem.

 

[electroRF]

It sounds to me you guys just need to talk to each other more than once every few days. More code design instead of code writing. Your script idea is just hiding a problem.

Hi,
This is a company, consists of tens of developers, therefore it'd make it impossible.

 

[NorthGuy]

I find it very strange that people need to assign their code to some memory banks and then a script needs to re-assign them. If script can do it, why people should ever bother about banks? This makes things difficult for both the script and the people.

If it is all totally proprietary, why not to modify the linker so that it assigns memory banks automatically? This would save a lot of work for people and would eliminate the need for the script.

I look at your posts about this proprietary controller, and whatever you mention about it, it strikes me as really bad design (memory banks in this case). I admire people who design their own chips because they want them better than what's available on the shelf. However, when they design their own chips and make them worse than cheap mainstream choices such as ARM, this looks totally backards to me.

 

[nsaspook]

Hi,
This is a company, consists of tens of developers, therefore it'd make it impossible.

What do you use for collaboration? Git is a nice system to handle projects like yours. https://git-scm.com/

 

[electroRF]

Hi NorthGuy,

You're right that we can modify the linker to do it, but I'd actually prefer to do it myself instead of assigning it to others.

Therefore, I raised it up here, and NorthGuy I'd actually love to hear how you'd accomplish such script, I mean what algorithm would you use?

Thanks a lot.

 

[Ian Rogers]

I find it very strange that people need to assign their code to some memory banks and then a script needs to re-assign them. If script can do it, why people should ever bother about banks? This makes things difficult for both the script and the people.

If it is all totally proprietary, why not to modify the linker so that it assigns memory banks automatically? This would save a lot of work for people and would eliminate the need for the script.

I look at your posts about this proprietary controller, and whatever you mention about it, it strikes me as really bad design (memory banks in this case). I admire people who design their own chips because they want them better than what's available on the shelf. However, when they design their own chips and make them worse than cheap mainstream choices such as ARM, this looks totally backards to me.

Spot on! This is why I assumed you were using a low level assembler..... If you are purposely splitting memory banks, it doesn't seem logical for a higher level coder... The idea of high level is to get away from this.... The MALLOC library is designed especially so you can dynamically sort out the memory for your application..

 

[NorthGuy]

I would just say: "Guys. Good news for you. You do not need to specify bank assignments any more. Because I'm going to throw these assignments away anyway and assign the banks with my script (modified liker) as I please. And, hey, don't I deserve a 10% raise for that?"

 

[kubeek]

I think you got two options:
If you are allocating dynamically i.e. using malloc, then you need to change the way it allocates the memory to work better.
However since you are talking about a script that somehow changes the code before it is compiled, then I suppose all the memory requirements are fixed, such as with arrays and variables. Then your script would have to parse the C files, decide somehow what to put where, and then rearrange the code such that the banks are used evenly. Now, mix in the unknown overhead of bank switching, and you got a whole another can of worms if you want the resulting code to be reasonably efficient. Might be better to write the code properly and account for the banks by yourself.
EDIT: either the script, or modify the compiler to assign the banks as it pleases and get rid of the banking in the code alltogether.

On a different note: You say there are tens of developpers in your company, yet you are trying to single-handedly crack a problem like this. Are your superiors aware of the problems you encounter? Are they even trying to solve them, or just say Nah I don't care?
I'd love to know why in the world are you banking the memory in the first place, what is the rationale behind that decision?
And also out of curiosity I'd love to know if this some kind of soft core for an FPGA, or if this is going to be produced in ASIC chips, if you can share that kind of info?

 

[misterT]

the main challenge is that the code / data are united into different groups.
So that actually the script will move groups.
That is a challenge because it'd make it harder for the script to find the exact amount of data/code it needs to transfer from an overfilled memory bank to an available memory bank.

Well, that sucks.. change to more modern microcontroller and toolchain.. problem solved.

 

[misterT]

I re-read the original post.. and still.. that is some messed up s**t.
My advice: "Back to the future".

 

[electroRF]

Hi guys.

The problem for the script to solve is simple.

I'd love to write this script since it'd be my way to get into C++ & C# and not write only C, so please respect my choice.

I described below the problem and wrote my question please.

The Script already gets the following inputs from the compiler & linker in a file they provide the script with:

1. how much space is available in each memory bank (or how much a memory bank is overfilled), and their total size --- There are 3 Memory Banks

2. Size of each function / variable and to which Memory Bank it is mapped.

2.1 These variables are global variables, not dynamic nor local (for dynamic / local, we use heap and stack which are not related to the script).

my goal is to move data / code from overfilled Memory Bank(s) to available Memory Bank(s) (using a script) - as simple as that.

The script will analyze the file it's provided with, and will re-map some code / variables to satisfy the above goal.

The main challenge:
The Functions / Data are divided into groups.

Therefore, say that I'd decide to move 139KB from Bank A to Bank C, the closest group I might find in Bank A is 180KB (or for example 100KB), and the script has to be aware of it.

My question is: what algorithm would you use?

 

[NorthGuy]

You lost me. You ask for help with the algorithm, and at the same time you refuse to accept any advise.

If you want to move blocks, it means that it is ok to move them. In other words, the algorithm does not have to keep the existing bank assignments. So why don't you tell us what prevents you from removing all the existing bank assignments and re-assigning from scratch?

 

[KeepItSimpleStupid]

I wrote real-time FORTRAN code on a Micro PDP-11 with RT11 F/B (Forground/Background). We could not add more stuff because we ran out of room. It's not just a case of what to put where, but who needs to call who. i.e. Overlays. Certain routines could swap to the same memory space. We did use one assembly language function for some reason (Move from previous Instruction Space) Nicely protected, Kernel and user I & D space. We, sort of, wanted to RSX-11 because of better memory management.

 

[electroRF]

You lost me. You ask for help with the algorithm, and at the same time you refuse to accept any advise.

If you want to move blocks, it means that it is ok to move them. In other words, the algorithm does not have to keep the existing bank assignments. So why don't you tell us what prevents you from removing all the existing bank assignments and re-assigning from scratch?

Hi NorthGuy,

I'll give you one example as for why it's good to divide a physical memory bank into different virtual memory banks - If you want to divide between data and code.

I'll get more into why it was done this way.

Do you have additional ideas as for why it's good?


Regarding the script.

This is my opportunity to write C++ & C# code, and I'd like to grab it with both hands.

I'd love to hear about an algorithm for how to best balance the Memory Banks.

 

[kubeek]

ElectroRf, if you don't answer the questions asked, no one will want to help you.
So once again, how severe is the overhead of bank switching?
Is it possible to remove all the bank assignements and re-assing from scratch?

 

[electroRF]

Hi Kubeek,

Thank you.

It'd not be possible to remove all bank assignments, I already suggested it before but it was decided not to at this stage.

 

[NorthGuy]

It'd not be possible to remove all bank assignments, I already suggested it before but it was decided not to at this stage.

Creating efficient software is hard as it is. It's getting much much harder if you have to comply with artificial constraints imposed by beurocrats. Would be interesting to know which thoughts (if any) brought them to this decision?

So, you can remove some assignments, but not all of them. Of course, for the algorithm to comply with this constrain, the algorithm must know which assignments are removable and which are not removable. How does the algorithm determines which is which, and what is an approximate percentage of removable vs non-removable assignments?