This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
Hi, I got idea from pipeline analysis discussion to use evolutionary algorithm to improve performance. I wrote a simple optimizer that tries does randomly permutes instruction sequence to determine best scheduling. It does relatively good job in that, sometimes we gain %1 over existing implementation. There are two benefits of evolver, first is that without scheduling constraints we can write code that is easier to review and then apply evolver which keeps code semantics. (I could supply sequence of swaps of adjacent instructions which do not interact and produce second implementaion from first one.) Second benefit is that we can do separate scheduling for each architecture with nearly zero additional effort which could also give us bit of performance. What I do is relatively simple so there is room for improvement. Main problem is that I do not know what is best representation. Instructions for partial order and it should be somewhat better to work on it and encode choices by inequalities that complete it to linear order but I do not know how. Second is limited knowledge of assembly we do not support control flow and do not know how determine if instruction flags affect control flow. Now I use EVOLVE_START EVOLVE_END blocks to mark basic blocks without control flow instructions in them. Second is that something could be gained by renaming registers but for this I would need to analyze what registers are available in given basic block. Next problem is that I determined parameters by trial and error. I want to add meta level that will also vary evolution parameters to get better results. What also is not entirely clear is that I use evolver to optimize some benchmark so we need to check if optimizations generalizes beyond that benchmark. An evolver is attached, I will send patches with optimizations if to see how successfull they will be.
Attachment:
evolver.tar.bz2
Description: Binary data
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |